Triangulate crashes in sweep.cc:703

[GoogleCodeExporter]

Hi there,

I've got a crash within sweep.cc:703 at "Point& op = *ot.OppositePoint(*t, p);" 
as the line 702 "Triangle& ot = t->NeighborAcross(p);" puts NULL  into the "ot" 
pointer. In line 705 this will be checked "if (&ot == NULL) {" but thats 
actually too late to so.

What steps will reproduce the problem?
1. I used the following Points which are actual locations (lat, lon)
x: 53.054451, y: 8.785962
x: 53.054460, y: 8.785930
x: 53.054466, y: 8.785924
x: 53.054469, y: 8.785912
x: 53.054468, y: 8.785901
x: 53.054466, y: 8.785894
x: 53.054462, y: 8.785889
x: 53.054454, y: 8.785888
x: 53.054448, y: 8.785890
x: 53.054443, y: 8.785898
x: 53.054442, y: 8.785912
x: 53.054445, y: 8.785923
x: 53.054438, y: 8.785949
x: 53.054324, y: 8.785840
x: 53.053981, y: 8.785509
x: 53.053989, y: 8.785484
x: 53.053993, y: 8.785480
x: 53.053997, y: 8.785471
x: 53.053998, y: 8.785460
x: 53.053997, y: 8.785450
x: 53.053993, y: 8.785441
x: 53.053989, y: 8.785438
x: 53.053987, y: 8.785437
x: 53.053978, y: 8.785438
x: 53.053972, y: 8.785447
x: 53.053969, y: 8.785457
x: 53.053969, y: 8.785467
x: 53.053972, y: 8.785476
x: 53.053973, y: 8.785479
x: 53.053968, y: 8.785496
x: 53.053855, y: 8.785387
x: 53.053835, y: 8.785368
x: 53.053659, y: 8.785197
x: 53.053627, y: 8.785167
x: 53.053582, y: 8.785123
x: 53.053518, y: 8.785061
x: 53.053215, y: 8.785930
x: 53.054318, y: 8.786995

2. Filled them into a Points array and put them into the CDT object,
3. Called Triangulate() on the CDT object and got the NULL Pointer exception.

Any ideas what is wrong with my dataset?

Thanks in advance!

Jan S:

What is the expected output? What do you see instead?

What version of the product are you using? On what operating system?

Please provide any additional information below.

Original issue reported on code.google.com by imp...@gmail.com on 6 Mar 2014 at 4:34

[GoogleCodeExporter]

Looking at your set of values this is most likely a result of lack of floating 
point precision. 

This is because of your data range. If you translate and scale your point 
values to be in the range -1 and 1 you should be fine I think.

Just translating to be in centered around 0 should be enough but the epsilon 
used in the lib is tuned for values in the range 0 and 1. So scaling helps with 
precision tests to.

Original comment by thahlen@gmail.com on 6 Mar 2014 at 6:03

[GoogleCodeExporter]

So if you have your points in an array[] you should try this:
Sometime you might also have to round values to 12 decimals since poly2tri uses 
en epsilon of 1.0e-12 for some tests.

double d;
double[] range = new double[] { Double.MAX_VALUE, 
Double.MIN_VALUE,Double.MAX_VALUE, Double.MIN_VALUE };
double[] center = new double[2];

for( int i=0; i<array.length; i += 2 )
{
   range[0] = Math.min( array[i], range[0] );
   range[1] = Math.max( array[i], range[1] );
   range[2] = Math.min( array[i+1], range[2] );
   range[3] = Math.max( array[i+1], range[3] );
}

center[0] = (range[0] + range[1])/2;
center[1] = (range[2] + range[3])/2;

if( (range[1]-range[0]) > (range[3]-range[2]) )
{
   d = 2/(range[1] - range[0]);  
}
else
{
   d = 2/(range[3] - range[2]);  
}

for( int i=0; i<array.length; i += 2 )
{
   array[i] = d*(array[i] - center[0]);
   array[i+1] = d*(array[i+1] - center[1]);
}

Original comment by thahlen@gmail.com on 6 Mar 2014 at 6:24

[GoogleCodeExporter]

This was a precision issue in input data

Original comment by thahlen@gmail.com on 2 Apr 2014 at 9:47

• Changed state: WontFix