find_separator_target() FATAL ERROR

Rogach commented 9 years ago

The following sequence of points gives errors:

-0.2567719874411157,-0.4983049800651602
0.12205285479992212,-0.640371712930281
-0.25972854724944455,-0.5143879072702902
-0.34168692840153536,-0.6418861147966213
-0.5288215108461576,0.18480346369654843
-0.35263585687204546,-0.50735692278175
-0.4821854389417177,0.46463421861462373

Here's the code and output: https://gist.github.com/Rogach/29cf52b69f40cc941fc6

The image of the polygon:

failure

The polygon looks relatively harmless, and I have no idea what the problem may be.

The error is relatively rare with smaller random polygons, but happens often with bigger polygons -it took ~300 random polygons with 4096 points to generate this error, ~30000 with 1024 points, and several million to find a case with 32 points - which I then simplified to the one in above image. (I used my own random polygon generator, not the one used in tests, so it may not happen in your tests)

aewallin commented 9 years ago

Thanks for reporting this. I've added a python example "polygon_2015-02-09.py" that shows this error. Is your polygon generator available under GPL - it could be included into openvoronoi?

Rogach commented 9 years ago

It's written in java, and I'm not comfortable with C++ enough to port it back. Here's the code: https://gist.github.com/Rogach/a6c75cd90221c09e0f9d

It's part of my port of openvoronoi to java - it's almost finished, and I'll upload it to github soon (under GPL 3, of course).

Rogach commented 9 years ago

@aewallin - just in case, want to notify you that I released port of openvoronoi to java, https://github.com/Rogach/jopenvoronoi. Thank you for all your work on this amazing library!

aewallin commented 9 years ago

Thanks for the link. I will include it in the readme for my c++ openvoronoi. Great work with the port - hope you found my c++ effort useful. If you find some bugs, make enhancements, or work on supporting circular arcs, please let me know!

On Wed, Feb 11, 2015 at 8:11 PM, Rogach notifications@github.com wrote:

@aewallin https://github.com/aewallin - just in case, want to notify you that I released port of openvoronoi to java, https://github.com/Rogach/jopenvoronoi. Thank you for all your work on this amazing library!

— Reply to this email directly or view it on GitHub https://github.com/aewallin/openvoronoi/issues/18#issuecomment-73932201.

Rogach commented 9 years ago

I minimized the bug, and that's what I've found:

In the following image the state after adding IN-NEW-OUT vertices is shown: wrong_split As you can see, (-0.305,-0.495) is almost exactly on the about-to-be added separator edge.

When trying to position the vertex on (-0.318,-0.503)--(-0.305,-0.495) edge, ALTSEP solver fails - (-0.305,-0.495) is just a bit bigger than t_max, and solution is rejected. Increasing eps in t_filter from 1e-9 to 1e-7 solves the problem.

But I suspect that playing with that eps will result in even more problems? Can you add some insight on this?

Rogach commented 9 years ago

I managed to fix this issue, others that I have opened against openvoronoi and lots of others in java port. But I feel that most of my changes are controversial, focused on special cases and "hacky", so I'm not sure that you will accept them as-is. Here's the breakdown of significant changes:

different handling of situation when no immediately acceptable solutions are found. Proposed solution tries to use dist_error and t range error to select best solution from existing ones, with some special cases for parallel lines. This approach avoids calls to desperate solution(), which tends to give completely wrong solutions. (code)
special handling for positioning a vertex between two linesites and their mutual poinsite - just select the pointsite location, and compute k properly from the other edge end - to avoid having wrong side solution selected due to numerical error. It's the common situation with polygons, so it could make sense to special-case it. (code)
topological determination of k3 in separator vertex positioning, instead of trying both solutions. This also helps with trimming wrong side solutions due to numerical errors. Here I exploited the fact that we always traverse vertices around the face in the same direction, thus we can guess k3 simply by checking whenever edge source vertex is IN or OUT. (code)
increased delta threshold in Edge.set_ll_parameters, since edge.point seems to be very unstable for almost parallel lines - resulting in wrong solutions selected in vertex positioner.

I'll need your permission before I can start backporting this stuff into openvoronoi. Also, I would greatly appreciate any insight on better solutions to aforementioned problems.

aewallin commented 9 years ago

