conic_x_monotone_arc_2.h

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

      return (slope_res);
    }
    else if (!is_vertical_slope2)
    {
      // The first arc has a vertical slope at p: check whether it is
      // facing upwards or downwards and decide accordingly.
      CGAL_assertion ((this->_info & FACING_MASK) != 0);

      if ((this->_info & FACING_UP) != 0)
        return (LARGER);
      return (SMALLER);
    }
    else if (!is_vertical_slope1)
    {
      // The second arc has a vertical slope at p_int: check whether it is
      // facing upwards or downwards and decide accordingly.
      CGAL_assertion ((arc._info & FACING_MASK) != 0);

      if ((arc._info & FACING_UP) != 0)
        return (SMALLER);
      return (LARGER);
    }

    // The two arcs have vertical slopes at p_int:
    // First check whether one is facing up and one down. In this case the
    // comparison result is trivial.
    if ((this->_info & FACING_UP) != 0 && (arc._info & FACING_DOWN) != 0)
      return (LARGER);
    else if ((this->_info & FACING_DOWN)!= 0 && (arc._info & FACING_UP)!= 0)
      return (SMALLER);

    // Compute the second-order derivative by y and act according to it.
    _derive_by_y_at (p, 2, slope1_numer, slope1_denom);
    arc._derive_by_y_at (p, 2, slope2_numer, slope2_denom);

    Comparison_result  slope_res = CGAL::compare(slope2_numer*slope1_denom,
                                                 slope1_numer*slope2_denom);

    // If necessary, use the third-order derivative by y.
    if (slope_res == EQUAL)
    {
      // \todo Check this!
      _derive_by_y_at (p, 3, slope1_numer, slope1_denom);
      arc._derive_by_y_at (p, 3, slope2_numer, slope2_denom);

      slope_res = CGAL::compare (slope2_numer*slope1_denom,
                                 slope1_numer*slope2_denom);
    }

    // \todo Handle higher-order derivatives:
    CGAL_assertion(slope_res != EQUAL);

    if ((this->_info & FACING_UP) != 0 && (arc._info & FACING_UP) != 0)
    {
      // Both are facing up.
      return ((slope_res == LARGER) ? SMALLER : LARGER);
    }
    // Both are facing down.
    return (slope_res);
  }

  /*!
   * Compute the intersections with the given arc.
   * \param arc The given intersecting arc.
   * \param inter_map Maps conic pairs to lists of their intersection points.
   * \param oi The output iterator.
   * \return The past-the-end iterator.
   */
  template<class OutputIterator>
  OutputIterator intersect (const Self& arc,
                            Intersection_map& inter_map,
                            OutputIterator oi) const
  {
    if (_has_same_supporting_conic (arc))
    {
      // Check for overlaps between the two arcs.
      Self    overlap;

      if (_compute_overlap (arc, overlap))
      {
        // There can be just a single overlap between two x-monotone arcs:
        *oi = make_object (overlap);
        oi++;
        return (oi);
      }

      // In case there is not overlap and the supporting conics are the same,
      // there cannot be any intersection points, unless the two arcs share
      // an end point.
      // Note that in this case we do not define the multiplicity of the
      // intersection points we report.
      Alg_kernel  ker;

      if (ker.equal_2_object() (left(), arc.left()))
      {
        Intersection_point_2  ip (left(), 0);

        *oi = make_object (ip);
        oi++;
      }

      if (ker.equal_2_object() (right(), arc.right()))
      {
        Intersection_point_2  ip (right(), 0);

        *oi = make_object (ip);
        oi++;
      }

      return (oi);
    }

    // Search for the pair of supporting conics in the map (the first conic
    // ID in the pair should be smaller than the second one, to guarantee
    // uniqueness).
    Conic_pair                   conic_pair;
    Intersection_map_iterator    map_iter;
    Intersection_list            inter_list;
    bool                         invalid_ids = false;

    if (_id.is_valid() && arc._id.is_valid())
    {
      if (_id < arc._id)
        conic_pair = Conic_pair (_id, arc._id);
      else
        conic_pair = Conic_pair (arc._id, _id);
      
      map_iter = inter_map.find (conic_pair);
    }
    else
    {
      // In case one of the IDs is invalid, we do not look in the map neither
      // we cache the results.
      map_iter = inter_map.end();
      invalid_ids = true;
    }

    if (map_iter == inter_map.end())
    {
      // In case the intersection points between the supporting conics have
      // not been computed before, compute them now and store them in the map.
      _intersect_supporting_conics (arc, inter_list);

      if (! invalid_ids)
        inter_map[conic_pair] = inter_list;
    }
    else
    {
      // Obtain the precomputed intersection points from the map.
      inter_list = (*map_iter).second;
    }

    // Go over the list of intersection points and report those that lie on
    // both x-monotone arcs.
    typename Intersection_list::const_iterator  iter;

    for (iter = inter_list.begin(); iter != inter_list.end(); ++iter)
    {
      if (_is_between_endpoints ((*iter).first) &&
          arc._is_between_endpoints ((*iter).first))
      {
        *oi = make_object (*iter);
        ++oi;
      }
    }

    return (oi);
  }
  //@}

  /// \name Constructing x-monotone arcs.
  //@{

  /*!
   * Split the arc into two at a given split point.
   * \param p The split point.
   * \param c1 Output: The first resulting arc, lying to the left of p.
   * \param c2 Output: The first resulting arc, lying to the right of p.
   * \pre p lies in the interior of the arc (not one of its endpoints).
   */
  void split (const Conic_point_2& p,
              Self& c1, Self& c2) const
  {
    // Make sure that p lies on the interior of the arc.
    CGAL_precondition_code (
      Alg_kernel   ker;
    );

    CGAL_precondition (this->contains_point (p) &&
                       ! ker.equal_2_object() (p, this->_source) &&
                       ! ker.equal_2_object() (p, this->_target));

    // Make copies of the current arc.
    c1 = *this;
    c2 = *this;

    // Assign the endpoints of the arc.
    if ((this->_info & IS_DIRECTED_RIGHT) != 0)
    {
      // The arc is directed from left to right, so p becomes c1's target
      // and c2's source.
      c1._target = p;
      c2._source = p;

      if (! p.is_generating_conic (_id))
      {
        c1._target.set_generating_conic (_id);
        c2._source.set_generating_conic (_id);
      }
    }
    else
    {
      // The arc is directed from right to left, so p becomes c2's target
      // and c1's source.
      c1._source = p;
      c2._target = p;

      if (! p.is_generating_conic (_id))
      {
        c1._source.set_generating_conic (_id);
        c2._target.set_generating_conic (_id);
      }
    }

    return;
  }

  /*!
   * Flip the arc.
   * \return An arc with swapped source and target and a reverse orienation.
   */
  Self flip () const
  {
    // Make a copy of the current arc.
    Self    arc = *this;

    // Reverse the orientation.
    if (this->_orient == CLOCKWISE)
      arc._orient = COUNTERCLOCKWISE;
    else if (this->_orient == COUNTERCLOCKWISE)
      arc._orient = CLOCKWISE;

    // Swap the source and the target.
    arc._source = this->_target;
    arc._target = this->_source;

    // Change the direction bit among the information flags.
    arc._info = (this->_info ^ IS_DIRECTED_RIGHT);

    return (arc);
  }

  /*!
   * Trim the arc given its new endpoints.
   * \param ps The new source point.
   * \param pt The new target point.
   * \return The new trimmed arc.
   * \pre Both ps and pt lies on the arc and must conform with the current
   *      direction of the arc.
   */
  Self trim (const Conic_point_2& ps,
             const Conic_point_2& pt) const
  {
    // Make sure that both ps and pt lie on the arc.
    CGAL_precondition (this->contains_point (ps) &&
                       this->contains_point (pt));

    // Make sure that the endpoints conform with the direction of the arc.
    Self         arc = *this;
    Alg_kernel   ker;

    if (! ((((this->_info & IS_DIRECTED_RIGHT) != 0) &&
            ker.compare_xy_2_object() (ps, pt) == SMALLER) ||
           (((this->_info & IS_DIRECTED_RIGHT) == 0) &&
            ker.compare_xy_2_object() (ps, pt) == LARGER)))
    {
      // We are allowed to change the direction only in case of a segment.
      CGAL_assertion (this->_orient == COLLINEAR);
      arc._info = (this->_info ^ IS_DIRECTED_RIGHT);
    }

    // Make a copy of the current arc and assign its endpoints.    
    if (! ker.equal_2_object() (ps, this->_source))
    {
      arc._source = ps;

      if (! ps.is_generating_conic (_id))
        arc._source.set_generating_conic (_id);
    }
    
    if (! ker.equal_2_object() (pt, this->_target))
    {
      arc._target = pt;

      if (! pt.is_generating_conic (_id))
        arc._target.set_generating_conic (_id);
    }

    return (arc);
  }

  /*!
   * Check whether the two arcs are equal (have the same graph).
   * \param arc The compared arc.
   * \return (true) if the two arcs have the same graph; (false) otherwise.
   */
  bool equals (const Self& arc) const
  {
    // The two arc must have the same supporting conic curves.
    if (! _has_same_supporting_conic (arc))
      return (false);

    // Check that the arc endpoints are the same.
    Alg_kernel   ker;

    if(this->_orient == COLLINEAR)
    {
      CGAL_assertion(arc._orient == COLLINEAR);
      return((ker.equal_2_object() (this->_source, arc._source) &&
              ker.equal_2_object() (this->_target, arc._target)) ||
              (ker.equal_2_object() (this->_source, arc._target) &&
               ker.equal_2_object() (this->_target, arc._source)));
    }

    if (this->_orient == arc._orient)
    {
      // Same orientation - the source and target points must be the same.
      return (ker.equal_2_object() (this->_source, arc._source) &&
              ker.equal_2_object() (this->_target, arc._target));
    }
    else
    {
      // Reverse orientation - the source and target points must be swapped.
      return (ker.equal_2_object() (this->_source, arc._target) &&
              ker.equal_2_object() (this->_target, arc._source));
    }
  }

  /*!
   * Check whether it is possible to merge the arc with the given arc.
   * \param arc The query arc.
   * \return (true) if it is possible to merge the two arcs;
   *         (false) otherwise.
   */
  bool can_merge_with (const Self& arc) const
  {
    // In order to merge the two arcs, they should have the same supporting
    // conic.
    if (! _has_same_supporting_conic (arc))
      return (false);

    // Check if the left endpoint of one curve is the right endpoint of the
    // other.
    Alg_kernel   ker;

    return (ker.equal_2_object() (right(), arc.left()) ||
            ker.equal_2_object() (left(), arc.right()));
  }

  /*!
   * Merge the current arc with the given arc.
   * \param arc The arc to merge with.
   * \pre The two arcs are mergeable.
   */
  void merge (const Self& arc)
  {
    CGAL_precondition (this->can_merge_with (arc));

    // Check if we should extend the arc to the left or to the right.
    Alg_kernel   ker;

    if (ker.equal_2_object() (right(), arc.left()))
    {
      // Extend the arc to the right.
      if ((this->_info & IS_DIRECTED_RIGHT) != 0)
        this->_target = arc.right();
      else
        this->_source = arc.right();
    }
    else
    {
      CGAL_precondition (ker.equal_2_object() (left(), arc.right()));

      // Extend the arc to the left.
      if ((this->_info & IS_DIRECTED_RIGHT) != 0)
        this->_source = arc.left();
      else
        this->_target = arc.left();
    }

    return;
  }

  bool is_upper() const
  {
    return ((this->_info & FACING_UP) != 0);
  }

  bool is_lower() const
  {
    return ((this->_info & FACING_DOWN) != 0);
  }
  //@}

private:

  /// \name Auxiliary (private) functions.
  //@{

  /*!
   * Set the properties of the x-monotone conic arc (for the usage of the
   * constructors).
   */
  void _set ()
  {
    // Convert the coefficients of the supporting conic to algebraic numbers.
    Nt_traits        nt_traits;

    alg_r = nt_traits.convert (this->_r);
    alg_s = nt_traits.convert (this->_s);
    alg_t = nt_traits.convert (this->_t);
    alg_u = nt_traits.convert (this->_u);
    alg_v = nt_traits.convert (this->_v);
    alg_w = nt_traits.convert (this->_w);

    // Set the generating conic ID for the source and target points.
    this->_source.set_generating_conic (_id);
    this->_target.set_generating_conic (_id);