Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] point lying over a line problem

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] point lying over a line problem


Chronological Thread 
  • From: Alejandro Aragon <>
  • To:
  • Subject: Re: [cgal-discuss] point lying over a line problem
  • Date: Wed, 23 Jul 2008 12:24:19 -0500
  • Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:from:to:in-reply-to:content-type :content-transfer-encoding:mime-version:subject:date:references :x-mailer; b=FZLRByi0r7k4JEpwNgwz7WvzjihbulrYz1KL3jQcSz30iHxTLBw6lmDv7PHJiUoEIw u55glkOxdRbuBKOpC0fENQ42qrvi6+tix1eNUA4BVqk250XPaB1OmdZMiohmz20hwvan JQTTkDkESa/wDPvuizNosktEdGtdsS5BadSg4=

By the way, quoting the FAQ:

"If your program does not involve the construction of new objects from the input data (such as the intersection of two objects, or the center of a sphere defined by the input objects), the CGAL::Exact_predicates_inexact_constructions_kernel kernel provides a nice and fast way to use exact predicates together with an inexact number type such as double for constructions."

Now, I modified my little example:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <iostream>

using std::cout;
using std::endl;
using namespace CGAL;

int main() {

typedef CGAL::Exact_predicates_inexact_constructions_kernel KernelType;
typedef KernelType::Point_2 PointType;
typedef KernelType::Line_2 LineType;


PointType p(0.034,0.006);
cout<<"point -> "<<p<<endl;

LineType l(-0.004, 0.004, 0.000112);
cout<<"line -> "<<l<<endl;

CGAL::Oriented_side test = l.oriented_side(p);

if ( test == CGAL::ON_POSITIVE_SIDE ) {
cout<<"point on positive side"<<endl;
} else if ( test == CGAL::ON_NEGATIVE_SIDE ) {
cout<<"point on negative side"<<endl;
} else {
cout<<"point over line"<<endl;
}

return 0;
}

Result of the program:

$./a.out
point -> 0.034 0.006
line -> -0.004 0.004 0.000112
point on negative side


so where did the exact predicate stated in the kernel go??? Is this supposed to work like this? or this is finally a bug?

Alejandro M. Aragón


On Jul 23, 2008, at 12:02 PM, Sylvain Pion wrote:

Alejandro Aragon a écrit :
I see your point but as soon as you start using double precision, the "mathematical sense" is out of question, right?

That's the naive view. A double value has a real (exact) value
(except NaNs and infinities). That is a fact.
Most (if not all) CGAL algorithms are designed with the model that the
input is known exactly, and compute the exact answer. They are proved
in the literature in this model.

Defining computational geometry structures and algorithms in a fuzzy model
has been done for some problems in the literature, but it is way less
generally used in computational geometry, and CGAL does not support it so far.
And it is hard.

So that a < b is not true if they are within tolerance. Also, what is the chance that your algorithms encounter something like what you described, where in "mathematical sense" a < b < c and then you think CGAL has a bug because it's not giving you the answer you expect? Instead, if you use a type that is not exact, you would expect algorithms to behave with the same degree of "exactness". I guess that is what users would expect, at least that is what I expect. If they want a more exact predicate, then use an "exact" type.

Depends on your needs. How do you define this tolerance?
(note that interval arithmetic can be used with CGAL, but this is not double,
this is slower, but this gives guarantees).
Tell us more about your problem.

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss




Archive powered by MHonArc 2.6.16.

Top of Page