infinite loop on ConstrainedPointSet

[keith.w...@gmail.com]

When I try to triangulate a particular set of data (not all data), I get the following error output:

                                           .

                                           .

                                           .

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipEdgeEvent(DTSweep.java:847)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipScanEdgeEvent(DTSweep.java:991)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipEdgeEvent(DTSweep.java:847)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipScanEdgeEvent(DTSweep.java:991)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipEdgeEvent(DTSweep.java:847)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipScanEdgeEvent(DTSweep.java:991)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipEdgeEvent(DTSweep.java:847)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipScanEdgeEvent(DTSweep.java:991)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipEdgeEvent(DTSweep.java:847)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipScanEdgeEvent(DTSweep.java:991)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipEdgeEvent(DTSweep.java:847)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipScanEdgeEvent(DTSweep.java:991)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipEdgeEvent(DTSweep.java:847)

There is a lot more of this same stuff before, but I think you get the point. Obviously I am using the Java version.

It's not really an infinite loop, it's infinite recursion that runs out of resources.

When I log output, it is flipping the same two points back and forth, so first is ep->eq, then next is eq->ep, then ep->eq,. then eq->ep, etc.

Logging was added in DTSweep.flipScanEdgeEvent(). op equals ep for the call to flipEdgeEvent

Is that enough information to help you find the problem?

I thought not. I have attached at file DummyData.java. Change the package to match your setup and it will load the data that is causing my problem.

Any help at all would be welcome.

Thanks.

Keith

[obi]

I blame myself for adding a dangerous API for ConstrainedPointSet :)

The thing is the way you create you data you create a point with same coordinate multiple times, this is not allowed. It is like adding same point multiple times to the list of points. The inital constructor I created for ConstrainePointSet is:

public ConstrainedPointSet( final List<A> points, final int[] index )

eg. You create a list of points in the XY plane. Then give a list of index pair which defines between which of these points there should be constraints.

Out of convenience I added the constructor:

public ConstrainedPointSet( final List<A> points, final List<A> constraints )

The java doc says: constraints - Pairs of two points defining a constraint, all points <b>must</b> be part of given PointSet!

So the list of constraints you add must be using the same Objects as the list of points. From your DummyData I see you both create new points for each constraint but also have multiple identical constraints?

// 34
constraints.add( new TPoint(115.88886, 2316.457633, 1006.0));
constraints.add( new TPoint(119.521649, 2291.996358, 1006.0));
// 35
constraints.add( new TPoint(115.88886, 2316.457633, 1006.0));
constraints.add( new TPoint(119.521649, 2291.996358, 1006.0));

So what you need to do is to create you constraints like this

// 10

 constraints.add(  tPoints.get(11)   );
 constraints.add(  tPoints.get(123) );

// 11

 constraints.add(  tPoints.get(75)  );
 constraints.add(  tPoints.get(12)  );

and also make sure you don't add same constraint twice.

 

[keith.w...@gmail.com]

I think I used that ConstrainedPointSet because it was in the examples. I like the indexed version better, although you may want to consider ConstrainedPointSet<List<TriangulationPoint> tPoints, List<Integer> constraints);

Apparently, I was sending duplicate constraints.

I have altered my code to used the int[] version and attached an updated DummyData.java. It still has the same infinite looping (recursion) error.

Thanks for looking at this.

Keith

[obi]

Could you possible dump the data as two list of values

like:( I guess you can skip the z coordinates)

0.0, 2275.296657, 1006.0,7.95038, 2434.01614, 1006.0,18.8695, 3116.654757, 1010.0,32.9059, 3165.958557, 1012.0,40.728128, 3117.860305, 1010.0 ....

0,6,1,5,2,4,3,7, .....

I assume there is no intersecting constraints then the first thing I would test is this:

https://groups.google.com/forum/#!topic/poly2tri/fGnjCz3ShCc

Center the data around 0 and scale it to be in the range [-1,1]. The epsilon in poly2tri is picked assuming the data to be in this range.

So if your issue is a float precision problem this might be the solution.

Can't say anything more until I get the data in a format I can handle.

-Thomas

[keith.w...@gmail.com]

After scaling the data, I'm getting a new error:

        at org.poly2tri.triangulation.delaunay.sweep.DTSweep.fillLeftBelowEdgeEvent(DTSweep.java:517)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.fillLeftBelowEdgeEvent(DTSweep.java:517)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.fillLeftBelowEdgeEvent(DTSweep.java:517)

data file in the format you want attached (DummyData.txt)

Keith

[obi]

Clearly poly2tri doesn't like this dataset at all :(

I have started to look at it, this might take a little time to figure out.

[obi]

I have located an error in the dataset! Duplicate points

-0.05374562839318825 -0.08316640472611317

-0.1565729970332478,0.18401125058373138

0.1563718745249352,0.5802322275839776

exists twice. poly2tri doesn't allow 2 points with identical coordinates. So what is happening is you have two constraints that share a point but there will be two different instances of that point in the list of point poly2tri traverse. This will mean that the graph built during triangulation will be defective.

Since the indexing will be affected i could not just remove those points so I just altered one of the pair of identical points and now the triangulation workes for me!

[obi]

This is the end result of my triangulation

[keith.w...@gmail.com]

Thanks. That solved it. The problem was not enough precision in the sorting/unique point routine in my software. Once the precision was increased, the duplicate points disappeared.

The odd thing is that the triangulation routine seems to work exactly as expected (at least as I expect it to) whether or not I scale the data to -1/1. It works well on multiple unscaled data sets. 

[obi]

Great!

Yeah translating and rescaling is most likely not needed but if you need those 12 points precision poly2tri uses as epsilon thats the way to go. 

There have been some cases where users have had point sets with very large numbers or a range way of center resulting in floating point issues.

But it's always the first thing I try on failed triangulation.