-
Notifications
You must be signed in to change notification settings - Fork 186
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.
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
Incorrect convex hull for nearly collinear points #1028
Comments
Can you try with |
Thanks for the suggestion, |
Yes, generally, floating-point numbers has some caveats when converting between display and internal representation. For instance, If you want to use fixed point/precision, please scale and convert to integers and run the hull (the crate supports hull on |
Closing; the output is correct for the given input (and data type). |
Consider these points that roughly form a triangle-like polygon:
Points A, B, C are the 3 points on the top right, from right to left. Point A is the topmost point.
The convex hull has all points of the input polygon. But Point B is actually slightly lower than the line from C to A. Therefore, the convex hull should go directly from C to A, skipping point B.
I am indeed using a particular CRS, hence why these numbers look unnatural. But plotting it on a "normal" 2D plane, it still appears that point B is unneeded for the convex hull. You can paste the printed output into desmos:
Furthermore, JTS correctly returns the answer as
POLYGON ((813580.3 817846.6, 813290.44 817857.06, 813462.3 817923.8, 813517.7 817943.9, 813544.4 817952.9, 813580.3 817846.6))
. So this shouldn't be a CRS issue.The last two points (leftmost two points) can be removed without affecting the result and this bug
The text was updated successfully, but these errors were encountered: