EdgeEvent - Point on constrained edge not supported yet

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Input data has constraints intersecting points of data not at endpoints

What is the expected output? What do you see instead?
I know its a TODO, but what can be done to handle this :)
'Exception: EdgeEvent - Point on constrained edge not supported yet'

What version of the product are you using? On what operating system?
Latest C# version

Please provide any additional information below.
The library works great by the way! So kudos to the developers. I would just 
love to not get the above exception on our users data.

Original issue reported on code.google.com by de...@primethought.biz on 22 Nov 2010 at 10:44

[GoogleCodeExporter]

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

Original comment by de...@primethought.biz on 22 Nov 2010 at 10:45

[GoogleCodeExporter]

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
.
.

Original comment by thahlen@gmail.com on 22 Nov 2010 at 11:26

[GoogleCodeExporter]

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.

Original comment by de...@primethought.biz on 22 Nov 2010 at 12:22

[GoogleCodeExporter]

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.

Original comment by thahlen@gmail.com on 22 Nov 2010 at 1:58

[GoogleCodeExporter]

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

Original comment by de...@primethought.biz on 24 Nov 2010 at 12:58

Attachments:

• triangulationbug.txt

[GoogleCodeExporter]

Any results from the test set above?

Original comment by de...@primethought.biz on 30 Nov 2010 at 2:39

[GoogleCodeExporter]

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.

Original comment by thahlen@gmail.com on 1 Dec 2010 at 1:09

[GoogleCodeExporter]

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. 

Original comment by de...@primethought.biz on 1 Dec 2010 at 1:34

[GoogleCodeExporter]

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.

Original comment by thahlen@gmail.com on 1 Dec 2010 at 2:02

[GoogleCodeExporter]

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]);
                        }
                    }
                }
            }
        }

Original comment by de...@primethought.biz on 1 Dec 2010 at 2:29

[GoogleCodeExporter]

Thnx :). 

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

Original comment by thahlen@gmail.com on 1 Dec 2010 at 6:05

[GoogleCodeExporter]

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. 

Original comment by thahlen@gmail.com on 15 Dec 2010 at 9:01

• Changed state: Done