Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2012-07-04 14:28:07

By this point it seems that the only concern about Voronoi implementation
is the Voronoi diagram data structure design.
I had enough time to read the whole thread again and here is my vision of
how the main issues should be resolved:

============================
1) [MAIN ISSUE] Decoupling input data from the output.
I think I've managed to come up with a pretty nice solution:
a) voronoi_diagram would not contain coordinates of the input geometries,
that means that voronoi_cell data structure will represent a cell, not
geometry (point or segment) inside it.
b) according to the above, new voronoi_cell data stucture will look like:
struct voronoi_cell {
  // Specifies type of the geometry that forms the cell.
  CellSourceCategory source_category;
  // Unique id of the source object that is inside the cell.
  size_t geometry_id;
  voronoi_edge* incident_edge;
  size_t color;
};

enum CellSourceCategory {
  POINT = 0,
    SINGLE_POINT = 0, // if divided by 4 falls into POINT root category.
    FIRST_POINT = 1, // if divided by 4 falls into POINT root category.
    SECOND_POINT = 2, // if divided by 4 falls into POINT root category.

  SEGMENT = 1,
    INITIAL_SEGMENT = 4, // if divided by 4 falls into SEGMENT root
category.
    OPPOSITE_SEGMENT = 5, // if divided by falls into SEGMENT root category.
};

Note: as one may admit CellSourceCategory requires just 3 bits, thus it
could be packed with geometry_id member.

c) CellSourceCategory is required to encapsulate edge geometries topology
within the voronoi diagram data structure.
E.g. checking whether the edge is curved or linear, primary or not without
accessing input geometries list.

d) geometry id corresponds to the index of the site (point, segment)
retrieved from the voronoi_builder during insertion.
It is given sequentially starting from 0. Thus will correspond to the input
geometry index within a container if inserting elements sequentially.
Note: both segment endpoints and segment itself will have the same
geometry_id, while all of them have dedicated voronoi cell in the output.
We identify them using CellSourceCategory.

e) voronoi_utils interface will be changed as voronoi diagram primitives
don't contain information about input geometries coordinates.
e.g. to sample curved voronoi_edge we will also need to pass random access
container holding input geometries in the order they were passed to the
voronoi builder.

============================
2) Each of the primitive types has size_t color member. Which could be
basically used to associate data with primitives or execute graph
algorithms.
Considering the new design of the voronoi_cell this produces 9/50 ~= 20%
(details could be provided on request) memory overhead.
Compiler directives could be used to enable/disable this data member if
approved by the community.

Note:
Please keep in mind that users are always free to implement their own
primitives types.
The current voronoi diagram topology implementation is one of the most
compact, considering the fact that it gives complete freedom on voronoi
graph traversal.
Thus I don't think that 20% overhead is significant.

============================
3) [QUESTIONABLE ISSUE] Voronoi diagram builder.
The main point of this build class is encapsulation of the voronoi diagram
construction methods.
At the moment it is implemented as part of the voronoi diagram structure
(Java style) and just redirects construction calls to the voronoi_diagram
private routines.
If required could be implemented as a friend class of the voronoi_diagram.

As always comments are welcome (especially on the solution of the first
issue).

Thanks,
Andrii