8000 Improve Convex Hull by ferk6a · Pull Request #752 · cp-algorithms/cp-algorithms · GitHub
[go: up one dir, main page]
Skip to content

Improve Convex Hull #752

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 7 commits into from
Oct 25, 2021
Merged

Improve Convex Hull #752

merged 7 commits into from
Oct 25, 2021

Conversation

ferk6a
Copy link
Contributor
@ferk6a ferk6a commented Oct 12, 2021

This fixes the convex hull page which was a tad confusing. The title of the page was "Convex Hull construction using Graham's Scan", and the reader is presented with the Monotone Chain algorithm by Andrew's instead (and no mention of the name "Monotone Chain", although Andrew's name is subtly in there), rather than the original Graham's Scan. So in this PR we:

  • Rename the page from "Convex Hull construction using Graham's Scan" to just "Convex Hull construction".
  • Add the original Graham's Scan to the page, along with renaming the existing code to Monotone Chain.
  • Add collinearity options for both algorithms, along with a explanation of the change required in Graham's Scan.
  • Add substantial testing for everything added.
  • Add a new convex hull problem: Onion Layers.

I think the convex hull explanation is far from ideal, but the changes seem to me like a good improvement. I'm also not sure on the convention for filenames, I used dashes in the Markdown files and underscores in source code files.

@jakobkogler
Copy link
Member

Thanks. That looks like a pretty good addition.
I'll try to review it in the next couple of days. Sorry for the long wait.

jakobkogler
jakobkogler approved these changes Oct 25, 2021
View reviewed changes
Copy link
Member
@jakobkogler jakobkogler left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hey.
Sorry again for the long wait. I've been really busy.

The article looks really clean, thanks for all the work.
I haven't checked every single line of the code, but I tried some tricky examples myself, and everything looks good.

@jakobkogler
Copy link
Member
jakobkogler commented Oct 25, 2021 •
edited
Loading

And like you said, some parts of the explanation could use some improvements. E.g. I didn't understand why we only need to reverse the last few collinear points, and e.g. not collinear points somewhere in the middle (I eventually figured it out by looking at some examples).
But the article is already a lot better, so I'm very happy to merge it.
Thanks again ❤️ 🙇‍♂️

@jakobkogler jakobkogler merged commit 2313f8d into cp-algorithms:master Oct 25, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@jakobkogler jakobkogler jakobkogler approved these changes

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@ferk6a @jakobkogler
0