CGAL users discussion list

[W Randolph Franklin <>]

Sebastien,

Thanks!

I'd actually spent some time reading the docs but somehow didn't see
that.   My bad.

FYI, the extract was part of a program is to take two planar
arrangements and compute the areas of all the non-empty intersections of
any polygon from the first with any polygon from the second.   The idea
is to do it in expected time linear in the number of pairs of
intersecting segments.    Pointers to any prior art are welcome.

Finally, why is an explicit to_double() required, instead of overloading
operator double() ?   I tried doing that, but it seems to require too
much internal knowledge.

/Randolph Franklin

On 06/19/2012 02:18 AM, Sebastien Loriot (GeometryFactory) wrote:
> Read these FAQ entries:
> http://www.cgal.org/FAQ.html#predicates_vs_constructions
> http://www.cgal.org/FAQ.html#inexact_NT
> 
> If you replace Exact_predicates_inexact_constructions_kernel by
> Exact_predicates_exact_constructions_kernel your error won't appear.
> 
> Sebastien.
> 
> 
> On 06/18/2012 11:52 PM, W Randolph Franklin wrote:
>> 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/
>>
>>
> 
>