Concave input polygons fail to convexify

GoogleCodeExporter commented 9 years ago

What steps will reproduce the problem?
1. Input a polygon with convex edge
2. Run ConvexPartition_HM

Example polygon from my data set
x=-2107 y=-1420 
x=-2107 y=-1547 
x=-2090 y=-1547 
x=-2090 y=-1579 
x=-2107 y=-1579 
x=-2107 y=-1547 
x=-2122 y=-1547 
x=-2122 y=-1579 
x=-2107 y=-1579 
x=-2107 y=-1667 
x=-1724 y=-1667 
x=-1724 y=-1420 

The library doesn't expressly mention its handling of this from what I can see 
but it appears that what happens is that the triangulation step fails, and the 
function fails to convexify the region. It would be great if the triangulation 
routines could be made to accomodate convex polygons for robustness. 

I'm feeding the polypartition library the polygonal output of the clipper 
library that I use to do boolean polygon operations. I have obstacles on the 
interior of a polygon working well, but when I place an obstacle on the edge, 
such that it creates a concave polygon around the edge where the obstacle is, 
the triangulation fails.

Original issue reported on code.google.com by jswig...@gmail.com on 24 Feb 2013 at 3:13

GoogleCodeExporter commented 9 years ago

Hi, in the PolyPartition library, the polygons such as the one you provided are 
considered self-intersecting. Please see the image of the polygon you provided 
in the attachment. Self-intersecting polygons are not handled, as stated on the 
front page. The library might be extended at some point to also handle such 
input, however there are no specific plans for this at the moment.

Original comment by ivan.fra...@gmail.com on 24 Feb 2013 at 4:19

Changed state: WontFix

Attachments:

test.png

GoogleCodeExporter commented 9 years ago

Doh sorry about that. I must have misinterpreted my debug rendering. I probably 
got confused by the wierd 'even-odd' output of the clipper library that I use 
first before polypartition. I fixed issues with that and so far I've got things 
working and not failing at all yet. I'll try reverting the triangulate call and 
see if its still solid. Here's a quick demo.

http://www.youtube.com/watch?v=WXKkdkl2rwQ&feature=youtu.be

Original comment by jswig...@gmail.com on 24 Feb 2013 at 7:10

icehuli / polypartition

Concave input polygons fail to convexify #4