CGAL users discussion list

[W Randolph Franklin <>]

Hi,

The following program fragment seems to show that the intersection of 2
segments can be outside their bounds.   I'm still learning, so the
mistake is probably mine, but I can't find it.  Help?

FYI, error.C was extracted from a much larger program and dataset.

Note that I'm using Exact_predicates_inexact_constructions_kernel and
the erroneous result was computed with a chain of Segment_2,
intersection, compare_x.

I compiled it this:

/usr/bin/g++-4.7 -O3 -frounding-math     error.C  -lCGAL -lmpfr -lgmp -o
error

My system is this:

Linux host 3.2.0-25-generic #40-Ubuntu SMP Wed May 23 20:30:51 UTC 2012
x86_64 x86_64 x86_64 GNU/Linux

Thanks.

================================================================

// Time-stamp: </wrf/c/overprop/error.C, Mon, 18 Jun 2012, 17:41:12 EDT,
http://wrfranklin.org/>

#include <iomanip>
#include <iostream>
using namespace std;

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/intersections.h>
#include <CGAL/Object.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
using CGAL::Object;
using CGAL::compare_x;
using CGAL::compare_y;
using CGAL::object_cast;

// Print an expression's name then its value, possible followed by a
// comma or endl.  Ex: cout << PRINTC(x) << PRINTN(y);
#define PRINT(arg)  #arg "=" << (arg)
#define PRINTC(arg)  #arg "=" << (arg) << ", "
#define PRINTN(arg)  #arg "=" << (arg) << endl

int main() {
  cout << "Intersection of 2 segments is outside their bounds." << endl;
  K::Point_2 v0(63.6421, 2067.410);
  K::Point_2 v1(62.7046, 2071.750);
  K::Point_2 w0(62.7046, 2071.750);
  K::Point_2 w1(59.8669, 2066.980);
  Object obj = CGAL::intersection(K::Segment_2(v0,v1), K::Segment_2(w0,w1));
  if (const K::Point_2 *xsect = object_cast<K::Point_2>(&obj)) {
    cout << "Intersection found. " << PRINTC(v0) << PRINTN(v1) <<
PRINTC(w0) << PRINTN(w1) << PRINTN(*xsect);
    if ((compare_x(*xsect,v0)*compare_x(*xsect,v1)>0) ||
        (compare_y(*xsect,v0)*compare_y(*xsect,v1)>0) ||
        (compare_x(*xsect,w0)*compare_x(*xsect,w1)>0) ||
        (compare_y(*xsect,w0)*compare_y(*xsect,w1)>0)) {
      cout << "\nERROR: intersection is not within bounds of edges." <<
endl;
      cout << PRINTN(compare_x(*xsect,v0));
      cout << PRINTN(compare_x(*xsect,v1));
      cout << PRINTN(compare_y(*xsect,v0));
      cout << PRINTN(compare_y(*xsect,v1));
      cout << PRINTC(compare_x(*xsect,w0)) << " WRONG, should be 0" << endl;
      cout << PRINTN(compare_x(*xsect,w1));
      cout << PRINTN(compare_y(*xsect,w0));
      cout << PRINTN(compare_y(*xsect,w1));
      cout << scientific << PRINTN(xsect->x()-w0.x()) << endl;
    }
  }
}

================================================================
Output:

Intersection of 2 segments is outside their bounds.
Intersection found. v0=63.6421 2067.41, v1=62.7046 2071.75
w0=62.7046 2071.75, w1=59.8669 2066.98
*xsect=62.7046 2071.75

ERROR: intersection is not within bounds of edges.
compare_x(*xsect,v0)=-1
compare_x(*xsect,v1)=1
compare_y(*xsect,v0)=1
compare_y(*xsect,v1)=0
compare_x(*xsect,w0)=1,  WRONG, should be 0
compare_x(*xsect,w1)=1
compare_y(*xsect,w0)=0
compare_y(*xsect,w1)=1
xsect->x()-w0.x()=7.105427e-15

================================================================


--
W. Randolph Franklin, Professor
ECSE Dept., 6026 JEC,
Rensselaer Polytechnic Inst,
110 8th St,
Troy NY, 12180 USA


 (most reliable address) or 

 or


+1 (518) 276-6077

http://wrfranklin.org/