Boost-Geometry-Utils

 view release on metacpan or  search on metacpan

src/medial_axis.hpp  view on Meta::CPAN

      color_(0) {
    if (is_linear)
      color_ |= BIT_IS_LINEAR;
    if (is_primary)
      color_ |= BIT_IS_PRIMARY;
  }

  medial_axis_cell_type* cell() { return cell_; }
  const medial_axis_cell_type* cell() const { return cell_; }
  void cell(medial_axis_cell_type* c) { cell_ = c; }

  medial_axis_vertex_type* vertex0() { return vertex_; }
  const medial_axis_vertex_type* vertex0() const { return vertex_; }
  void vertex0(medial_axis_vertex_type* v) { vertex_ = v; }

  medial_axis_vertex_type* vertex1() { return twin_->vertex0(); }
  const medial_axis_vertex_type* vertex1() const { return twin_->vertex0(); }

  medial_axis_edge_type* twin() { return twin_; }
  const medial_axis_edge_type* twin() const { return twin_; }
  void twin(medial_axis_edge_type* e) { twin_ = e; }

  medial_axis_edge_type* next() { return next_; }
  const medial_axis_edge_type* next() const { return next_; }
  void next(medial_axis_edge_type* e) { next_ = e; }

  medial_axis_edge_type* prev() { return prev_; }
  const medial_axis_edge_type* prev() const { return prev_; }
  void prev(medial_axis_edge_type* e) { prev_ = e; }

  // Returns a pointer to the rotation next edge
  // over the starting point of the half-edge.
  medial_axis_edge_type* rot_next() { return prev_->twin(); }
  const medial_axis_edge_type* rot_next() const { return prev_->twin(); }

  // Returns a pointer to the rotation prev edge
  // over the starting point of the half-edge.
  medial_axis_edge_type* rot_prev() { return twin_->next(); }
  const medial_axis_edge_type* rot_prev() const { return twin_->next(); }

  // Returns true if the edge is finite (segment, parabolic arc).
  // Returns false if the edge is infinite (ray, line).
  bool is_finite() const { return vertex0() && vertex1(); }

  // Returns true if the edge is infinite (ray, line).
  // Returns false if the edge is finite (segment, parabolic arc).
  bool is_infinite() const { return !vertex0() || !vertex1(); }

  // Returns true if the edge is linear (segment, ray, line).
  // Returns false if the edge is curved (parabolic arc).
  bool is_linear() const {
    return (color_ & BIT_IS_LINEAR) ? true : false;
  }

  // Returns true if the edge is curved (parabolic arc).
  // Returns false if the edge is linear (segment, ray, line).
  bool is_curved() const {
    return (color_ & BIT_IS_LINEAR) ? false : true;
  }

  // Returns false if edge goes through the endpoint of the segment.
  // Returns true else.
  bool is_primary() const {
    return (color_ & BIT_IS_PRIMARY) ? true : false;
  }

  // Returns true if edge goes through the endpoint of the segment.
  // Returns false else.
  bool is_secondary() const {
    return (color_ & BIT_IS_PRIMARY) ? false : true;
  }

  color_type color() const { return color_ >> BITS_SHIFT; }
  void color(color_type color) const {
    color_ &= BITS_MASK;
    color_ |= color << BITS_SHIFT;
  }
  
  // foot: where radius from vertex0 touches source segment at a 90 degree angle
  const detail::point_2d<default_voronoi_builder::int_type>* foot() const { 
    if (!footset_) {return NULL;}
    return &foot_;
  }
  void foot(coordinate_type x, coordinate_type y) {
    footset_ = true;
    foot_.x(x);
    foot_.y(y);
  }

 private:
  // 5 color bits are reserved.
  enum Bits {
    BIT_IS_LINEAR = 0x1,  // linear is opposite to curved
    BIT_IS_PRIMARY = 0x2,  // primary is opposite to secondary

    BITS_SHIFT = 0x5,
    BITS_MASK = 0x1F
  };

  medial_axis_cell_type* cell_;
  medial_axis_vertex_type* vertex_;
  medial_axis_edge_type* twin_;
  medial_axis_edge_type* next_;
  medial_axis_edge_type* prev_;
  mutable color_type color_;
  mutable detail::point_2d<default_voronoi_builder::int_type> foot_;
  bool footset_;
  mutable detail::point_2d<default_voronoi_builder::int_type> p1_;

};