Hi, thanks for your contributions and notes. I will hopefully have time to review over the weekend. I would encourage you to find more failure-cases (and post them as issues), and if possible port your polygon-generator (which seems good at finding problematic cases!) to either python or c++ - I may do that myself at some point also if I find time. Another option would be to store test-cases in text-files, so they can be used as tests for both openvoronoi and Jopenvoronoi. I could contribute with text-files for the freetype fonts I have been using as tests. zipped text files makes sense for large texts (Java and Python have built-in support for zip or gzip?)

Have you read the papers by Held on his VRONI implementation? (drop me an email if you don't have access to the PDFs). The overall philosophy is that the logic of the algorithm that constructs the topology (i.e. graph) of the diagram should never fail. For the numerical calculations (i.e. where to place new vertices etc) we accept that there are errors, and just do the best we can. For the numerical algorithms a multi-step approach is possible, where a faster simple algorithm is used whenever it works, and we fall back on a slower algorithm for 'hard' cases. For really impossible cases there can be a 'desperate'-mode and perhaps a warning to the user. This is the philosophy, but I know it isn't captured very clearly in the openvoronoi codebase. Any refactoring to make the distinction between the logic/topology side of things and the numerical algorithms clearer would be welcome. Similarly the multi-step approach to numerical calculations isn't very well documented or clear in the codebase.

Anders

On Wed, Feb 25, 2015 at 7:53 PM, Rogach notifications@github.com wrote:

I managed to fix this issue, others that I have opened against openvoronoi and lots of others in java port. But I feel that most of my changes are controversial, focused on special cases and "hacky", so I'm not sure that you will accept them as-is. Here's the breakdown of significant changes:

different handling of situation when no immediately acceptable solutions are found. Proposed solution tries to use dist_error and t range error to select best solution from existing ones, with some special cases for parallel lines. This approach avoids calls to desperate solution(), which tends to give completely wrong solutions. (code https://github.com/Rogach/jopenvoronoi/blob/master/src/main/java/org/rogach/jopenvoronoi/VertexPositioner.java#L182 )

special handling for positioning a vertex between two linesites and their mutual poinsite - just select the pointsite location, and compute k properly from the other edge end - to avoid having wrong side solution selected due to numerical error. It's the common situation with polygons, so it could make sense to special-case it. (code https://github.com/Rogach/jopenvoronoi/blob/master/src/main/java/org/rogach/jopenvoronoi/VertexPositioner.java#L85 )

topological determination of k3 in separator vertex positioning, instead of trying both solutions. This also helps with trimming wrong side solutions due to numerical errors. Here I exploited the fact that we always traverse vertices around the face in the same direction, thus we can guess k3 simply by checking whenever edge source vertex is IN or OUT. (code https://github.com/Rogach/jopenvoronoi/blob/master/src/main/java/org/rogach/jopenvoronoi/VertexPositioner.java#L122 )

increased delta threshold in Edge.set_ll_parameters https://github.com/Rogach/jopenvoronoi/blob/master/src/main/java/org/rogach/jopenvoronoi/Edge.java#L250, since edge.point seems to be very unstable for almost parallel lines - resulting in wrong solutions selected in vertex positioner.

I'll need your permission before I can start backporting this stuff into openvoronoi. Also, I would greatly appreciate any insight on better solutions to aforementioned problems.

— Reply to this email directly or view it on GitHub https://github.com/aewallin/openvoronoi/issues/18#issuecomment-76017008.

Rogach commented 9 years ago

Hi!

About tests - I do have a simple text format I used for test-case storage. First goes list of points in "%f,%f" form, then goes list of segments in "%f,%f->%f,%f" form (except that I used Java's %s specifier, that correctly prints doubles to the last significant decimal place, while %f for some reason only prints 6 decimal places). Yes, zipping is nice, Java and Python definitely have readily available facilities for it.

Yes, Sugihara's and Held's papers were the real eye-openers for me. My changes were primarily motivated by the fact that in corner cases current implementation fails to provide any solution due to fatal errors after some vertices were positioned extremely incorrectly. The biggest heat comes from the fact that k values are often incorrectly determined - and that throws separator positioning off-track. To rephrase, we get k values as a result of numeric calculations, but then use them in topology calculations, which is bound to create problems. And I don't see an easy way to get rid of those k values.

Some praise is in order - while I read quite a bit of source code of different projects, yours is clearly outstanding - I consider it one of the best examples of code structuring. As for the logic/topology, it is presented in the very readable way, almost exactly as it was described in the papers - I don't think that it can be improved further. And multi-step approach to numerical calculations is verbatim right there in VertexPositioner.position() - my changes actually only obscured the intent.

Rogach commented 9 years ago

I'll see what I can do about polygon generator.

There are now several interesting things I created to track down bugs in the code:

random polygon, simple random polygon that uses space partitioning to create nice polygons in n*log(n) time.
"random labyrinth", another facility to test various corner cases that arise when working with polygons with lots of perpendicular or parallel edges.
lindenmayer curves - also helps with edge cases. I implemented Moore and Gosper curves.
and failure minimizer, which allows to quickly minimize found test cases for debugging.

I don't like C++, but I'll try to build openvoronoi's python bindings on my machine, after that it shouldn't be too hard to port above stuff.

Rogach commented 9 years ago

One last note: here's the java reference implementation for aforementioned simple text format (with optional gzip support), the relevant parts are write and read methods.

aewallin commented 9 years ago

A common format for text-input is a good idea. It seems your format repeats the geometry twice. I would suggest separating geometry from topology, i.e. first vertices in some format: id (xcoord,ycoord) ... 42 (1.234, 3.1415) 43 (7.89, 9.123) ... then topology using the integer ids: 42 43 (this could mean line-site from vertex 42 to vertex 43)

We obviously sometimes want 'islands' inside an outer polygon - I'm not sure if the text-file format needs something additional for this(e.g. which line-segments make up a polygon), or if the above simple format is sufficient. Polygons should have an inside and an outside - but this can be handled with the direction of the segments, e.g. a rule that the inside of a polygon is always to the left when traveling along a line-segment from source to target vertex.

For the future I would also like to represent circular arcs somehow. These need a start and an end-vertex, and then additional data EITHER (radius, cw/ccw flag), OR (centerpoint, cw/ccw flag). I haven't thought deeply about the difference between these formats (both are used in e.g. G-code for cnc machines) - there are probably advantages and disadvantages with both approaches.

Hopefully I can find time to cook up a text-file format and some test-cases over the weekend. It would be nice to have automated tests for both openvoronoi and Jopenvoronoi with the same input data.

On Thu, Feb 26, 2015 at 10:51 AM, Rogach notifications@github.com wrote:

One last note: here's https://github.com/Rogach/jopenvoronoi/blob/master/src/main/java/org/rogach/jopenvoronoi/EuclideanInput.java the java reference implementation for aforementioned simple text format (with optional gzip support), the relevant parts are write https://github.com/Rogach/jopenvoronoi/blob/master/src/main/java/org/rogach/jopenvoronoi/EuclideanInput.java#L115 and read https://github.com/Rogach/jopenvoronoi/blob/master/src/main/java/org/rogach/jopenvoronoi/EuclideanInput.java#L140 methods.

— Reply to this email directly or view it on GitHub https://github.com/aewallin/openvoronoi/issues/18#issuecomment-76142205.

Rogach commented 9 years ago

Repeating geometry twice makes implementation a bit simpler (all you need is a hasmap on the read side), but that's extremely small matter, so let's use vertex ids.

Why do we need to bake particular geometric structure into the text format? From mathematical standpoint, polygon is just a collection of segments, but not every collection of segments is a polygon - and since voronoi diagram is defined for any collection of segments, it doesn't seem right to restrict us to polygons. That is, inside/outside doesn't matter when generating voronoi diagram, or am I forgetting something here?

Yes, having shared test base is going to be awesome.

aewallin commented 9 years ago

many downstream algorithms such as medial-axis and offset generation require a sense of "inside" and "outside". If it's not specified by the user then a separate step that figures out what is inside and what is outside is required. Anyway I agree it does not have to be part of the text-file specification, some examples (such as the font geometry) just use a convention where e.g. the outer boundary is specified CW and islands within are specified CCW. I should add that the text-file should have optional comments at the top. For example lines starting with "#" could be treated as comments.

I hope to work on this a bit in the evening.

On Fri, Feb 27, 2015 at 6:38 PM, Rogach notifications@github.com wrote:

Repeating geometry twice makes implementation a bit simpler (all you need is a hasmap on the read side), but that's extremely small matter, so let's use vertex ids.

Why do we need to bake particular geometric structure into the text format? From mathematical standpoint, polygon is just a collection of segments, but not every collection of segments is a polygon - and since voronoi diagram is defined for any collection of segments, it doesn't seem right to restrict us to polygons. That is, inside/outside doesn't matter when generating voronoi diagram, or am I forgetting something here?

Yes, having shared test base is going to be awesome.

— Reply to this email directly or view it on GitHub https://github.com/aewallin/openvoronoi/issues/18#issuecomment-76425176.

aewallin / openvoronoi

find_separator_target() FATAL ERROR #18