point lying over a line problem

classic Classic list List threaded Threaded
31 messages Options
12
Reply | Threaded
Open this post in threaded view
|

point lying over a line problem

aaragon
Hi, no one has replied to my post yet, so I decided to send it again  
in case someone will. I'm trying to check how the oriented_side()  
function works for a line. I
created a very simple example, where a point should lie on a line, but  
it
doesn't. The program is as follows:

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

using std::cout;
using std::endl;

int main() {

typedef CGAL::Cartesian<double> 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;
}

The output of this little program is:

point -> 0.034 0.006
line -> -0.004 0.004 0.000112
point on negative side

Can someone tell me what is happening here? The point should not be on  
the
negative side. Thank you all.
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

Sylvain Pion
Administrator
Alejandro Aragon a écrit :
> Hi, no one has replied to my post yet, so I decided to send it again in
> case someone will.

Wrong decision : you should have decided to read the FAQ, for example.


> I'm trying to check how the oriented_side() function
> works for a line. I
> created a very simple example, where a point should lie on a line, but it
> doesn't. The program is as follows:
>
> #include <CGAL/Cartesian.h>
> #include <iostream>
>
> using std::cout;
> using std::endl;
>
> int main() {
>
> typedef CGAL::Cartesian<double> 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;
> }
>
> The output of this little program is:
>
> point -> 0.034 0.006
> line -> -0.004 0.004 0.000112
> point on negative side
>
> Can someone tell me what is happening here? The point should not be on the
> negative side. Thank you all.

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/


smime.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

Olivier Devillers
In reply to this post by aaragon
Alejandro Aragon a écrit :
> typedef CGAL::Cartesian<double> KernelType;

If you compute with double, rounding errors make your points non collinear
(e.g. during the decimal to binary conversion if your input is given by
floating point number in decimal notation)

http://www.cgal.org/FAQ.html#inexact_NT
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

andreas.fabri
In reply to this post by Sylvain Pion
Sylvain Pion wrote:
> Alejandro Aragon a écrit :
>> Hi, no one has replied to my post yet, so I decided to send it again
>> in case someone will.
>
> Wrong decision : you should have decided to read the FAQ, for example.

http://www.cgal.org/FAQ.html#inexact_NT

>
>
>> I'm trying to check how the oriented_side() function works for a line. I
>> created a very simple example, where a point should lie on a line, but it
>> doesn't. The program is as follows:
>>
>> #include <CGAL/Cartesian.h>
>> #include <iostream>
>>
>> using std::cout;
>> using std::endl;
>>
>> int main() {
>>
>> typedef CGAL::Cartesian<double> 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;
>> }
>>
>> The output of this little program is:
>>
>> point -> 0.034 0.006
>> line -> -0.004 0.004 0.000112
>> point on negative side
>>
>> Can someone tell me what is happening here? The point should not be on
>> the
>> negative side. Thank you all.
>
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

aaragon
In reply to this post by Sylvain Pion
There is nothing in the FAQ that prevents people from reposting a  
message, thanks for your helpful reply.

On Jul 23, 2008, at 10:38 AM, Sylvain Pion wrote:

> Alejandro Aragon a écrit :
>> Hi, no one has replied to my post yet, so I decided to send it  
>> again in case someone will.
>
> Wrong decision : you should have decided to read the FAQ, for example.
>
>
>> I'm trying to check how the oriented_side() function works for a  
>> line. I
>> created a very simple example, where a point should lie on a line,  
>> but it
>> doesn't. The program is as follows:
>> #include <CGAL/Cartesian.h>
>> #include <iostream>
>> using std::cout;
>> using std::endl;
>> int main() {
>> typedef CGAL::Cartesian<double> 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;
>> }
>> The output of this little program is:
>> point -> 0.034 0.006
>> line -> -0.004 0.004 0.000112
>> point on negative side
>> Can someone tell me what is happening here? The point should not be  
>> on the
>> negative side. Thank you all.
>
>
> --
> 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
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

