Triangulations fails with null pointer exception

[GoogleCodeExporter]

What steps will reproduce the problem?

I tried to triangulate a polygon and it failed with a null pointer exception. I 
attached a file which describes the polygon. For the description of the polygon 
i used the simple feature access specification. If you would prefer another 
format I could provide it to you.

Interestingly the triangulation fails only sometimes with a null pointer 
exception. Besides this polygon I run poly2tri on many polygons. And in some 
runs it fails here, other runs are fine. In general I experience problems if 
points of the outer shell and from holes are equal or if two holes (like in 
this case) have an equal point.

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

This is the nullpointer exception I get:
java.lang.NullPointerException
    at org.poly2tri.triangulation.delaunay.sweep.DTSweep.flipEdgeEvent(DTSweep.java:647)
    at org.poly2tri.triangulation.delaunay.sweep.DTSweep.edgeEvent(DTSweep.java:632)
    at org.poly2tri.triangulation.delaunay.sweep.DTSweep.edgeEvent(DTSweep.java:584)
    at org.poly2tri.triangulation.delaunay.sweep.DTSweep.edgeEvent(DTSweep.java:584)
    at org.poly2tri.triangulation.delaunay.sweep.DTSweep.edgeEvent(DTSweep.java:349)
    at org.poly2tri.triangulation.delaunay.sweep.DTSweep.sweep(DTSweep.java:111)
    at org.poly2tri.triangulation.delaunay.sweep.DTSweep.triangulate(DTSweep.java:72)
    at org.poly2tri.Poly2Tri.triangulate(Poly2Tri.java:108)
    at org.poly2tri.Poly2Tri.triangulate(Poly2Tri.java:98)
    at org.poly2tri.Poly2Tri.triangulate(Poly2Tri.java:67)

What version of the product are you using? On what operating system?
poly2tri 0.1.1 on windows 7

Please provide any additional information below.

I run the debugger and in DTSweep.flipEdgeEvent it seems to me that there is 
missing a neighbor for the current triangle. Because the DelaunayTriangle ot is 
set to null.

Following variables are present:
t = [[1.6474112E8,6.10009088E8], [1.6474112E8,6.09992704E8], 
[1.64839424E8,6.0997632E8]]
p = [1.6474112E8,6.09992704E8]
ep = [1.64724736E8,6.09992704E8]
eq = [1.6474112E8,6.09992704E8]
neighbors[0] = [[1.6474112E8,6.09992704E8], [1.64724736E8,6.09992704E8], 
[1.64839424E8,6.0997632E8]]
neighbors[1] = null
neighbors[2] = [[1.64724736E8,6.09992704E8], [1.6474112E8,6.09992704E8], 
[1.6474112E8,6.10009088E8]]

Original issue reported on code.google.com by csp....@googlemail.com on 12 Nov 2010 at 10:18

Attachments:

• polygon.txt

[GoogleCodeExporter]

That file contains 3 different polygons and I have no problem triangulating 
them.

What is weird in your additional information is triangle t, it seems to contain 
2 points from the second triangle set and one point from the first. Maybe you 
are adding the point to a list without clearing it between triangulations?

Also the triangulation lib assumes all input polygons is simple non self 
intersecting. So it will fail if you have multiple points on the exact same 
coordinate or add holes that share points with the polygon.

Since validation of all input hits performance the only duplicate points that 
are removed is if first and last point is the same in a given polygon. Other 
validation will have to be done prior to triangulation. I also sorry that 
Poly2Tri does not include a polygon validation tool at this time.

Original comment by thahlen@gmail.com on 13 Nov 2010 at 9:50

[GoogleCodeExporter]

> Maybe you are adding the point to a list without clearing it between 
triangulations?
I don't unterstand what you mean. I create a new PolygonPoint for every point I 
have and add them to a list. Then I pass the list as argument to the polygon 
constructor.

> Also the triangulation lib assumes all input polygons is simple non self 
intersecting.
>So it will fail if you have multiple points on the exact same coordinate or 
add holes that share points with the polygon.
Yes that is exactly what I do. Is there a possibility to enhance your library 
to handle holes that have one point in common with the polygon? Because I think 
that are also valid polygons, that are quite common and in some simple test 
cases your library already triangulates this polygons fine.

Original comment by csp....@googlemail.com on 15 Nov 2010 at 8:37

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

In the polygon.txt file you sent there are 3 separate polygons. 

Neighter one of the polygons contains the three points in your debug info.
t = [[1.6474112E8,6.10009088E8], [1.6474112E8,6.09992704E8], 
[1.64839424E8,6.0997632E8]]

Point 1.6474112E8,6.10009088E8 is in the second polygon and so is 
1.6474112E8,6.09992704E8. Tho 1.64839424E8,6.0997632E8 is part of the first 
polygon in polygon.txt

In some way you send in the points for multiple polygons as one polygon to the 
triangulator, atleast if you use the data in the polygon.txt file?

Original comment by thahlen@gmail.com on 15 Nov 2010 at 8:53

[GoogleCodeExporter]

In the polygon.txt is only defined one polygon. The first polygon is the shell 
and the other two polygons are holes of the first polygon.

Original comment by csp....@googlemail.com on 15 Nov 2010 at 11:32

[GoogleCodeExporter]

I was translating and scaling the input coordinates and then triangulating, 
just so I could display the result on the screen. Then I had no issues. 
I did just something simple like this:
list.add(new PolygonPoint(1647 - data[i]/1e5, 6099 - data[i+1]/1e5));

Now I tried plugging in the large values and then I get the same error as you.

I'm no expert on floating point operations so I'm not really sure why this 
difference.

Original comment by thahlen@gmail.com on 15 Nov 2010 at 1:43

[GoogleCodeExporter]

Did you try to normalize your coordinate range around 0 before triangulation 
for better precision?

I'm closing this issue since I have found no bugs in the lib.

Original comment by thahlen@gmail.com on 21 Nov 2010 at 3:14

• Changed state: WontFix