polypartition icon indicating copy to clipboard operation
polypartition copied to clipboard
verified publisher icon ivanfratric

ConvexPartition_OPT fails on some polys

Open abakobo opened this issue 6 years ago • 2 comments

Hi

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

abakobo avatar Jan 30 '19 14:01 abakobo

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.

ivanfratric avatar Feb 03 '19 19:02 ivanfratric

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

aaronfranke avatar Jan 07 '21 03:01 aaronfranke