Incorrect error handling of invalid polygons.

[GoogleCodeExporter]

- What steps will reproduce the problem?

1. Take 4 points that would work in a clockwise direction, say 1,2,3,4.
2. Feed the CDT a polyline with the order 1,3,4,2 instead. We have 2 edges 
overlapping and therefore not a valid polygon.

No exception thrown or error handling.

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

Handle invalid polygons and throw exception or some way of knowing 
triangulation cannot be completed.



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

Downloaded source on Jan 19th. Windows 7

Original issue reported on code.google.com by turbovi...@gmail.com on 2 Feb 2011 at 7:55

[GoogleCodeExporter]

C++ version BTW.

Original comment by turbovi...@gmail.com on 2 Feb 2011 at 7:58

[GoogleCodeExporter]

Currently the lib assumes that the user has validated the input to be a simple 
polygon.

I'm looking into a way to just throw an exception in cases where constraints 
intersect during the triangulation.

Original comment by thahlen@gmail.com on 3 Feb 2011 at 9:15

• Changed state: Started

[GoogleCodeExporter]

I believe the C# port has some excellent pre-processing functions to help 
simplify the initialization/validation process. I'm in the process of updating 
the C++ code, and will incorporate into the library soon.

Original comment by mason.gr...@gmail.com on 5 Mar 2011 at 1:56

[GoogleCodeExporter]

Original comment by mason.gr...@gmail.com on 8 Mar 2011 at 2:29

• Changed state: Accepted

[GoogleCodeExporter]

Sorry I completely forgot about this issue, have been busy with other stuff.

My first brain storm on this would be the following:
To throw an exception when we have intersecting constraints this should be all 
we need to do. (Not tested)

When enforcing a constraint on the triangulation we trace the constraint thru 
current triangulation and flip triangles. We could easily test if one of the 
edges we cross already are a constrained edge and throw an exception.

I would implement this as follows:
In void Sweep::FlipEdgeEvent(..)
Adding this as first thing to do in that method

    if( t.getConstrainedEdgeAcross(p) )
    {
        throw new RuntimeException( "Input Error: Intersecting Constraints" );
    }

should be enough to catch all constraint intersections due to self intersecting 
input.

with a reservation for not having tested it yet :)

Original comment by thahlen@gmail.com on 8 Mar 2011 at 3:11

[GoogleCodeExporter]

There is no such method in the Triangle class as we speak.
The only 2 I can see are:

- bool GetConstrainedEdgeCCW(Point& p);
- bool GetConstrainedEdgeCW(Point& p);

Original comment by turbovi...@gmail.com on 8 Mar 2011 at 4:37

[GoogleCodeExporter]

Oh. sorry. I'm working with the Java version so didn't know that.

    public boolean getConstrainedEdgeAcross( TriangulationPoint p )
    {
        if( p == points[0] )
        {
            return cEdge[0];
        }
        else if( p == points[1] )
        {
            return cEdge[1];
        }
        return cEdge[2];
    }

Original comment by thahlen@gmail.com on 8 Mar 2011 at 4:43

[GoogleCodeExporter]

Seems to work like a charm, thanks!

Original comment by turbovi...@gmail.com on 8 Mar 2011 at 7:11

[GoogleCodeExporter]

Original comment by mason.gr...@gmail.com on 10 Mar 2011 at 7:04

• Changed state: Done