Description
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