Dead code and robustness

[heli...@gmail.com]

This does not affect the performance in any manner, but the following functions appear to be dead code:

    Point operator +( const Point &a, const Point &b )
    Point operator -( const Point &a, const Point &b )
    Point operator *( double s, const Point &a )
    Point operator !=( const Point &a, const Point &b )
    Point operator Cross( const Point &a, const Point &b )
    Point operator Cross( const Point &a, double s )
    Point operator Cross( double s, const Point &a )
    Sweep::HoleAngle( Node &node )
    SweepContext::RemoveFromMap( Triangle *triangle )
    SweepContext::RemoveNode( Node *node )
    Triangle::Clear()
    Triangle::ClearNeighbor( Triangle *triangle )
    Triangle::Contains( const Edge &e )
    Triangle::Legalize( Point &point )
    Triangle::MarkConstrainedEdge( Edge &edge )

that could be removed from the source code.

I also noticed that this project appears to have been derived from Poly2Tri and possibly PolygonTriangulator. This is a much nicer and cleaner implementation of the Domiter-Zalik sweep-line algorithm, but it does not implement Shewchuk's exact arithmetic for the Sweep::Orient2d and Sweep::InCircle functions for robustness. (Poly2Tri inexplicably does not implement Shewchuk's exact arithmetic for InCircle or set up the Intel CPU properly for exact arithmetic, while PolygonTriangulator effectively disables exact arithmetic by failing to initialize the exact arithmetic module).

It should not be difficult to implement exact arithmetic for Orient2d and InCircle, but I am not sure whether ::InScanArea would also have to rewritten.

[obi]

There are probably some redundant functions lingering since the development. I agree that unused functions are unnecessary :)

Those two projects you mention have zero relations to this library. It was just unfortunate that there existed a project called poly2tri prior to this library. But that is something I didn't get aware of until one or two years after this lib was released.

I had no prior knowledge of triangulation algorithms before writing this lib. I read the paper "Sweep-line algorithm for constrained Delaunay triangulation" by V. Domiter and and B. Zalik. The sweep line part of the algorithm is based on this paper. The constrained edge part is not based on any paper but an algorithm I came up with myself during development. The only documentation of it in existence is pretty much this picture FlipScan

The lib was written in Java but most ports is based on the stripped C++ version. So any low level cpu wizardry was never even considered during development. 

I have not been aware of "Shewchuk's exact arithmetic". The default epsilon for the lib is set to 1e-12 my guess is that any improvements exact arithmetic gives will not matter. It would require some floating point analysis of the code to determine the optimal epsilon and what improvements " Shewchuk's exact arithmetic" would give. The linked page even states that the code don't work on cpu's with "extended precision internal floating-point register"?

If you have any code and examples on improved robustness for poly2tri I would be happy to take a look at it.

[Mason Austin Green]

I would have to double check the code, but most all of those C++ functions are "utility" functions. If they aren't currently used, then they were at some point in development.

Any helpful contributions to the library are greatly appreciated.

--
You received this message because you are subscribed to the Google Groups "poly2tri" group.
To unsubscribe from this group and stop receiving emails from it, send an email to poly2tri+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[obi]

Looked around some on the web and found this:

https://github.com/govert/RobustGeometry.NET/tree/master/RobustGeometry/Predicates

I could easily port that to the Java branch. If there ever will be an Issue that can be solved by this I will consider adding it.