arr_landmarks_pl_functions.h

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

      {
       //intersect = false;
        return (true);
      }
      return (false); //V
    }                                                                         
    if (comp_right_xy_res == SMALLER) 
    {  //the segments ends before (to the right) of the curve 
      Comparison_result curve_comp_right_res = 
        compare_y_at_x(seg_right,cv);

      if (curve_comp_right_res == EQUAL) {
        CGAL_PRINT_DEBUG("2 points collide");
        //this means that the query point is on the curve
        return (false); //V
      }
      if (curves_comp != curve_comp_right_res) 
      { //the segment is on the other side of the segment's end-point
        CGAL_PRINT_DEBUG("intersecting");
        intersect = true;
        return (true);
      }
      else {
        //intersect = false;
        return (true);
      }
    }
    else if (comp_right_xy_res == LARGER) 
    { //the curve ends before (to the right) of the segment
      Comparison_result curve_comp_right_res =
        compare_y_at_x(cv_right,seg) ;      

      if (curve_comp_right_res == EQUAL) {
        CGAL_PRINT_DEBUG("2 points collide");
        //this means that the curve's right enpoint is on the segment
        //intersect = false;
        return (true);
      }
      if (curves_comp == curve_comp_right_res) 
      {//the segment is on the same side as the curve's end-point
        CGAL_PRINT_DEBUG("intersecting");
        intersect = true;
        return (true);
      }
      else {
        //intersect = false;
        return (true);
      }
    }
    else { //(comp_right_xy_res == EQUAL) 
        CGAL_PRINT_DEBUG("2 endpoints collide");
        //this means that the query point is on the curve
        //(even on the curve's endpoint = vertex)
        return (false); //V
    }
  }

  // the right end-point of the segments is equal to the right end-point 
  //of the curve
  else if (comp_right_xy_res == EQUAL) 
  {
    CGAL_PRINT_DEBUG("the right end-point of the segments is equal to the"\
                <<" right end-point of the curve");
    // compare to the left of the curves
    Comparison_result curves_comp = compare_y_at_x_left(seg, cv, seg_right);

    if (curves_comp == EQUAL) 
    {
      CGAL_PRINT_DEBUG("overlap !!!");
      //this means: 
      // 1. the query is on the curve (should have been checked). 
      // 2. the landmark is on the curve (should have been checked).
      // 3. the curve endpoint is on the segment. if it's the left endpoint - 
      //    intersect. right - no intersection.
      if (compare_y_at_x(cv_left, seg) == EQUAL)
      {
        intersect = true;
        return (true);
      }
      else if (compare_y_at_x(cv_right, seg) == EQUAL)
      {
       //intersect = false;
        return (true);
      }
      return (false); //V
    }
    if (comp_left_xy_res == SMALLER) 
    { //the curve ends before (to the left) of the segment 
      Comparison_result curve_comp_left_res = 
        compare_y_at_x(cv_left,seg) ;

      if (curve_comp_left_res == EQUAL) {
        CGAL_PRINT_DEBUG("2 points collide");
        //this means that the curve's left enpoint is on the segment
        intersect = true;
        return (true);
      }
      if (curves_comp == curve_comp_left_res) {
        CGAL_PRINT_DEBUG("intersecting");
        intersect = true;
        return (true);
      }
      else {
        //intersect = false;
        return (true);
      }
    }
    else if (comp_left_xy_res == LARGER) 
    { //the segment ends before (to the left) of the curve 
      Comparison_result curve_comp_left_res = 
        compare_y_at_x(seg_left,cv) ;

      if (curve_comp_left_res == EQUAL) {
        CGAL_PRINT_DEBUG("2 points collide");
        //this means that the query point is the curve
        return (false); //V
      }
      if (curves_comp != curve_comp_left_res) {
        CGAL_PRINT_DEBUG("intersecting");
        intersect = true;
        return (true);
      }
      else {
        //intersect = false;
        return (true);
      }
    }
    else { //(comp_left_xy_res == EQUAL) 
        CGAL_PRINT_DEBUG("2 endpoints collide");
        return (false); //V
    }
  }

  //one curve is inside the other curve's x-range (fully) 
  else if (comp_left_xy_res != comp_right_xy_res) { 
    if (comp_left_xy_res == LARGER) 
    {  //the segment is inside the curve's x-range
      CGAL_PRINT_DEBUG("the segment is inside the curve's x-range.");
      CGAL_LM_DEBUG ( //checks for debugging - remove later
        if (! is_in_x_range(cv,seg_left) ) {
          CGAL_PRINT_ERROR( "! is_in_x_range(cv,seg_left) "); 
          return (false); } //V-debugging
        if (! is_in_x_range(cv,seg_right) )  {
          CGAL_PRINT_ERROR("(! is_in_x_range(cv,seg_right) "); 
          return (false); } //V-debugging
      )

      Comparison_result curve_comp_left_res = 
        compare_y_at_x(seg_left,cv);
      Comparison_result curve_comp_right_res =
        compare_y_at_x(seg_right,cv) ;

      if ((curve_comp_left_res == EQUAL)||
        (curve_comp_right_res == EQUAL))
      {
        //CGAL_PRINT_ERROR(" WARNING 7: left or right endpoint of the 
        //segment is on the curve ");
        //this should not happen since p is on the curve, 
        //we should have find it already, and if v is on the curve, 
        //than v should have cut the curve in two
        //this can happen if we're walking from edge. 
        CGAL_PRINT_DEBUG("no intersection");
        //intersect = false;
        return (true);
        //return (false);
      }
      if  (curve_comp_left_res == curve_comp_right_res) 
      {  //no intersection
        CGAL_PRINT_DEBUG("no intersection");
        //intersect = false;
        return (true);
      }
      else 
      {
        CGAL_PRINT_DEBUG("intersecting");
        intersect = true;
        return (true);
      }
    }
    else
    {  //the curve is inside the segments's x-range
      CGAL_PRINT_DEBUG("the curve is inside the segments's x-range");
      CGAL_LM_DEBUG ( //checks for debugging - remove later
        if (! is_in_x_range(seg,cv_left) ) {
         CGAL_PRINT_ERROR( "! is_in_x_range(seg,cv_left)"); 
         return (false);} //V-debugging
        if (! is_in_x_range(seg,cv_right) ) {
         CGAL_PRINT_ERROR("! is_in_x_range(seg,cv_right)"); 
         return (false);} //V-debugging
      )

      Comparison_result curve_comp_left_res = compare_y_at_x(cv_left,seg);
      Comparison_result curve_comp_right_res = compare_y_at_x(cv_right,seg);

      if (curve_comp_right_res == EQUAL)
      {
        CGAL_PRINT_DEBUG("the curve right endpoint is on the segment");
        CGAL_PRINT_DEBUG("no intersection");
        //intersect = false;
        return (true);
      }
      else if (curve_comp_left_res == EQUAL) 
      {
        CGAL_PRINT_DEBUG("the curve left endpoint is on the segment");
        CGAL_PRINT_DEBUG("intersecting");
        intersect = true;
        return (true);
      }
      else if  (curve_comp_left_res == curve_comp_right_res) 
      {  //no intersection
        CGAL_PRINT_DEBUG("no intersection");
        //intersect = false;
        return (true);
      }
      else 
      {
        CGAL_PRINT_DEBUG("intersecting");
        intersect = true;
        return (true);
      }
    }
  }
  else 
  {//one endpoint of the first curve is inside the other curve's 
    //x-range and one endpoitn is out, and vise versa.
    if (comp_left_xy_res == SMALLER) 
    { //if the segment right point is in and the curve's left point
      CGAL_PRINT_DEBUG("the segment right point is in and the"\
                  <<"curve's left point");
      CGAL_LM_DEBUG ( //checks for debugging - remove later
        if (! is_in_x_range(seg,cv_left) ) {
         CGAL_PRINT_ERROR("! is_in_x_range(seg,cv_left)"); 
         return (false);}
        if (! is_in_x_range(cv,seg_right) ) {
         CGAL_PRINT_ERROR( "! is_in_x_range(cv,seg_right)"); 
         return (false);}
      )

      Comparison_result curve_comp_left_res = 
        compare_y_at_x(cv_left,seg);
      Comparison_result curve_comp_right_res = 
        compare_y_at_x(seg_right,cv);

      if (curve_comp_right_res == EQUAL || curve_comp_left_res == EQUAL) 
      {
        if (equal(seg_right, cv_left)) {
          //this case is o.k., just return that there is 
          //no intersection, because probably v is the same 
          //for both curves
          CGAL_PRINT_DEBUG("segment's right endpoint = "\
                      <<"curve's left endpoint ");
          CGAL_PRINT_DEBUG("no intersection");
          //intersect = false;
          return (true);    
        }
        if (curve_comp_left_res == EQUAL)
        {
          //the curve's left end-point is on the segment.
          CGAL_PRINT_DEBUG("the curve's left end-point is on the segment");
          CGAL_PRINT_DEBUG("intersecting");
          intersect = true;                    
          return (true);
        }
        //the segment's right endpoint is on the curve. 
        return (false); //V
      }
      if  (curve_comp_left_res == curve_comp_right_res) 
      {  //intersection
        CGAL_PRINT_DEBUG("intersecting");
        intersect = true;
        return (true);        
      }
      else 
      {
        CGAL_PRINT_DEBUG("no intersection");
        //intersect = false;
        return (true);      
      }
    }
    else 
    { //if the curve's right point is in and the segment's left point
      CGAL_PRINT_DEBUG("the curve's right point is in and the "\
                  <<"segment's left point");
      CGAL_LM_DEBUG ( //checks for debugging - remove later
        if (! is_in_x_range(cv,seg_left) ) {
          CGAL_PRINT_ERROR("! is_in_x_range(cv,seg_left) ***  "); 
          return (false);  } //V-debugging
        if (! is_in_x_range(seg,cv_right) ) {
          CGAL_PRINT_ERROR("! is_in_x_range(seg,cv_right) *** "); 
          return (false); } //V-debugging
      )

      Comparison_result curve_comp_left_res = 
        compare_y_at_x(seg_left,cv);
      Comparison_result curve_comp_right_res = 
        compare_y_at_x(cv_right,seg);

      CGAL_PRINT_DEBUG("curve_comp_right_res="<<curve_comp_right_res);
      CGAL_PRINT_DEBUG("curve_comp_left_res= "<<curve_comp_left_res);

      if (curve_comp_right_res == EQUAL || curve_comp_left_res == EQUAL)
      {
        if (equal(seg_left, cv_right)) {
          //this case is o.k., just return that 
          //there is no intersection, because probably 
          //v is the same for both curves
          CGAL_PRINT_DEBUG("segment's left endpoint = "\
                      <<"curve's right endpoint ");
          CGAL_PRINT_DEBUG("no intersection");
          //intersect = false;
          return (true);    
        }
        if (curve_comp_right_res == EQUAL)
        {
          CGAL_PRINT_DEBUG("intersecting");
          intersect = true;
          return (true);        
        }
        //the segment's left endpoint is on the curve. 
        return (false); //V
      }
      if  (curve_comp_left_res == curve_comp_right_res) 
      {  //intersection
        CGAL_PRINT_DEBUG("intersecting . ");
        intersect = true;
        return (true);        
      }
      else 
      {
        CGAL_PRINT_DEBUG("no intersection .");
        //intersect = false;
        return (true);      
      }
    }
  }
}

CGAL_END_NAMESPACE

#endif