Geometry Boost List: Re: [geometry] Voronoi triangulation GSOC

From: Tinko Bartels (tinkobartels_at_[hidden])
Date: 2020-05-30 09:58:12

Hi Brook,

 Do you have any docs built anywhere, or just what is in the repo?

As of now, only what is in the repo. I also expect that changes to
interfaces may be required during the review of my PR. I have not abandoned
the project, though, so after I have more confidence in the interface and
more time than during the current GSoC20, I want to add a proper
documentation.

Can any point type be used?  Must it have floating point coordinates?
> (Boost.Polygon uses integer types, hence the question.)
>

Not any point type. The algorithm, in its current implementation, only
works for 2D, cartesian coordinates.

It may be possible to extend the idea to spherical coordinates. I
implemented a modified version of the s-hull algorithm, you can find the
original algorithm here: http://s-hull.org/. I have been thinking about
other coordinate systems. Intuitively, it would seem that you could port it
to spherical coordinate systems by sorting the points by latitude, add
virtual points on both poles, using one of the poles as seed point and do a
sweep with a moving circle of equal latitude (corresponding to the circle
sweep with an increasing circle of equal distance in the cartesian case).
In the end, you'd have to remove the virtual pole points, which would leave
a (I think) convex hole at both poles that (I think) could be trivially
triangulated via fan triangulation. However, that is just a guess, my
understanding of (and hence my intuition on) spherical geometry is too
limited make confident statements about that off the top of my head. I
might have time to explore that idea later (maybe after this year's GSoC).
To make the triangulation Delaunay we would also need an incircle-strategy
for spherical coordinates and the robustness of that whole enterprise would
depend on the robustness of the spherical side- and incircle-strategies. At
the moment I have no knowledge about whether there are formulas for robust
implementation of those strategies based on spherical coordinates.

With regard to coordinate number types: It should work with integer and
floating point coordinates. Making it robust against rounding errors for
floating point coordinates was a big part of the project. It is not robust
against overflow or underflow errors with float-coordinates (that may be an
issue with coordinates with absolute values larger than ~1e150 or smaller
than about ~1e-145, I think). With integer coordinates, there are no
robustness-issues anyway with regard to rounding or underflow. There are
some calculations during the construction in which there may be conversions
to floating point types of interim results that may induce rounding errors.
I am not sure if that could result in robustness issues with integer
coordinates. There may be robustness issues with integer coordinates with
regard to overflow, if the magnitude of the input coordinates is about as
large or larger than the square of the maximum representable integer of the
calculation type.

By the way, the robust side strategy has been merged into the current
develop-tree as an extension:
https://github.com/boostorg/geometry/tree/develop/include/boost/geometry/extensions/triangulation/strategies/cartesian

Do you have a good way to do that, i.e., to turn the infinitely large
> “edge” polygons into finitely sized ones whose outer edges create a box?
>

I should mention at this point, that anything with regard to Voronoi meshes
was not my main focus when I worked on the project. It was grafted onto the
Delaunay Triangulation data-structure exploiting the dual relationship
between those two. My guess (with my current understanding of the design
philosophies of Boost.Geometry) for the proper way to do this in the
context of Boost.Geometry would be to have some extension for the
ring-concept that allows boundary edges to go to infinity and then to
implement an intersection algorithm for that with envelopes. However, that
is not part of my PR and not something I planned for or achieved during
GSoC 2019. Also this would just be my proposal, the authors of
Boost.Geometry would be more qualified to make judgements on the proper
design of this feature.

Mathematically, I think you would do it like this:
Let's assume a non-degenerate case (at least three points in the input that
do not all lie on a shared line). Consider an infinite edge. It starts at
some finite point p that is a node of the voronoi mesh. p must be the
center of the circumcircle of some triangle p1, p2, p3 in the dual Delaunay
triangulation. The infinite edge is then the edge in the mesh between two
cells that corresponds to two of those points, let's say p1 and p2. The
direction d of the infinite edge is then orthogonal to the line [p1, p2]
and points away from p3, I think. The direction d as a point lies in some
quadrant of the coordinate system (depending on the signs of its x and y
coordinates), let's say I.

Via the quadrant you know what edge of the envelope the infinite edge can
cross, in the case of quadrant I it would be the top and the right edge of
the envelope. Find the intersection point p_i of the ray starting at p with
direction d with one of those two edges of the envelope. Do the same for
the other infinite edge of the voronoi cell. Add those two intersection
points and the boundary of the envelope and, if applicable, the 1 or 2
corners (I think) of the envelope that lie between them to the ring, in
proper order with regard to the orientation. The resulting ring should be
the infinite cell intersected with the envelope.

Here's a rough sketch: https://ibb.co/zPZNRcq (based on this image:
https://de.wikipedia.org/wiki/Datei:Voronoi-Delaunay.svg)

By the way, I also found the uniform_point_distribution among the other
> pull requests, but haven’t tried it yet.  Sorry to bother you about that
> one, although I’m still interested in its integration status.
>

No need to be sorry, I am happy to see that there is interest in this work.
Those features are also under review:
https://github.com/boostorg/geometry/pull/618 . During the GSoC19 I got
some things wrong with regard to the design philosophies of Boost.Geometry
but I reorganized a lot of the code since (after many helpful comments
during the review). So I would say that the review has further progressed
there and if future reviews consider my changes to be correct then this
feature may be closer to integration than the triangulation code. You can
find the current state on this branch:
https://github.com/BoostGSoC19/geometry/tree/feature/uniform_point_distribution
.

Thanks again for working on this.
>

Thanks for your interest.

Cheers,
Tinko