CGAL users discussion list

[Frédérik Paradis <>]

I made a mistake in the description of the calculation but the code is doing it correctly.

2016-02-26 8:47 GMT-05:00 Frédérik Paradis <>:

Thank you for your answer Sebastien.

There are several factors to take into account:
- would there be a significant speed up when using dimension specific implementation?
- can the implementation be made easily dimension generic?

The answer to the first question is no and the second is yes. So I guess I should just make a dimension generic implementation. However, since the CGAL::Ipelet_base class return instances of Point_2, I have to convert these instances into Point_d. Is there a way to do do that? Right now, I do something like that:

  Point_d point_2_to_point_d(Point_2 p) {
    return Point_d(CGAL::to_double(p.x()), CGAL::to_double(p.y()));
  }

  Point_2 point_d_to_point_2(Point_d p) {
    return Point_2(CGAL::to_double(p[0]), CGAL::to_double(p[1]));
  }

This class is not documented so it cannot appear in examples but it can
certainly be used in the implementation of algorithms of CGAL. Actually
it is even better to reuse something existing than creating an almost
identical duplicate. At the same time if you need some improvements
or new functions in this class they should be welcome.

Perfect.

I would need a more precise definition to answer correctly. However,
there is the traits Root_of_traits that depending on the number type
used will provide an exact representation of algebraic numbers of degree 2  when using an exact number type.

http://doc.cgal.org/latest/Number_types/classCGAL_1_1Root__of__traits.html

http://doc.cgal.org/latest/Number_types/classCGAL_1_1Sqrt__extension.html

So, let r_v and r_v be the radius of two circles v and w. We get r = max(r_v, r_w). Let d be the distance between the circles v and w. Let s be a constant greater than 0. We want to verify if d >= s*r.

Here is how I've done the calculation:

  bool are_well_separated(const Node* v, const Node* w) const  {
    Sphere_d cir_v = v->enclosing_circle();
    Sphere_d cir_w = w->enclosing_circle();
    FT max_rad =  CGAL::sqrt(std::max(cir_v.squared_radius(), cir_w.squared_radius()));
    FT distance_vw = CGAL::sqrt(CGAL::squared_distance(cir_v.center(), cir_w.center()));
    return (distance_vw - 2.*max_rad) > s*max_rad;
  }

I do not really understand how to use the two classes that mentionned.

Thank you for your answer.

Frédérik

2016-02-26 1:20 GMT-05:00 Sebastien Loriot (GeometryFactory) <>:

On 02/16/2016 03:24 PM, Frédérik Paradis wrote:

Hi everyone,

Hello Frédérik,

I'm currently developing a module for CGAL for the Well-separated pair
decomposition (WSPD) (See [1]). It is actually the first time I use CGAL
so I do not fully understand yet the overall architecture of CGAL. So I
have a couple of questions about how my module should work.

For now, I developed the WSPD with the Split tree in 2D using the class
Point_container.

I developed it in 2D first because I wanted to develop an Ipelet for
Ipe, but I want to develop it in d dimension. So, the first questions is
when do you do many module for 2, 3 and dimension and when do you do
only one module for d dimension?

There are several factors to take into account:
- would there be a significant speed up when using dimension specific implementation?
- can the implementation be made easily dimension generic?

I'm currently using the class Point_container which seems really tied
with the Kd-tree. Should I use that or implement the splitting part
myself? Also, this class take in a parameter an iterator of that typedef:

typedef std::vector<const Point_d*> Point_vector;

It seems contrary to the coding rules of CGAL which has led me to
believe it was more an internal class for the Split tree than anything else.

This class is not documented so it cannot appear in examples but it can
certainly be used in the implementation of algorithms of CGAL. Actually
it is even better to reuse something existing than creating an almost
identical duplicate. At the same time if you need some improvements
or new functions in this class they should be welcome.

Also, when computing the WSPD, it requires the comparison of the
distance between two circles and a factor times the radius of the two
circles. For now, I'm just using CGAL::to_double and the sqrt function.
Is there any other way a should do that?

I would need a more precise definition to answer correctly. However,
there is the traits Root_of_traits that depending on the number type
used will provide an exact representation of algebraic numbers of degree 2  when using an exact number type.

http://doc.cgal.org/latest/Number_types/classCGAL_1_1Root__of__traits.html

http://doc.cgal.org/latest/Number_types/classCGAL_1_1Sqrt__extension.html

Sebastien.

That's all for my questions but I will surely have more later.

Thank you.

Frédérik


[1] http://people.scs.carleton.ca/~michiel/aa-handbook.pdf

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