aaragon
In reply to this post by Olivier Devillers
Thanks for replying, I actually read the FAQ before posting my message  
and I understand that the double type is inexact. However, I don't see  
why the need of using an "exact" number type when algorithms can be  
modified such that they give exact results within tolerance. If a  
double precision type is exact up to the 15th digit, then algorithms  
should take that into account so when I try to intersect that point  
with the line, the point is supposed to lie over the line within let's  
say tol = 10e-14.

Why would I use an exact number type? I don't want to do that, it will  
slow down a program that I'm actually trying to speed up by doing some  
profiling.

Alejandro M. Aragón

On Jul 23, 2008, at 10:42 AM, Olivier Devillers wrote:

> Alejandro Aragon a écrit :
>> typedef CGAL::Cartesian<double> KernelType;
>
> If you compute with double, rounding errors make your points non  
> collinear
> (e.g. during the decimal to binary conversion if your input is given  
> by
> floating point number in decimal notation)
>
> http://www.cgal.org/FAQ.html#inexact_NT
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

Fernando Cacciola-3
Hi Alejandro,

> the point is supposed to lie over the line within let's
> say tol = 10e-14.
>
This is an arbitrary interpretation of what lying over a line means.
If this interpretation works in you particular case, you can implement it easily
via the squared_distance() function, but have in mind that your sample point
miught not actually lie on the line in spite of the number type used.
That is, you will get the wrong answer for using plain double, but you could
also be just expecting the opposite answer because you asummed closed enough is
the same as exactly on the line.  CGAL predicates are strictly exact: they
return the answer they would if you used an exact number type.

> Why would I use an exact number type?

You wouldn't.
Please read the FAQ much more carefully, in particular de paragraph starting
with:

 "If your program does not involve the construction of new objects from the
input data..."

CGAL uses a technique knows as "Floating-point filtering" which exploits the
precision of 'double' as much as possible yet it guarrantees correct results
even when that precision is detected as not being enough for a particular
operation.

HTH

Fernando Cacciola
www.geometryfactory.com

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

aaragon
In reply to this post by andreas.fabri
By the way, talking about points in CGAL. I decided to create my own  
point class, templated by the dimension of the point to see the  
difference in creation time with that of the CGAL types. I introduced  
an implicit conversion so that I can use my point type where a CGAL  
algorithm needs it. Then my test was just creating points. It was  
surprising the time that it took the creation of 10e9 Point_2 objects  
compared to my simple templated point class:

int main(int argc, char *argv[]) {

        typedef CGAL::Point_2 PointType;

        Timer t1;
        cout<<"CGAL point"<<endl;
        t1.Reset();
        for (long i=0; i<1.0e9; ++i) {
                PointType p(3,5);
        }
        t1.Tac();
        cout<<"my point"<<endl;
        t1.Reset();
        for (long i=0; i<1.0e9; ++i) {
                geometry::Point<2> p(3,5);
        }
        t1.Tac();

        exit(0);
}

$./a.out
CGAL point
Time: 74.2738sec
Measurement granularity: 1000000 of a second
my point
Time: 1.57362sec
Measurement granularity: 1000000 of a second

so can someone tell me why is this? I would never expect an almost  
factor of 50 in execution times! and this was just for creating a point.

Alejandro M. Aragón


On Jul 23, 2008, at 10:48 AM, Andreas Fabri wrote:

> Sylvain Pion wrote:
>> Alejandro Aragon a écrit :
>>> Hi, no one has replied to my post yet, so I decided to send it  
>>> again in case someone will.
>> Wrong decision : you should have decided to read the FAQ, for  
>> example.
>
> http://www.cgal.org/FAQ.html#inexact_NT
>
>>> I'm trying to check how the oriented_side() function works for a  
>>> line. I
>>> created a very simple example, where a point should lie on a line,  
>>> but it
>>> doesn't. The program is as follows:
>>>
>>> #include <CGAL/Cartesian.h>
>>> #include <iostream>
>>>
>>> using std::cout;
>>> using std::endl;
>>>
>>> int main() {
>>>
>>> typedef CGAL::Cartesian<double> 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;
>>> }
>>>
>>> The output of this little program is:
>>>
>>> point -> 0.034 0.006
>>> line -> -0.004 0.004 0.000112
>>> point on negative side
>>>
>>> Can someone tell me what is happening here? The point should not  
>>> be on the
>>> negative side. Thank you all.
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

