Inconsistent behavior with holes that share a point

[GoogleCodeExporter]

Hi,

I am seeing inconsistent behavior with holes that share a vertex.  Everything 
here has been sanitized by clipper and guaranteed to have a 'strictly simple' 
output.

Example #1.  This triangulates fine:

Outline
10, 0
10, 10
0, 10
0,0

Hole 1
2, 1
3, 3
1, 2

Hole 2
3, 3
6, 4
4, 7

Example #2.  This causes a segmentation fault.

Outline
374000, 96000
374000, 317000
576000, 317000
576000, 96000

Hole 1
449000, 291000
393000, 205000
419000, 177000

Hole 2
539000, 138000
419000, 177000
420000, 139000

In both examples, the holes share one point.

Why does one crash, but the other doesn't?

Original issue reported on code.google.com by buckyballreaction on 20 Dec 2013 at 5:51

[GoogleCodeExporter]

The thing is that two holes that share a point actually form a weak polygon. I 
can understand the problem, clipper does make all polygons strictly simple but 
when you add two of these as holes you are actually creating a weak polygon out 
of two simple one's. 

Anyways poly2tri should be able to support these cases if when you create the 
points you make sure that shared points are one unique object.

Does hole 1 and hole 2 share the same point object for the shared point?

One dirty solution would be to shrink the holes a tiny amount that isn't 
visible to the naked eye. A simple way would be to loop thru the vertexes of 
each hole and move it them tiny bit: 
For a 3 vertex hole the unrolled loop would look like:
p0 = p0 + 2e-12*normalize(p1 - p0);
p1 = p1 + 2e-12*normalize(p2 - p1);
p2 = p2 + 2e-12*normalize(p0 - p2);

By moving the p0 closer to p1 along the edge they form you do a form of shrink 
that ensures that no new intersection between the holes will form when you 
"wiggle" each hole vertex.

The factor has to be atleast twice the size of the epsilon used given that all 
points is in the range [-1,1].

Original comment by thahlen@gmail.com on 20 Dec 2013 at 11:14

[GoogleCodeExporter]

Hi,

I'm not sure I fully understand the problem... but you are saying that if I can 
guarantee weakly-simple polygons (one unique object) for holes that share a 
vertex, then poly2tri should handle them?

I'd like to avoid shrinking as it'll add more computation requirements to an 
already expensive process (which is why we chose poly2tri to begin with - it is 
fast!).  Also, with our use case, there's no guarantee that shrinking won't 
create the exact same situation since we have to feed very dirty data into 
clipper.

I'll have to study clipper a bit more to see what it can do in this respect.

Original comment by buckyballreaction on 20 Dec 2013 at 4:22

[GoogleCodeExporter]

Check if the holes polygons created by clipper use same object instance for 
shared points or if clipper creates a new point for every hole.

The problem if you have two different point instances with same coordinate is 
that the graph of connected points poly2tri uses during triangulation will not 
be correct and the triangulation can fail due to this.

Think of the triangulation as this.

You have a list of unique points to triangulate.
You can add some constraints that some triangle edges must exist between some 
points.

This is all poly2tri cares about. 

When you add holes what you actually do is add more points to the list of 
unique points. Then enforce some edges between points in this list.

What makes poly2tri a polygon triangulator is the knowledge that we have a 
closed loop of constraints forming an outer hull. With this knowledge we can 
pick a triangle inside and loop thru all triangles and just save those inside 
this hull.

Original comment by thahlen@gmail.com on 20 Dec 2013 at 5:44

[GoogleCodeExporter]

The easiest way would be if you could make clipper return a list of all points 
and the polygons would just be list of indexes to this list of points.

Original comment by thahlen@gmail.com on 20 Dec 2013 at 5:46

[GoogleCodeExporter]

Ah OK, that makes sense (I also read up a bit more on the sweep-line 
algorithm).  Although I'm still a little curious as to why both of my examples 
above don't fail - could it be because of the resolution or accuracy of the 
sweep-line?

Clipper does not use the same object instance for each Point, there is almost 
no pointer usage, everything is on the stack.  

Also, here is the documentation it gives on its output with respect to 
weakly/strictly simple polygons:

http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes
/Clipper/Properties/StrictlySimple.htm

It looks like output polygons are guaranteed to be simple in some form, or 
guaranteed to be strictly simple if you set the flag.  No guarantee or option 
of weakly-only, however.  In my code we use the StrictlySimple(true) flag 
because it reduced the crashing cases significantly; just the one in my opening 
post remains so far.

Also, when I manually adjust the two holes, in the crashing case, into one hole 
to form a weakly simple polygon by clipper's definition, it still crashes:

hole:
393000, 205000
419000, 177000
420000, 139000
539000, 138000
419000, 177000
449000, 291000

Original comment by buckyballreaction on 20 Dec 2013 at 6:19

[GoogleCodeExporter]

Adding the same point twice as different instances will make poly2tri behave in 
an undefined manner. Sometime it will work and sometimes not, it all depends on 
how the two identical points end up in the advancing front and how the 
constraints are directed. The connected graph will be flawed but under some 
circumstances the triangulation will work anyways.

This is why poly2tri only supports simple polygons.

Given you can enforce that holes just share unique common points, poly2tri can 
triangulate these polygons.

Original comment by thahlen@gmail.com on 20 Dec 2013 at 6:45

