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

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2012-05-23 15:12:31

Andrii Sydorchuk wrote:

>I would like to keep voronoi_builder data structure as pure computational geometry algorithm implementation that is decoupled from the input and output.
>It's not responsibility of voronoi_builder to support data association, it should operate just with a geometry primitives by their coordinates, not concepts. 
>The concept customization is achieved using public static methods in voronoi.hpp header that retrieve coordinates of the input objects. 
>It is responsibility of the output object builder (voronoi_diagram_builder) to do mapping to the initial input set and voronoi_builder 
>can just provide enough information (like indexes in the previous post) to simplify this procedure.

I'm fine with it being an index.  This is how my own algorithms work.  For example the connectivity graph extraction and the map overlay are index based.  Below is the implementation of the interface for the general polygon connectivity extraction algorithm.  You construct the connectivity_extraction object, insert into it with its insert member function, which returns an int, which is the index of your inserted object.  The output data structure passed into the extract() function is required to be indexable with [] operators using the indexes returned.  In the case of voronoi diagram you can return an index for each site inserted into the voronoi builder and write that index to a member of the voronoi cell at the output.  If the user wants to index to a vector of altitude that is pretty easy, they just push the altitude back onto a vector at the time they insert the site into the voronoi builder.

namespace boost { namespace polygon {
  //ConnectivityExtraction computes the graph of connectivity between rectangle, polygon and
  //polygon set graph nodes where an edge is created whenever the geometry in two nodes overlap
  template <typename coordinate_type>
  class connectivity_extraction{
  private:
    typedef arbitrary_connectivity_extraction<coordinate_type, int> ce;
    ce ce_;
    unsigned int nodeCount_;
  public:
    inline connectivity_extraction() : ce_(), nodeCount_(0) {}
    inline connectivity_extraction(const connectivity_extraction& that) : ce_(that.ce_),
                                                                          nodeCount_(that.nodeCount_) {}
    inline connectivity_extraction& operator=(const connectivity_extraction& that) {
      ce_ = that.ce_;
      nodeCount_ = that.nodeCount_; {}
      return *this;
    }

    //insert a polygon set graph node, the value returned is the id of the graph node
    inline unsigned int insert(const polygon_set_data<coordinate_type>& ps) {
      ps.clean();
      ce_.populateTouchSetData(ps.begin(), ps.end(), nodeCount_);
      return nodeCount_++;
    }
    template <class GeoObjT>
    inline unsigned int insert(const GeoObjT& geoObj) {
      polygon_set_data<coordinate_type> ps;
      ps.insert(geoObj);
      return insert(ps);
    }

    //extract connectivity and store the edges in the graph
    //graph must be indexable by graph node id and the indexed value must be a std::set of
    //graph node id
    template <class GraphT>
    inline void extract(GraphT& graph) {
      ce_.execute(graph);
    }
  };
}}

Regards,
Luke