Olivier Devillers
In reply to this post by aaragon
YOU are using a non exact number type, your input (after rounding) is
not collinear
the code answer they are not collinear.
It seems perfect behavior.

Alejandro Aragon a écrit :
> Why would I use an exact number type?
read the CGAL philosophy page,
read the papers referenced by the FAQ
>> http://www.cgal.org/FAQ.html#inexact_NT\

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

Fernando Cacciola-3
In reply to this post by aaragon
Hi Alejandro,


> so can someone tell me why is this? I would never expect an almost
> factor of 50 in execution times! and this was just for creating a point.
>
The Cartesian<> kernel uses reference counted objects (including Point objects).
Use Simple_cartesian<double> instead.

Also, benchmarking code is a very tricky bussiness and small details can make a
lot of difference. At the very least, interleave and repeat each loop a number
of times and report the average.

HTH

Fernando Cacciola
www.geometryfactory.com

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

Sylvain Pion
Administrator
In reply to this post by aaragon
Alejandro Aragon a écrit :

> By the way, talking about points in CGAL. I decided to create my own
> point class, templated by the dimension of the point to see the
> difference in creation time with that of the CGAL types. I introduced an
> implicit conversion so that I can use my point type where a CGAL
> algorithm needs it. Then my test was just creating points. It was
> surprising the time that it took the creation of 10e9 Point_2 objects
> compared to my simple templated point class:
>
> int main(int argc, char *argv[]) {
>
>     typedef CGAL::Point_2 PointType;
>
>     Timer t1;
>     cout<<"CGAL point"<<endl;
>     t1.Reset();
>     for (long i=0; i<1.0e9; ++i) {
>         PointType p(3,5);
>     }
>     t1.Tac();
>     cout<<"my point"<<endl;
>     t1.Reset();
>     for (long i=0; i<1.0e9; ++i) {
>         geometry::Point<2> p(3,5);
>     }
>     t1.Tac();
>
>     exit(0);
> }
>
> $./a.out
> CGAL point
> Time: 74.2738sec
> Measurement granularity: 1000000 of a second
> my point
> Time: 1.57362sec
> Measurement granularity: 1000000 of a second
>
> so can someone tell me why is this? I would never expect an almost
> factor of 50 in execution times! and this was just for creating a point.

Cartesian<> uses reference-counting, which obviously shows-up
in such a synthetic benchmark.
Try to compare with Simple_cartesian maybe?

--
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
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

andreas.fabri
In reply to this post by aaragon
Hi Alejandro,

Cartesian has reference counted objects. You might try Simple_cartesian instead.

Best regards,

andreas



Alejandro Aragon wrote:

