minkowski_sum_conv_2.h

很多二维 三维几何计算算法 C++ 类库

    return (sum_holes);
  }

private:

  /*!
   * Compute a convolution cycle starting from tow given vertices.
   * \param cycle_id The index of the current cycle.
   * \param n1 The size of the first polygon.
   * \param forward1 Whether we move forward or backward on this polygon.
   * \param dirs1 The directions of the edges in the first polygon.
   * \param curr1 Points to the current vertex in the first polygon.
   * \param k1 The index of this vertex (between 0 and n1 - 1).
   * \param n2 The size of the second polygon.
   * \param forward2 Whether we move forward or backward on this polygon.
   * \param dirs2 The directions of the edges in the second polygon.
   * \param curr2 Points to the current vertex in the second polygon.
   * \param k2 The index of this vertex (between 0 and n2 - 1).
   * \param used_labels Input/output: The segment labels used so far.
   * \param queue A queue of anchor vertices for loops in the cycle.
   * \param cycle Output: An list of labeled segments that constitute the
   *                      convolution cycle.
   * \return A past-the-end iterator for the output segments.
   */
  void _convolution_cycle (unsigned int cycle_id,
                           unsigned int n1, bool forward1, 
                           const std::vector<Direction_2>& dirs1, 
                           Vertex_circulator curr1, unsigned int k1,
                           unsigned int n2, bool forward2, 
                           const std::vector<Direction_2>& dirs2, 
                           Vertex_circulator curr2, unsigned int k2,
                           Labels_set& used_labels,
                           Anchors_queue& queue,
                           Segments_list& cycle) const

  {
    // Update the circulator pointing to the next vertices in both polygons.
    unsigned int          seg_index = 0;
    const unsigned int    first1 = k1;
    const unsigned int    first2 = k2;
    Vertex_circulator     next1 = curr1;
    Vertex_circulator     next2 = curr2;
    Convolution_label     label;
    Point_2               first_pt, curr_pt, next_pt;
    bool                  inc1, inc2;
    Comparison_result     res;
    const bool            MOVE_ON_1 = true, MOVE_ON_2 = false;

    if (forward1)
      ++next1;
    else
      --next1;

    if (forward2)
      ++next2;
    else
      --next2;
    
    // Start constructing the convolution cycle from *curr1 and *curr2.
    curr_pt = first_pt = f_add (*curr1, f_vector(CGAL::ORIGIN, *curr2));
    do
    {
      // Determine on which polygons we should move.
      inc1 = false;
      inc2 = false;

      if (f_ccw_in_between (dirs1[k1],
                            dirs2[(n2 + k2 - 1) % n2],
                            dirs2[k2]))
      {
        inc1 = true;

        label = Convolution_label (k1, k2, 1);
        if (used_labels.count (label) != 0)
          inc1 = false;
      }
      
      if (f_ccw_in_between (dirs2[k2],
                            dirs1[(n1 + k1 - 1) % n1],
                            dirs1[k1]))
      {
        if (inc1)
        {
          // If we are about to increment the first polygon, add an anchor
          // to the queue. Next time we reach here we will increment the
          // second polygon (and proceed until reaching this point again and
          // closing the loop).
          label = Convolution_label (k1, k2, 2);
          if (used_labels.count (label) == 0)
          {
	    queue.push_back (Anchor (Vertex_ref (curr1, k1),
				     Vertex_ref (curr2, k2)));
          }
        }
        else
        {
          inc2 = true;

          label = Convolution_label (k1, k2, 2);
          if (used_labels.count (label) != 0)
            inc2 = false;
        }
      }
      
      if (! inc1 && ! inc2 &&
          f_equal (dirs1[k1], dirs2[k2]))
      {
        inc1 = true;
        inc2 = true;

        label = Convolution_label (k1, k2, 1);
        if (used_labels.count (label) != 0)
          inc1 = false;

        if (inc1)
          label = Convolution_label ((k1 + 1) % n1, k2, 2); 
        else
          label = Convolution_label (k1, k2, 2);

        if (used_labels.count (label) != 0)
          inc2 = false;
      }

      CGAL_assertion (inc1 || inc2);

      // Act according to the increment flags.
      if (inc1)
      {
        // Translate the current edge of the first polygon to *curr2.
        next_pt = f_add (*next1, f_vector(CGAL::ORIGIN, *curr2));

        res = f_compare_xy (curr_pt, next_pt);
        CGAL_assertion (res != EQUAL);

        cycle.push_back (Labeled_segment_2 (Segment_2 (curr_pt, next_pt),
                                            X_curve_label ((res == SMALLER),
                                                           cycle_id,
                                                           seg_index,
							   MOVE_ON_1)));
        used_labels.insert (Convolution_label (k1, k2, 1));
	seg_index++;

        // Proceed to the next vertex of the first polygon.
        curr1 = next1;
        k1 = (k1 + 1) % n1;

        if (forward1)
          ++next1;
        else
          --next1;

        curr_pt = next_pt;
      }

      if (inc2)
      {
        // Translate the current edge of the second polygon to *curr1.
        next_pt = f_add (*next2, f_vector(CGAL::ORIGIN, *curr1));

        res = f_compare_xy (curr_pt, next_pt);
        CGAL_assertion (res != EQUAL);

        cycle.push_back (Labeled_segment_2 (Segment_2 (curr_pt, next_pt),
                                            X_curve_label ((res == SMALLER),
                                                           cycle_id,
                                                           seg_index,
							   MOVE_ON_2)));
        used_labels.insert (Convolution_label (k1, k2, 2));
	seg_index++;

        // Proceed to the next vertex of the second polygon.
        curr2 = next2;
        k2 = (k2 + 1) % n2;

        if (forward2)
          ++next2;
        else
          --next2;

        curr_pt = next_pt;
      }

    } while (k1 != first1 || k2 != first2); 

    CGAL_assertion (f_equal (curr_pt, first_pt));

    // Before moving un-necessary sub-cycles from the segment list, make sure
    // the list contains no "cyclic" sub-cylces. We do that by making sure that
    // the first and last segments of the list correspond to traversals of
    // different polygons.
    int     steps = cycle.size();

    while (steps > 0 &&
           cycle.front().label().get_flag() == 
           cycle.back().label().get_flag())
    {
      cycle.push_back (cycle.front());
      cycle.pop_front();
      steps--;
    }

    if (steps == 0)
    {
      cycle.clear();
      return;
    }

    // Reduce un-necessary sub-cycles. This is done by scanning the segments
    // list for subsequences sharing a common move_on indicator. When we
    // encounter such a subsequence that equals the size of the corresponding
    // polygon, we can safely remove it from the convolution cycle.
    typename std::list<Labeled_segment_2>::iterator  first, curr;
    bool                                             move_on;
    unsigned int                                     count = 1;
    bool                                             reduced_cycle = false;

    curr = first = cycle.begin();
    move_on = first->label().get_flag();

    curr->label().set_flag (false);
    ++curr;
    while (curr != cycle.end())
    {
      if ((move_on == MOVE_ON_1 && count == n1) ||
          (move_on == MOVE_ON_2 && count == n2))
      {
	// We have discovered a sequence of moves on one of the polygon that
	// equals the polygon size, so we can remove this sequence.
        cycle.erase (first, curr);
	reduced_cycle = true;
        first = curr;
        move_on = first->label().get_flag();
        count = 1;
      }
      else
      {
        if (move_on == curr->label().get_flag())
        {
          count++;
        }
        else
        {
          first = curr;
          move_on = first->label().get_flag();
          count = 1;
        }
      }

      curr->label().set_flag (false);
      ++curr;
    }

    if ((move_on == MOVE_ON_1 && count == n1) ||
        (move_on == MOVE_ON_2 && count == n2))
    {
      cycle.erase (first, curr);
      reduced_cycle = true;
    }

    // Eliminate "antenna"s that occur in the cycle.
    typename std::list<Labeled_segment_2>::iterator  next, after_next;
    bool                                             found_antenna;

    next = curr = cycle.begin();
    ++next;

    while (curr != cycle.end())
    {
      // If the current segment is the last one in the cycle, its next segment
      // (in cyclic order) is the first one.
      if (next == cycle.end())
      {
        found_antenna = f_equal (curr->source(), cycle.begin()->target());
        if (found_antenna)
        {
          next = cycle.begin();
          after_next = cycle.end();
        }
      }
      else
      {
        found_antenna = f_equal (curr->source(), next->target());
        if (found_antenna)
        {
          after_next = next;
          ++after_next;
        }
      }

      // We know that curr's target and next's source is the same point.
      // If they also share their other endpoint, then these two segments
      // form an antenna and should threrefore be removed from the cycle.
      if (found_antenna)
      {
        cycle.erase (curr);
        cycle.erase (next);
        curr = after_next;

        if (after_next != cycle.end())
        {
          next = curr;
          ++next;
        }

        reduced_cycle = true;
      }
      else
      {
        curr = next;
	if(next != cycle.end())
	{
	  ++next;
	}
      }
    }

    // In case we have reduced the cycle, re-number the segments in it.
    if (reduced_cycle)
    {
      seg_index = 0;
      for (curr = cycle.begin(); curr != cycle.end(); ++curr, ++seg_index)
        cycle.back().label().set_index (seg_index);
    }

    cycle.back().label().set_flag (true);
    return;
  }
};


CGAL_END_NAMESPACE

#endif