EdgeEvent - Point on constrained edge not supported yet about poly2tri HOT 12 CLOSED

This is not a defect!! Just a request for implementation

Actually I have implemented support for most of these cases in the Java code. 
If you are using floating point data these cases should be really rare.

So what are you doing? This should never be an issue when triangulating 
polygons since the edges of the polygon is the constraints. If you have this 
problem with polygons then the polygon would not be simple but self 
intersecting.

If you got an example I could test, please just dump some point and constraints 
in the form:
x,y,z
x,y,z
.
.

Hi, 
Ok I am using the C# port, where there are commented TODO's where these
exceptions are thrown.

I did notice that I had some points very close by, and when I filtered these
the issue went away.

Is it just close almost coincidential points that can cause this? If so I
can pre-filter to make sure.

If you have a set of points then you just pick two points at random to create a 
constrained edge. There is always a tiny chance that this edge might pass thru 
another point in this set. 

The chance that this edge will pass thru another point is pretty low when 
dealing with float coordinates but if you point data is somewhat structured. eg 
several points have the exact same x or y coordinates the likely hood that this 
might happen gets bigger. In the java version I have implemented a way to split 
the constraint edge in to several edges when these intersections happen. 

If you have two points really close (almost coincidental) I guess that a 
constraint edge from one of these point might consider the other point as 
intersecting the constrained edge. So filtering almost coincidental points will 
probably solve most of you problems. But as described above there are other 
ways the edges can intersect points.

Here is a set of points that does cause a failure.
It is a large polygon (the boundary of South Africa) that is being rendered as 
a filled polygon in my application.

Please let me know the results

Any results from the test set above?

Sorry have been busy with another project :).

I ran the dataset on the current Java release and the Triangulation in itself 
works fine. This is 10 times more polygon edges than I have every tried to 
triangulate before so the recursive meshClean will result in a stack overflow 
:X. 

This is the triagulation output without removing "external" triangles:
http://img530.imageshack.us/img530/2923/capture1291208037953.png

I use the DataLoader in the java example base to load the polygon this will 
also translate and rescale the polygon points around 0,0. Also had to change 
the loader to support Double instead of Float due to the precision in your 
dataset.

I totally understand!!!

Thanks.

Yes I did a quick non recursive version of the meshclean to avoid the stack 
overflow!

The output looks perfect. So I think the Java version is totally fine, but we 
need to get the C# version to be in step with it. I have actually 'Genericized' 
the C# version so I can get back my original points when triangulating surfaces 
in 3D. I have a great interest in getting the C# version working as the Java 
one does.
Will there be an update to the C# version? I am willingto help in any way I can 
if that helps!, since I really like this library. It has good performance in 
the managed environmnent. 

Ah. 

Would you like to share the your meshClean, could use one non recursive version 
:).

First just try to normalize the coordinates to be within the range +-10 could 
improve the precision during computations a little bit. But your coordinates 
seems to use the whole range pretty good already.

There is also a EPSILON=1e-12 in the triangulation util. You could try to set 
it to EPSILON=1e-13 or even smaller. 

Since this started as more of a hobby project there is no floating point 
precision analysis done on the algorithm so I just picked a reasonably EPSILON 
that would give a wide margin of robustness. Since your coordinates are of such 
high precision lowering the epsilon might help.

Here is a nonrecursive version of MeshClean:

    public void MeshClean( DelaunayTriangle<Tag> triangle ) {
        MeshCleanReqNoStack(triangle);
    }

        /// <summary>
        /// Clean mesh without chewing the stack.
        /// Derek Diamond 25 Nov 2010
        /// </summary>
        /// <param name="triangle"></param>
        private void MeshCleanReqNoStack( DelaunayTriangle<Tag> triangle ) {
            var stack = new System.Collections.Generic.Stack<DelaunayTriangle<Tag>>();

            stack.Push(triangle);

            while (stack.Count > 0)
            {
                var t = stack.Pop();

                if (t != null && !t.IsInterior)
                {
                    t.IsInterior = true;
                    Triangulatable.AddTriangle(t);

                    for (int i = 0; i < 3; i++)
                    {
                        if (!t.EdgeIsConstrained[i])
                        {
                            stack.Push(t.Neighbors[i]);
                        }
                    }
                }
            }
        }

Thnx :). 

Wierd that it didn't occur to me to replace the recursive function and the call 
stack with an ordinary stack, so simple!

If there is any direct issues with the C# version you might try

https://github.com/MaulingMonkey/poly2tri-cs/issues

I'm closing this now since there is nothing to fix in the java codebase which 
is the base of all other versions.