ConvexPartition_OPT fails on some polys

ivanfratric / polypartition

Tiny Polygon Partitioning and Triangulation Library

MIT License

644 stars 115 forks source link

ConvexPartition_OPT fails on some polys #35

Open abakobo opened 5 years ago

abakobo commented 5 years ago

ConvexPartition_HM seems to work with any input polygon. But ConvexPartition_OPT seems to fail with larger(?) polys. The attached file contains a poly that will not be Partitionned with _OPT (an empty list is returned). With _HM it will be partitionned correctly though.

Best Regards

polyfourte.txt

ivanfratric commented 5 years ago

Thank you for reporting this! Given that I haven't been doing any computational geometry for a while now, any help in figuring out the root cause would be greatly appreciated. ConvexPartition_OPT does have an O(n^3) space complexity so it wouldn't be well suited for very large polygons, but for 69 points (like in the example you provided) it should work fine.

aaronfranke commented 3 years ago

Confirmed, running Triangulate_OPT on this polygon results in a blank image, no data is output. Everything except Triangulate_OPT works on this polygon.

Here's an updated test case: issue-35.txt, here are some test outputs: issue-35.zip