VoronoiDiagram sensitive to the order that lines are added

[opeongo]

I had a try at using the jopenvoronoi library. First off, thanks very much for your efforts at porting this to Java, this is greatly appreciated.

I used the library to insert a small sample of point and line sites into a VoronoiDiagram. The lines are non-intersecting. The insert_line_site method threw an exception with the following information:

Exception in thread "main" java.lang.AssertionError: c < 30000 at org.rogach.jopenvoronoi.VoronoiDiagram.repair_face(VoronoiDiagram.java:1614) at org.rogach.jopenvoronoi.VoronoiDiagram.insert_line_site(VoronoiDiagram.java:297) at org.rogach.jopenvoronoi.VoronoiDiagram.insert_line_site(VoronoiDiagram.java:118)

I rearranged the order of the line insertions so that the lines were inserted roughly in a top to bottom order, and then the process worked correctly.

Is this a know issue, that lines must be inserted in some particular order? If so, what are the rules? Or is this a question for the author of openvoronoi?

Here is a sample code that demonstrates the problem:

      //vertices
        System.err.println("add vertices");
        // line 1
        Vertex v1=vd.insert_point_site(new Point(0.4688321320388161, 0.5721630761892574));
        Vertex v2=vd.insert_point_site(new Point(0.5058348543325453, 0.6116864120228264));
        // line 2
        Vertex v3=vd.insert_point_site(new Point(0.4676644843944667, 0.14559440261470627));
        Vertex v4=vd.insert_point_site(new Point(0.5299451505909778, 0.22422772973181948));
        // line 3
        // v1
        Vertex v5=vd.insert_point_site(new Point(0.3990853987138186, 0.6415690863444968));
        Vertex v6=vd.insert_point_site(new Point(0.3729122932912645, 0.6480077124468139));
        Vertex v7=vd.insert_point_site(new Point(0.32779457738866813, 0.6143608857982717));
        Vertex v8=vd.insert_point_site(new Point(0.22693297450513644, 0.5030910125880271));
        // line 4
        // v4
        Vertex v9=vd.insert_point_site(new Point(0.6406656057326543, 0.3640239162472442));
        Vertex v10=vd.insert_point_site(new Point(0.6448875654993259, 0.389081247971103));
        Vertex v11=vd.insert_point_site(new Point(0.6330118434419065, 0.40878488410714986));
        // v1
        // line 5
        // v8
        Vertex v12=vd.insert_point_site(new Point(0.20962013060047913, 0.48303100856119374));
        // line 6
        // v12
        // v4
        // line 7
        // v12
        Vertex v13=vd.insert_point_site(new Point(0.14730087533143332, 0.41082760278911357));
        //lines
        // line 1
        System.err.println("Adding line 1");
        vd.insert_line_site(v1, v2);
        // line 2
        System.err.println("Adding line 2");
        vd.insert_line_site(v3, v4);
        // line 3
        System.err.println("Adding line 3");
        vd.insert_line_site(v1, v5);
        vd.insert_line_site(v5, v6);
        vd.insert_line_site(v6, v7);
        vd.insert_line_site(v7, v8);
        // line 4
        System.err.println("Adding line 4");
        vd.insert_line_site(v4, v9);
        vd.insert_line_site(v9, v10);
        vd.insert_line_site(v10, v11);
        vd.insert_line_site(v11, v1);
        // line 5
        System.err.println("Adding line 5");
        vd.insert_line_site(v8, v12);
        // line 6
        System.err.println("Adding line 6");
        vd.insert_line_site(v12, v4);
        // line 7
        System.err.println("Adding line 7");
        vd.insert_line_site(v12, v13);

The above code will trigger the error. After rearranging the insertion order by moving line 2 to the last insertion the algorithm works correctly.

Thanks,

Tom

[Rogach]

I minimized the error to the following configuration:

VoronoiDiagram vd = new VoronoiDiagram();
Vertex v3 = vd.insert_point_site(new Point(0.4676644843944667, 0.14559440261470627));
Vertex v4 = vd.insert_point_site(new Point(0.5299451505909778, 0.22422772973181948));
Vertex v9 = vd.insert_point_site(new Point(0.6406656057326543, 0.3640239162472442));
Vertex v12 = vd.insert_point_site(new Point(0.20962013060047913, 0.48303100856119374));
vd.insert_line_site(v3, v4);
vd.insert_line_site(v4, v9);
vd.insert_line_site(v12, v4);

You can immediately see the root cause here - v4 is shared between three lines. There wasn't much done on that currently (see this issue I opened upstream). It would be nice to have this use-case working, but I won't be able to devote sufficient time to this any time soon.

However, if you would be able to create a fix, I would gladly accept a pull request.

[opeongo]

I note that even in this minimized example that the diagram is computed correctly if the order of the line insertions is changed.

Do you have any suggestions on how to approach getting this case to work correctly? It will take me a while to get familiar with the code.

[Rogach]

Yes, that stuff is sensitive to the order. Also you may find that sometimes twiddling the coordinates by some small random value also solves some of these errors.

If you are going to dig into the code, the following two papers are essential - they will answer most of the questions right away:

Sugihara and Iri, (1992) "construction of the voronoi diagram for one 
million generators in single-precision arithmetic" 
http://dx.doi.org/10.1109/5.163412

Sugihara, Iri, Inagaki, Imai, (2000) "topology oriented implementation 
- an approach to robust geometric algorithms" 
http://dx.doi.org/10.1007/s004530010002

Code structure almost exactly follows the algorithm described in these papers.

As for approaching the case, I can't say much - I tried to fix this a while ago, but didn't have enough time. The basic idea would be to step through the algorithm, ensuring that internal state is sane. You will eventually find the place where the code makes some incorrect assumptions, and then it will be relatively easy to fix.

It would be easier to output algorithm stages to .svg files, so that you will be able to examine internal state in graphical format. You can use SvgOutput utility for that - it will work correctly even in the middle of the algorithm.