
12

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 cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss

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 SophiaAntipolis
Geometrica ProjectTeam
CGAL, http://cgal.org/


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 cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


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 cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


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 SophiaAntipolis
> Geometrica ProjectTeam
> CGAL, http://cgal.org/>

You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


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 = 10e14.
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 cgaldiscuss.
> To unsubscribe or access the archives, go to
> https://listssop.inria.fr/wws/info/cgaldiscuss
You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


Hi Alejandro,
> the point is supposed to lie over the line within let's
> say tol = 10e14.
>
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 "Floatingpoint 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 cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


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 cgaldiscuss.
> To unsubscribe or access the archives, go to
> https://listssop.inria.fr/wws/info/cgaldiscuss
You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


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 cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


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 cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss

Administrator

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 referencecounting, which obviously showsup
in such a synthetic benchmark.
Try to compare with Simple_cartesian maybe?

Sylvain Pion
INRIA SophiaAntipolis
Geometrica ProjectTeam
CGAL, http://cgal.org/
You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


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 cgaldiscuss.
>> To unsubscribe or access the archives, go to
>> https://listssop.inria.fr/wws/info/cgaldiscuss>

You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


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 =
> 10e14.
>
> 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 cgaldiscuss.
>> To unsubscribe or access the archives, go to
>> https://listssop.inria.fr/wws/info/cgaldiscuss>

You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


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 = 10e14.
>> 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 cgaldiscuss.
>>> To unsubscribe or access the archives, go to
>>> https://listssop.inria.fr/wws/info/cgaldiscuss>
> 
> You are currently subscribed to cgaldiscuss.
> To unsubscribe or access the archives, go to
> https://listssop.inria.fr/wws/info/cgaldiscuss
You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


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 cgaldiscuss.
>>> To unsubscribe or access the archives, go to
>>> https://listssop.inria.fr/wws/info/cgaldiscuss>
> 
> You are currently subscribed to cgaldiscuss.
> To unsubscribe or access the archives, go to
> https://listssop.inria.fr/wws/info/cgaldiscuss
You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss

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 SophiaAntipolis
Geometrica ProjectTeam
CGAL, http://cgal.org/
You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


> 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 cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss

Administrator

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 SophiaAntipolis
Geometrica ProjectTeam
CGAL, http://cgal.org/
You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


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, tolerancebased 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/694x7gHTH
Fernando Cacciola
www.geometryfactory.com

You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


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 SophiaAntipolis
> Geometrica ProjectTeam
> CGAL, http://cgal.org/> 
> You are currently subscribed to cgaldiscuss.
> To unsubscribe or access the archives, go to
> https://listssop.inria.fr/wws/info/cgaldiscuss
You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss

12