[GoogleCodeExporter]

Perhaps I'm not thinking out-of-the-norm enough to understand (please forgive 
me).  

Are you saying that the hole that crashes above can still be triangulated if 
fed properly into poly2tri?  If so, what would the geometry look like?  Can 
just simple list of (in this case, 5) points suffice for input?

Original comment by buckyballreaction on 20 Dec 2013 at 10:48

[GoogleCodeExporter]

You would have to build you hole like this to support shared points

pseudo code:

list = { new Point( 393000, 205000 ), 
         new Point( 419000, 177000 ), 
         new Point( 420000, 139000 ), 
         new Point( 539000, 138000 ), 
         new Point( 449000, 291000 ) };

hole1 = { list[4], list[0], list[1] };
hole2 = { list[3], list[1], list[2] };

Most likely you will have to spend more time remapping points than it would 
take to just shrink the holes like I wrote above. Which is a pretty straight 
forward and fast fix. You could probably skip normalization of the vector if 
you know your line segments isn't to short or long.

Since I really don't know what you are doing before and after triangulation I 
can't give any better suggestions than this.

Original comment by thahlen@gmail.com on 20 Dec 2013 at 11:47

[GoogleCodeExporter]

What you would have after the shrink operation is this overly exaggerated.

Original comment by thahlen@gmail.com on 21 Dec 2013 at 12:15

Attachments:

• hole_shrink.png

[GoogleCodeExporter]

Very interesting...  now I understand what you meant by "shared points are one 
unique object".

I will implement the shrinking and see how everything goes.  I will also 
continue the discussion about unique Point objects as an output of clipper.

Thanks again!

Original comment by buckyballreaction on 21 Dec 2013 at 7:13

[GoogleCodeExporter]

Using the clipper OffsetPolygon class to shrink the polygons slightly added 
about 50% processing time overhead, but did resolve the issues.  This was a 
little too much overhead for my tastes.

I did, however, adapt your 'wiggle-shrink' algorithm to our situation.  Since 
we upscale our points into clipper by 1000, all I needed to do was shrink the 
output back along the line by 1.  I can do it in-place with the clipper output 
like so:

// Shrink large polygons by reducing each coordinate by 1 in the
// general direction of the last point as we wind around
static void edgeShrink(Path &path) {
   unsigned int prev = path.size() - 1;
   for(unsigned int i = 0; i < path.size(); i++) {
      // Adjust coordinate by 1 depending on the direction
      path[i].X - path[prev].X > 0 ? path[i].X-- : path[i].X++;
      path[i].Y - path[prev].Y > 0 ? path[i].Y-- : path[i].Y++;

      prev = i;
   }
}

This simple method didn't add measurable difference to the computation time and 
the crashing case is also solved.

Good idea!

Original comment by buckyballreaction on 21 Dec 2013 at 10:42

[GoogleCodeExporter]

Great! :)

Original comment by thahlen@gmail.com on 21 Dec 2013 at 11:37

• Changed state: WontFix

[GoogleCodeExporter]

buckyballreaction, why didn't you choose to remap points instead?
Using std::map and std::pair that should have been quite fast, and it looks 
like it's more robust than messing with coordinates. What do you think?

Original comment by motond...@gmail.com on 30 Apr 2014 at 4:02

[GoogleCodeExporter]

I'm not sure I understand what you mean by 're-map' points.  

The original issue was due to a conflict between having duplicate points in the 
input but poly2tri requiring only one instance of each point.

My solution was a quick way to guarantee no duplicate points with the output 
from Clipper.

Original comment by buckyballreaction on 30 Apr 2014 at 4:28

[GoogleCodeExporter]

I mean that the solution proposed by thahlen in comment #8 sounds not too 
inefficient. I would build such a map:

std::map<std::pair<long,long>, Point*> unique_points;

and then loop through Clipper's output to populate it or reuse existing Point 
pointers if the coordinate pair was already seen.

Since I would like to go this way, I was wondering why you thought that 
manipulating coordinates to perform shrinking was more robust. I would be 
afraid of the existence of another point at the new, shifted, coordinates...

From what I understood from thahlen's words, poly2tri is not afraid of polygons 
or holes sharing a point, it's just afraid of duplicate allocated point 
structures with same coordinates - which is very good news and a lot less 
strict than I thought since an easy workaround can be applied!

Original comment by motond...@gmail.com on 30 Apr 2014 at 6:34

[GoogleCodeExporter]

Ah OK.  I understand now.  That may definitely be a more exact solution.

In my case, however, speed is paramount. I'm doing large-scale triangulation 
during the level loading for my game.  Before my above code I had already 
up-scaled floating point values by 1000 and converted them to integers (for 
input to Clipper).  My solution is not quite exact, but close enough at our 
level.  It also has only 2 branches and arithmetic operations without new 
object allocation (I think).

I do not know how much slower your implementation would be, but I'd expect it 
to be so.  I'd be interested in timings between the two if you happen to run 
them.

Original comment by buckyballreaction on 30 Apr 2014 at 7:05

[GoogleCodeExporter]

Okay, thanks for feedback. I understand your performance needs. In my case I 
prefer robustness over speed. Not sure I'll do comparisons, but will definitely 
share my code if I'm going this way.

Original comment by motond...@gmail.com on 30 Apr 2014 at 8:15