infinite loop in DTSweep.edgeEvent

Keith Willenson

unread,

Feb 12, 2014, 3:52:27 PM2/12/14

to poly...@googlegroups.com

Using the attached data set, it goes into an infinite loop because, in DTSweep.edgeEvent, ep, p1, and eq are collinear, BUT p1 is NOT between ep and eq.

So I have made the following changes. If these changes produce some unexpected side effect or if the data is somehow bad, I'd like to know so I can make appropriate adjustments.

I added this method to TriangulationPoint

<code>

/**
* returns true if this point is in bounds a->b, inclusive of ends<br/>
* reduced number of method calls and (hidden) comparisons at expense of
* additional storage (two doubles) and possibly some code clarity.<br/>
* if (getX() < Math.min(a.getX(), b.getX())) { return false; }<br/>
* might be easier to understand.
* @param a
* @param b
* @return
*/
public boolean inBounds(TriangulationPoint a, TriangulationPoint b)
{
// check if x in bounds
double min = a.getX(),
max = b.getX(),
value = getX();
if (min > max)
{
double temp = min;
min = max;
max = temp;
}
if (value < min)
{
return false;
}
else if (value > max)
{
return false;
}
// end check if x in bounds

// check if y in bounds
min = a.getY();
max = b.getY();
value = getY();
if (min > max)
{
double temp = min;
min = max;
max = temp;
}
if (value < min)
{
return false;
}
else if (value > max)
{
return false;
}
// end check if y in bounds

return true;
}

</code>

Then I added the following to DTSweep.edgeEvent

<code>

if( o1 == Orientation.Collinear )
{
// start added code here
if (! p1.inBounds(eq, ep))
{
return; // not really collinear
}
// end added code

</code>

and

<code>

if( o2 == Orientation.Collinear )
{
// start added code here
if (! p2.inBounds(eq, ep))
{
return; // not really collinear
}
// end added code

</code>

VirtualCurveData.txt

obi

unread,

Feb 12, 2014, 6:41:27 PM2/12/14

to poly...@googlegroups.com

Looking at your point data the first i would try is to round values to 12 decimals or less.

Poly2tri uses 1e-12 as epsilon when testing collinearity.

Even if you got 2 points and the third point is considered collinear is doesn't matter if it is outside the range of the first two. If we try to create a triangle it will be degenerate. This can happen when you feed poly2tri points with to high resolution and they are very close to a straight line.

Just think of a simple polygon with two rectangular holes, see attached picture. Very easy to triangulate but if you feed poly2tri with two holes where the bottom edge of the two holes just differ in lets say the 14 or 15th decimal. You might end up with a case where poly2tri tries to generate a degenerate triangle and fails.

poly2tri.png

Keith Willenson

unread,

Feb 13, 2014, 12:51:09 PM2/13/14

to poly...@googlegroups.com

Rounding to 12 decimals worked. Removed extra code. Thanks.

Could this be documented or automatically done (round to epsilon) in triangulate?

obi

unread,

Feb 14, 2014, 6:18:17 AM2/14/14

to poly...@googlegroups.com

Yeah I think there should be added a note that for best floating point robustness during triangulation the point data should be centered around 0, scaled in the range -1,1 and rounded to 12 decimals.

In most of the cases tho the data isn't high precision and the range is not so big that centering around 0 is needed. So then it would mean some unneeded transforms.

Reply all

Reply to author

Forward