find_separator_target() FATAL ERROR

[Rogach]

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:

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]

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]

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]

@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]

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 [email protected] 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
#18 (comment).

[Rogach]

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:

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]

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]

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 [email protected] 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
#18 (comment).

[Rogach]

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]

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]

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]

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 [email protected] 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
#18 (comment).

[Rogach]

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]

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 [email protected] 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
#18 (comment).