error with continue triangulation

[Kate Yan]

I tried to triangulate a polygon with some holes. If I call the triangulating method after I have added all holes, the algorithm is fine. But If I triangulate the polygon after I add one hole, and then triangulate it again with another holed added, there are the following errors:

Apr 10, 2014 9:34:18 PM org.poly2tri.triangulation.delaunay.DelaunayTriangle pointCCW

SEVERE: point location error

Exception in thread "main" java.lang.RuntimeException: [FIXME] point location error

at org.poly2tri.triangulation.delaunay.DelaunayTriangle.pointCCW(DelaunayTriangle.java:224)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.edgeEvent(DTSweep.java:492)

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.edgeEvent(DTSweep.java:320)

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

at org.poly2tri.triangulation.delaunay.sweep.DTSweep.triangulate(DTSweep.java:68)

at org.poly2tri.Poly2Tri.triangulate(Poly2Tri.java:96)

at org.poly2tri.Poly2Tri.triangulate(Poly2Tri.java:88)

at org.poly2tri.Poly2Tri.triangulate(Poly2Tri.java:63)

at test.Main.testErrorCase(Main.java:193)

at test.Main.main(Main.java:16)

I remember I have seen that this package can deal with re-triangulation. Could you please give me some help? Thank you. The code I wrote is as below.

public static void testErrorCase() {

List<PolygonPoint> points = new ArrayList<PolygonPoint>();

PolygonPoint p1 = new PolygonPoint(0.0, 0.0);

PolygonPoint p2 = new PolygonPoint(1000.0, 0.0);

PolygonPoint p3 = new PolygonPoint(1000.0, 1000.0);

PolygonPoint p4 = new PolygonPoint(0.0, 1000.0);

points.add(p1);

points.add(p2);

points.add(p3);

points.add(p4);

Polygon polygon = new Polygon(points);

//

PolygonPoint q1;

PolygonPoint q2;

PolygonPoint q3;

PolygonPoint q4;

PolygonPoint q5;

PolygonPoint q6;

Polygon hole;

//

List<PolygonPoint> pointsForHole1 = new ArrayList<PolygonPoint>();

q1 = new PolygonPoint(244.8906951930522, 784.9009127526291);

q2 = new PolygonPoint(417.27284706091024, 633.4895106359271);

q3 = new PolygonPoint(437.80056771258273, 629.3750254650489);

q4 = new PolygonPoint(716.6601402050248, 813.2107179582445);

q5 = new PolygonPoint(690.2401226027848, 1000.0);

q6 = new PolygonPoint(262.25990550668615, 1000.0);

pointsForHole1.add(q1);

pointsForHole1.add(q2);

pointsForHole1.add(q3);

pointsForHole1.add(q4);

pointsForHole1.add(q5);

pointsForHole1.add(q6);

hole = new Polygon(pointsForHole1);

polygon.addHole(hole);

                // If I comment the line below, it will be fine.

Poly2Tri.triangulate(polygon);

//

List<PolygonPoint> pointsForHole2 = new ArrayList<PolygonPoint>();

q1 = new PolygonPoint(245.22551393964045, 0.0);

q2 = new PolygonPoint(802.2744579508885, 0.0);

q3 = new PolygonPoint(828.2006326705192, 150.89951487587393);

q4 = new PolygonPoint(571.2499578357936, 376.5914529912652);

q5 = new PolygonPoint(218.81850471369796, 144.25415267198147);

pointsForHole2.add(q1);

pointsForHole2.add(q2);

pointsForHole2.add(q3);

pointsForHole2.add(q4);

pointsForHole2.add(q5);

hole = new Polygon(pointsForHole2);

polygon.addHole(hole);

Poly2Tri.triangulate(polygon);

}

[zzzzrrr]

Yes, this is expected behavior.

Please read the basic instructions:
http://code.google.com/p/poly2tri/wiki/README?ts=1328629791&updated=README

[Kate Yan]

I don't quite understand. Did the error caused by conflicting with 

• Interior holes must not touch other holes, nor touch the polyline boundary

But I think the problem is related to re-triangulation with new holes. Because if I only triangulate once with those two holes, it will be fine. But if I triangulate twice, there is an error.

I referred to this question: dynamic triangulation (https://groups.google.com/forum/#!topic/poly2tri/yqoiwJAYS44). You said "Just add the new points to your original point-set, and re-triangulate." So I think maybe I can just add new holes, and re-triangulate it. :P

[zzzzrrr]

In that context, "re-triangulate" meant "try-again" with Steiner points.

There is no error: poly2tri is not intended to triangulate your points more than once.

Regards,
Mason

[obi]

I never considered using poly2tri that way. Polygon is a datastructure you create for usage during a triangulation and there is a list of constraints kept in the TriangulationPoint used in the triangulation. 

But just looking at it. There might be a way to support retriangulation when adding more holes **if they for sure don't intersect or touch**.

It would be to add a method clearEdges() in TriangulationPoint, e.g. a way to empty this array after a previous triangulation.

Then in Polygon.prepareTriangulation method add a 

_point.clearEdges in each of the three loops that loop over outer edge points, hole points and steiner points.

This would be my first try. Still you don't have an api to remove holes from Polygon so if all you can is add holes and the usefulness might be pretty limited.

-Thomas

[Kate Yan]

Thank you. I understand now.

--
You received this message because you are subscribed to a topic in the Google Groups "poly2tri" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/poly2tri/LYWNR1uOIt4/unsubscribe.
To unsubscribe from this group and all its topics, send an email to poly2tri+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Kate Yan]

Thank you. I decide not to revise the Poly2Tri source code. I changed my code as follows. When I need to re-triangulation, I generate a new polygon, and put all holes, including the newly one, into the polygon, and triangulate this polygon.