> By the way, talking about points in CGAL. I decided to create my own
> point class, templated by the dimension of the point to see the
> difference in creation time with that of the CGAL types. I introduced an
> implicit conversion so that I can use my point type where a CGAL
> algorithm needs it. Then my test was just creating points. It was
> surprising the time that it took the creation of 10e9 Point_2 objects
> compared to my simple templated point class:
>
> int main(int argc, char *argv[]) {
>
>     typedef CGAL::Point_2 PointType;
>
>     Timer t1;
>     cout<<"CGAL point"<<endl;
>     t1.Reset();
>     for (long i=0; i<1.0e9; ++i) {
>         PointType p(3,5);
>     }
>     t1.Tac();
>     cout<<"my point"<<endl;
>     t1.Reset();
>     for (long i=0; i<1.0e9; ++i) {
>         geometry::Point<2> p(3,5);
>     }
>     t1.Tac();
>
>     exit(0);
> }
>
> $./a.out
> CGAL point
> Time: 74.2738sec
> Measurement granularity: 1000000 of a second
> my point
> Time: 1.57362sec
> Measurement granularity: 1000000 of a second
>
> so can someone tell me why is this? I would never expect an almost
> factor of 50 in execution times! and this was just for creating a point.
>
> Alejandro M. Aragón
>
>
> On Jul 23, 2008, at 10:48 AM, Andreas Fabri wrote:
>
>> Sylvain Pion wrote:
>>> Alejandro Aragon a écrit :
>>>> Hi, no one has replied to my post yet, so I decided to send it again
>>>> in case someone will.
>>> Wrong decision : you should have decided to read the FAQ, for example.
>>
>> http://www.cgal.org/FAQ.html#inexact_NT
>>
>>>> I'm trying to check how the oriented_side() function works for a
>>>> line. I
>>>> created a very simple example, where a point should lie on a line,
>>>> but it
>>>> doesn't. The program is as follows:
>>>>
>>>> #include <CGAL/Cartesian.h>
>>>> #include <iostream>
>>>>
>>>> using std::cout;
>>>> using std::endl;
>>>>
>>>> int main() {
>>>>
>>>> typedef CGAL::Cartesian<double> 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;
>>>> }
>>>>
>>>> The output of this little program is:
>>>>
>>>> point -> 0.034 0.006
>>>> line -> -0.004 0.004 0.000112
>>>> point on negative side
>>>>
>>>> Can someone tell me what is happening here? The point should not be
>>>> on the
>>>> negative side. Thank you all.
>>
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

andreas.fabri
In reply to this post by aaragon

tolerant algorithms are difficult to implement correctly.
Imagine you do 1D geometry, and decide that points (numbers)
are equal if they only differ on the 15th digit.

Imagine a < b < c  in the mathematical sense, and  positioned
in a way that a ~ b and b ~ c, but  a !~ c then  your algorithms
on top of the  equality test of points must be written with
the assumption that your equality test is not transitive.


andreas

Alejandro Aragon wrote:

> Thanks for replying, I actually read the FAQ before posting my message
> and I understand that the double type is inexact. However, I don't see
> why the need of using an "exact" number type when algorithms can be
> modified such that they give exact results within tolerance. If a double
> precision type is exact up to the 15th digit, then algorithms should
> take that into account so when I try to intersect that point with the
> line, the point is supposed to lie over the line within let's say tol =
> 10e-14.
>
> Why would I use an exact number type? I don't want to do that, it will
> slow down a program that I'm actually trying to speed up by doing some
> profiling.
>
> Alejandro M. Aragón
>
> On Jul 23, 2008, at 10:42 AM, Olivier Devillers wrote:
>
>> Alejandro Aragon a écrit :
>>> typedef CGAL::Cartesian<double> KernelType;
>>
>> If you compute with double, rounding errors make your points non
>> collinear
>> (e.g. during the decimal to binary conversion if your input is given by
>> floating point number in decimal notation)
>>
>> http://www.cgal.org/FAQ.html#inexact_NT
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

aaragon
I see your point but as soon as you start using double precision, the  
"mathematical sense" is out of question, right? 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.

Alejandro M. Aragón

On Jul 23, 2008, at 11:25 AM, Andreas Fabri wrote:

