Attached is a case for which ConvexPartition_HM fails

[GoogleCodeExporter]

I've attached sets of points for which convex partitioning fails.

cvxPartPolys0.txt:  outer boundary
cvxPartPolys1.txt:  hole
cvxPartPolys2.txt:  hole

removeHoles0.txt:  result of 'RemoveHoles()'

It appears that 'Triangulate_EC()' can't find an 'ear', so the process aborts.

Original issue reported on code.google.com by gbburkha...@gmail.com on 21 Dec 2011 at 9:55

Attachments:

• cvxPartPolys0.txt
• cvxPartPolys1.txt
• cvxPartPolys2.txt
• removeHoles0.txt

[GoogleCodeExporter]

There are two problems here:

There was indeed a bug in polypartition in the RemoveHoles method, which is now 
fixed.

But there is also a problem with your input that prevents it from working with 
polypartition:

Both cvxPartPolys1.txt and cvxPartPolys2.txt have two consecutive identical 
vertices, for example the vertex (-1, 1) is both the first and the last vertex 
in cvxPartPolys1.txt. In the current version of polypartition it is considered 
that polygons with two identical consecutive vertices are self-intersecting and 
thus not a valid input. Checking and cleaning the input in such cases is 
considered to be the responsibility of the caller.

Once you remove identical consecutive vertices, you should find that your 
example works with the most recent version of polypartition.

Original comment by ivan.fra...@gmail.com on 22 Dec 2011 at 1:29

• Changed state: Fixed

[GoogleCodeExporter]

I'm impressed with the quick fix.

Sorry about posting the examples with the duplicate vertices.  I had 
them in there to get a complete drawing with GnuPlot (plot 
"cvxPartPolys1.txt" with lines).  As you discovered, the problem could 
be demonstrated by omitting the last line of each file.

Thanks!

Original comment by gbburkha...@gmail.com on 22 Dec 2011 at 2:27