template <typename T>
struct medial_axis_traits {
  typedef T coordinate_type;
  typedef medial_axis_cell<coordinate_type> cell_type;
  typedef medial_axis_vertex<coordinate_type> vertex_type;
  typedef medial_axis_edge<coordinate_type> edge_type;
  typedef class {
   public:
    enum { ULPS = 128 };
    bool operator()(const vertex_type& v1, const vertex_type& v2) const {
      return (ulp_cmp(v1.x(), v2.x(), ULPS) ==
              detail::ulp_comparison<T>::EQUAL) &&
             (ulp_cmp(v1.y(), v2.y(), ULPS) ==
              detail::ulp_comparison<T>::EQUAL);
    }
   private:

src/medial_axis.hpp  view on Meta::CPAN

event_log_ += "x1=\""+to_str(edge->vertex0()->x())+"\" y1=\""+to_str(edge->vertex0()->y())+"\" ";
event_log_ += "x2=\""+to_str(edge->vertex1()->x())+"\" y2=\""+to_str(edge->vertex1()->y())+"\" />\n";
if (edge->is_primary()) {
event_log_ += "<line style=\"stroke-width:200000;stroke:orange;\" ";
event_log_ += "x1=\""+to_str(edge->vertex0()->x())+"\" y1=\""+to_str(edge->vertex0()->y())+"\" ";
event_log_ += "x2=\""+to_str(edge->vertex1()->x())+"\" y2=\""+to_str(edge->vertex1()->y())+"\" />\n";
} else if (!edge->is_primary()) {
event_log_ += "<line style=\"stroke-width:200000;stroke:aqua;\" ";
event_log_ += "x1=\""+to_str(edge->vertex0()->x())+"\" y1=\""+to_str(edge->vertex0()->y())+"\" ";
event_log_ += "x2=\""+to_str(edge->vertex1()->x())+"\" y2=\""+to_str(edge->vertex1()->y())+"\" />\n";
}
}
}
}

    // Now all edges within the polygon have color() == 0 and all edges
    // outside of the polygon or inside holes in the polygon have 
    // color() == 1.

    /////////////
    // At this point we modify the half edge graph to better represent the 
    // the medial axis.
    // The main thing to do is update next() and prev() pointers to follow
    // along the primary edges that represent the medial axis, instead
    // of having them point just to the next/prev within each Voronoi cell.

    // Get the edge corresponding to the first polygon input segment
    // so the first loop we traverse is the outer polygon loop.
    // Currently it doesn't matter that we process that first, but we
    // may want to enhance the output data structure later to reflect 
    // inside vs outside/in-concavity/in-hole medial axis edge collections.

    edge_type * start_edge = NULL;
    for (edge_iterator it = edges_.begin(); it != edges_.end(); ++it) {
      if (it->cell()->source_index() == 0
          && it->color() == 0
          && it->is_primary()
         ) {
        start_edge = &(*it);
        break;
      }
    }

    // Walk the edge references and modify to represent medial axis.
    while (start_edge != NULL) {
      edge_type * edge = start_edge;
      //start_edge->color(2);
      do {
        // mark visited internal edges (will restore to 0 afterward)
        edge->color(2);

        // if next edge is within polygon
        if (edge->next()->color() == 0 || edge->next()->color() == 2) {
          if (edge->next()->is_primary()) { 
            // go to next edge within same cell 
            edge = edge->next();
          } else { 
            // skip over a non-primary edge to the primary edge that follows it
            edge_type* prev = edge;
            edge = edge->next()->twin()->next();
            // get foot from non-primary endpoint and
            // mirror foot info from the non-primary to the twin
            if (prev->twin()->vertex0() && prev->twin()->vertex1() && prev->next()->vertex1()) {
              // The reflect about line case is simple:
              double x = prev->next()->vertex1()->x();
              double y = prev->next()->vertex1()->y();
              
              if (!edge->foot()) {
                edge->foot(x, y);
              }
              
              double x0 = prev->twin()->vertex0()->x();
              double y0 = prev->twin()->vertex0()->y();
              double x1, y1;
              // would like to already have foot in place
              // but not quite there yet, and this performs well
              if (true || !prev->twin()->foot()) {
                if (!prev->twin()->is_curved()) {
                  double x1 = prev->twin()->vertex1()->x() + 0;
                  double y1 = prev->twin()->vertex1()->y() + 0;
                  reflect(x, y, x0, y0, x1, y1);
                  prev->twin()->foot(x, y);
                  //printf("reflect foot to line\n");
                } else {
                  // The case for a curved edge isn't as simple, but 
                  // it seems most feet in this case are already properly
                  // calculated by the event-processing code.
                  // It may be that we never get to, or should never need to 
                  // get into this else{}. Maybe eliminate this after foot-finding
                  // in the event-processing has been fully understood and
                  // implemented.
                  // ... "reflect foot for parabola" still happens a lot -
                  //     still depending on it
                  if (!prev->twin()->prev()->is_primary()) {
                    //printf("from prev twin prev non-primary\n");
                    prev->twin()->foot(prev->twin()->prev()->vertex0()->x(),
                                       prev->twin()->prev()->vertex0()->y()
                                      );       
                  }
                  else {
                    double x = prev->next()->vertex1()->x();
                    double y = prev->next()->vertex1()->y();
                    if (!edge->is_curved()) {
                      double x0 = edge->vertex0()->x();
                      double y0 = edge->vertex0()->y();
                      double x1 = edge->vertex1()->x();
                      double y1 = edge->vertex1()->y();
                      reflect(x, y, x0, y0, x1, y1);
                      prev->twin()->foot(x, y);
                      //printf("reflect foot for parabola\n");
                    }                  
                  }
                }
              }
            }
            // first make the clipped-out edges ahead link to themselves
            prev->next()->twin()->next(prev->next());
            prev->next()->prev(prev->next()->twin());
            // now link this to new next
            prev->next(edge);
            edge->prev(prev);

src/medial_axis.hpp  view on Meta::CPAN

        );
      if (it->vertex0()) {
        printf("[%f , %f , %f]",
          it->vertex0()->x(),
          it->vertex0()->y(),
          it->vertex0()->r()
        );
      }
      else {printf("no vert0");}
      printf("\n");
      }
    }
    */
  }

 private:
  typedef typename cell_container_type::iterator cell_iterator;
  typedef typename vertex_container_type::iterator vertex_iterator;
  typedef typename edge_container_type::iterator edge_iterator;
  typedef typename TRAITS::vertex_equality_predicate_type
    vertex_equality_predicate_type;

  template <typename SEvent>
  bool is_primary_edge(const SEvent& site1, const SEvent& site2) const {
    bool flag1 = site1.is_segment();
    bool flag2 = site2.is_segment();
    if (flag1 && !flag2) {
      return (site1.point0() != site2.point0()) &&
             (site1.point1() != site2.point0());
    }
    if (!flag1 && flag2) {
      return (site2.point0() != site1.point0()) &&
             (site2.point1() != site1.point0());
    }
    return true;
  }

  template <typename SEvent>
  bool is_linear_edge(const SEvent& site1, const SEvent& site2) const {
    if (!is_primary_edge(site1, site2)) {
      return true;
    }
    return !(site1.is_segment() ^ site2.is_segment());
  }

  // Remove degenerate edge.
  void remove_edge(edge_type* edge) {
    
    // Are these two ifs necessary?
    // Put these in for debugging, where the problem was something else,
    // but these do fill in/transfer some missing feet.
    // After revising the foot-finding (trying to do it all in the sweepline
    // event processing), see if these are still needed.
    if (edge->foot() && !edge->next()->foot()) {
      edge->next()->foot(edge->foot()->x(), edge->foot()->y());
    }
    if (edge->twin()->foot() && !edge->twin()->next()->foot()) {
      edge->twin()->next()->foot(edge->twin()->foot()->x(), edge->twin()->foot()->y());
    }

    // Update the endpoints of the incident edges to the second vertex.
    vertex_type* vertex = edge->vertex0();
    edge_type* updated_edge = edge->twin()->rot_next();
    while (updated_edge != edge->twin()) {
      updated_edge->vertex0(vertex);
      updated_edge = updated_edge->rot_next();
    }
    
    edge_type* edge1 = edge;
    edge_type* edge2 = edge->twin();

    edge_type* edge1_rot_prev = edge1->rot_prev();
    edge_type* edge1_rot_next = edge1->rot_next();

    edge_type* edge2_rot_prev = edge2->rot_prev();
    edge_type* edge2_rot_next = edge2->rot_next();

    // Update prev/next pointers for the incident edges.
    edge1_rot_next->twin()->next(edge2_rot_prev);
    edge2_rot_prev->prev(edge1_rot_next->twin());
    edge1_rot_prev->prev(edge2_rot_next->twin());
    edge2_rot_next->twin()->next(edge1_rot_prev);

  }

  void mark_exterior(edge_type* edge) {
    if (edge->color() == 1) {
      return;
    }
    edge->color(1);
    edge->twin()->color(1);
    edge->cell()->color(1);
    edge->twin()->cell()->color(1);
    vertex_type* v = edge->vertex1();
    if (!v) {v = edge->vertex0();}
    if (v == NULL || !edge->is_primary()) {
      return;
    }
    v->color(1);
    edge_type* e = v->incident_edge();
    do {
      mark_exterior(e);
      e = e->rot_next();
    } while (e != v->incident_edge());
  }

  void mark_interior(edge_type* edge, bool backward = false) {
    // This function seems to work as intended, though it's still
    // on probation. The conditionals in the do {} while(); might not all be
    // correct or necessary (or they might be). 
    edge->color(0);
    edge->twin()->color(0);
    vertex_type* v = edge->vertex0();
    edge_type* e;
    if (edge->is_curved()) {
      edge_type* start_e = (edge->cell()->contains_point()) ? edge : edge->twin();
      e = start_e;
      do {
        if (!e->is_primary()) { 
          e->color(0);
          e->twin()->color(0);