>
> tolerant algorithms are difficult to implement correctly.
> Imagine you do 1D geometry, and decide that points (numbers)
> are equal if they only differ on the 15th digit.
>
> Imagine a < b < c  in the mathematical sense, and  positioned
> in a way that a ~ b and b ~ c, but  a !~ c then  your algorithms
> on top of the  equality test of points must be written with
> the assumption that your equality test is not transitive.
>
>
> andreas
>
> Alejandro Aragon wrote:
>> Thanks for replying, I actually read the FAQ before posting my  
>> message and I understand that the double type is inexact. However,  
>> I don't see why the need of using an "exact" number type when  
>> algorithms can be modified such that they give exact results within  
>> tolerance. If a double precision type is exact up to the 15th  
>> digit, then algorithms should take that into account so when I try  
>> to intersect that point with the line, the point is supposed to lie  
>> over the line within let's say tol = 10e-14.
>> Why would I use an exact number type? I don't want to do that, it  
>> will slow down a program that I'm actually trying to speed up by  
>> doing some profiling.
>> Alejandro M. Aragón
>> On Jul 23, 2008, at 10:42 AM, Olivier Devillers wrote:
>>> Alejandro Aragon a écrit :
>>>> typedef CGAL::Cartesian<double> KernelType;
>>>
>>> If you compute with double, rounding errors make your points non  
>>> collinear
>>> (e.g. during the decimal to binary conversion if your input is  
>>> given by
>>> floating point number in decimal notation)
>>>
>>> http://www.cgal.org/FAQ.html#inexact_NT
>>> --
>>> You are currently subscribed to cgal-discuss.
>>> To unsubscribe or access the archives, go to
>>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

aaragon
In reply to this post by andreas.fabri
Indeed that made the difference, using simple cartesian gave:

$./a.out
Time: 1.5705sec
Measurement granularity: 1000000 of a second
Time: 1.56849sec
Measurement granularity: 1000000 of a second

so I guess it's the same. Now, why would you use reference counting  
for such a small type??? Let's say you use double precision Point_2  
types, you would need 64 bits to represent the x and y coordinates and  
then half of that to keep track of the storage???? Isn't that  
something silly to do? I would expect using reference counting in  
objects that require a large amount of storage (the std::string class  
for example, even though I believe that even that class is not using  
reference counting). If you allocate 100 different points, 33% of your  
memory goes away in using pointers!!!

I guess that Cartesian uses objects that really need reference  
counting, but I don't think that the Point_2 should be one of them.  
Then users of the library who didn't bother to go over the entire  
documentation (like me) think that Cartesian is their best candidate,  
when it is not.

Alejandro M. Aragón

On Jul 23, 2008, at 11:20 AM, Andreas Fabri wrote:

> Hi Alejandro,
>
> Cartesian has reference counted objects. You might try  
> Simple_cartesian instead.
>
> Best regards,
>
> andreas
>
>
>
> Alejandro Aragon wrote:
>> By the way, talking about points in CGAL. I decided to create my  
>> own point class, templated by the dimension of the point to see the  
>> difference in creation time with that of the CGAL types. I  
>> introduced an implicit conversion so that I can use my point type  
>> where a CGAL algorithm needs it. Then my test was just creating  
>> points. It was surprising the time that it took the creation of  
>> 10e9 Point_2 objects compared to my simple templated point class:
>> int main(int argc, char *argv[]) {
>>    typedef CGAL::Point_2 PointType;
>>    Timer t1;
>>    cout<<"CGAL point"<<endl;
>>    t1.Reset();
>>    for (long i=0; i<1.0e9; ++i) {
>>        PointType p(3,5);
>>    }
>>    t1.Tac();
>>    cout<<"my point"<<endl;
>>    t1.Reset();
>>    for (long i=0; i<1.0e9; ++i) {
>>        geometry::Point<2> p(3,5);
>>    }
>>    t1.Tac();
>>    exit(0);
>> }
>> $./a.out
>> CGAL point
>> Time: 74.2738sec
>> Measurement granularity: 1000000 of a second
>> my point
>> Time: 1.57362sec
>> Measurement granularity: 1000000 of a second
>> so can someone tell me why is this? I would never expect an almost  
>> factor of 50 in execution times! and this was just for creating a  
>> point.
>> Alejandro M. Aragón
>> On Jul 23, 2008, at 10:48 AM, Andreas Fabri wrote:
>>> Sylvain Pion wrote:
>>>> Alejandro Aragon a écrit :
>>>>> Hi, no one has replied to my post yet, so I decided to send it  
>>>>> again in case someone will.
>>>> Wrong decision : you should have decided to read the FAQ, for  
>>>> example.
>>>
>>> http://www.cgal.org/FAQ.html#inexact_NT
>>>
>>>>> I'm trying to check how the oriented_side() function works for a  
>>>>> line. I
>>>>> created a very simple example, where a point should lie on a  
>>>>> line, but it
>>>>> doesn't. The program is as follows:
>>>>>
>>>>> #include <CGAL/Cartesian.h>
>>>>> #include <iostream>
>>>>>
>>>>> using std::cout;
>>>>> using std::endl;
>>>>>
>>>>> int main() {
>>>>>
>>>>> typedef CGAL::Cartesian<double> 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;
>>>>> }
>>>>>
>>>>> The output of this little program is:
>>>>>
>>>>> point -> 0.034 0.006
>>>>> line -> -0.004 0.004 0.000112
>>>>> point on negative side
>>>>>
>>>>> Can someone tell me what is happening here? The point should not  
>>>>> be on the
>>>>> negative side. Thank you all.
>>>
>>> --
>>> You are currently subscribed to cgal-discuss.
>>> To unsubscribe or access the archives, go to
>>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

