icehuli / polypartition Goto Github PK

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.

What steps will reproduce the problem?

Square input poly with an interior square hole seems to be failing

input poly 1 
-1423 479
-1423 419
-1363 419
-1363 479

input poly 2 - marked as hole
-1403, 459
-1383, 459
-1383, 439
-1403, 439

Thanks

It would be very useful for me to include an index to the original polygons 
vertex-list to the points in the output, so that I don't have to find 
corresponding vertices by computing distances.

Hello.

using namespace std; pollutes global namespace. It is a good practice not to do 
this in the header files. I've cleaned the your header from this evil :)
https://www.dropbox.com/s/t9ofl7w51y3qzn5/polypartition.h
It will be great if you can commit this. 

Also see: 
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml
for more details and tips

Also I made some minor refactorings in cpp file:
https://www.dropbox.com/s/61xp6cb79hqzpx9/polypartition.cpp

This is a very helpful library, thank you.
However there are a few things that could be improved:
a) Return the triangulated surface either using an index buffer or iterators, 
not by copying the points.
b) Use iterators as function parameters to allow the user to also use other 
containers than std::list.
c) Maybe (I am unsure if this is possible), use template programming to accept 
several types of input points. There are many libraries which provide some sort 
of 2D vector (double or float), whose access patterns are very similar (e.g. 
vec.x or vec.x()). Maybe these can be generalized so that you don't need to do 
type conversions.

gcc 4.5.1 reported possible use of uninitialized variables.  It looks like 
there might be some problems:

line 414:

    if(vertices[j].angle > ear->angle) {
        ear = &(vertices[j]);
    }

The value of 'ear' is set, but earfound is not set.  So subsequently, this code 
will be executed:

        if(!earfound) {
            delete [] vertices;
            return 0;
        }

Suggest dropping 'earfound', set 'ear=0' initially, and test for 'ear' not null 
instead of "if(!earfound).

line 579:  potential use of uninitialized variable 'minweight'  Suggest 
initializing to -DBL_MAX.

Hello,
what input problems might cause Triangulate_MONO() to return 0?

(or, same thing, what requirements are there on input for triangulation to 
succeed?)

I'm going to append actual failing coordinates (polygon with holes) later today 
or tomorrow, as well as check whether partitioning fails or actual 
triangulation. Is there a format you prefer?

Thank you!

Hope the number of points less than 8.The box2d shape can only have less than 8 
points.

Hi Ivan Fratric,

I use Triangulate_EC to triangulate polygons with hole. When the hole and outer 
polygon have common node, the result is wrong. Could you please help me to take 
a look at it?
Thanks,

Tang Laoya

PS:
data example 1:
2
4
1
 -1.191966510797976E-003  0.202231151541577     
  8.150796829630741E-003  0.186049010752862     
  2.980143192424173E-002  0.198549010752862     
  2.045866858381302E-002  0.214731151541577 
8
0      
  3.525591640424161E-002  0.213001949189431     
  4.514750408646251E-002  0.211126769678226     
  4.301140661905761E-002  0.181202914852858     
 -1.683630303167994E-002  0.185475109787668     
 -1.470020556427498E-002  0.215398964613036     
 -4.642556696250064E-003  0.215850079145971     
  1.537278144042436E-002  0.215352008559904     
  2.045866858381302E-002  0.214731151541577     


data example 2:
2
4
1
  2.980143192424157E-002 -0.198549010752862     
  8.150796829630581E-003 -0.186049010752862     
 -1.191966510798143E-003 -0.202231151541577     
  2.045866858381282E-002 -0.204731151461601
8
0       
 -4.642556696250190E-003 -0.215850079145971     
 -1.470020556427507E-002 -0.215398964613036     
 -1.683630303168007E-002 -0.185475109787668     
  4.301140661905749E-002 -0.181202914852858     
  4.514750408646243E-002 -0.211126769678226     
  3.525591640424149E-002 -0.213001949189431     
  2.045866858381282E-002 -0.204731151461601     
  1.537278144042421E-002 -0.215352008559904     

What steps will reproduce the problem?
1. Compile polypartition.h and polypartition.cpp normally
2. Get error in MSVC2010 Express: "Set is not a template"

Please provide any additional information below.

The problem was fixed by specifying the std namespace with set, the library 
compiled fine after this.

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.