Sylvain Pion
Administrator
Alejandro Aragon a écrit :

> Indeed that made the difference, using simple cartesian gave:
>
> $./a.out
> Time: 1.5705sec
> Measurement granularity: 1000000 of a second
> Time: 1.56849sec
> Measurement granularity: 1000000 of a second
>
> so I guess it's the same. Now, why would you use reference counting for
> such a small type??? Let's say you use double precision Point_2 types,
> you would need 64 bits to represent the x and y coordinates and then
> half of that to keep track of the storage???? Isn't that something silly
> to do? I would expect using reference counting in objects that require a
> large amount of storage (the std::string class for example, even though
> I believe that even that class is not using reference counting). If you
> allocate 100 different points, 33% of your memory goes away in using
> pointers!!!
>
> I guess that Cartesian uses objects that really need reference counting,
> but I don't think that the Point_2 should be one of them. Then users of
> the library who didn't bother to go over the entire documentation (like
> me) think that Cartesian is their best candidate, when it is not.

Historical artefact, I owuld say (like many things in CGAL you may find strange).

Had you gone a bit at the documentation, you would not have used Cartesian
or Simple_cartesian at all, maybe.

Also, keep in mind that the primary goal of CGAL's kernels is to support
the higher level geometric algorithms, which have specific requirements
e.g. in terms of robustness.

We still don't know what you do with your points :-)

--
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
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

Hoffmann  Michael
In reply to this post by aaragon
> if you use a type that is not exact, you would expect algorithms to
> behave with the same degree of "exactness".

would be very nice, indeed... Unfortunately, this does not work so
easily with combinatorial algorithms based on binary decisions. If the
answer is yes or no, you either get it right or you don't. There's no
almost...

/Michael
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

Sylvain Pion
Administrator
In reply to this post by aaragon
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
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

Fernando Cacciola-3
In reply to this post by aaragon
Hi Alejandro,

> I see your point but as soon as you start using double precision, the
> "mathematical sense" is out of question, right? So that a < b is not
> true if they are within tolerance.
There is a, say, tolerance-based school of flaoting point programming which
works very well in several fields like computer graphics, simulations, numerical
analysis, etc, but just doesn't work in geometric computing as it depends on
(discrete) combinatorial properties.
You might find further insight reading the following usenet discussion on the
subject:

http://tinyurl.com/694x7g

HTH

Fernando Cacciola
www.geometryfactory.com



--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: point lying over a line problem

aaragon
In reply to this post by Sylvain Pion
Naive???? Try to represent 0.1 exactly using a double precision type!  
Then you'll realize that as soon as you start using an inexact type,  
the strict "mathematical sense" Andreas was talking about really goes  
away...

I write a GFEM library and as you may know, as soon as you don't use  
standard FEM you need heavy computation involving geometry. A library  
should be written in a way that naive users as me (as you pointed out)  
would expect a point (usually represented by double types) to lie on  
top of a line within the same tolerance as the inexact type.

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

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
12