a question about some basic algorithms

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

a question about some basic algorithms

Valdes, Julio
Dear Sirs:

First of all thank you for the formidable effort that represents the work around the CGAL library.
I am not an expert in computational geometry, but I need to use some basic algorithms and I have not been able to find my way through the documentation.
Please excuse me if my questions are too trivial for you.
The algorithms that I am interested in are related to convex hulls (in d > 3 dimensions):
1) distance from a point to a convex hull.
2) whether a point is inside/outside with respect to a given convex hull.

I would appreciate if you could direct me to the algorithms in CGAL that approach the aforementioned problems.
In case that there would not be available algorithms for the general case, references to lower dimension versions would be also helpful.
Any additional comments that you could provide, given your expertise in the domain would be greatly appreciated.
Sincerely

Julio J. Valdés
National Research Council Canada                                    | Conseil National de Recherches Canada
Digital Technologies Research Centre                               | Centre de Recherche en Technologies Numériques
Data Science for Complex Systems Group                        | Science des Données pour les Systèmes Complexes
M-50, 1200 Montreal Road, Ottawa, Ontario K1A 0R6 | M-50, 1200 chemin Montréal, Ottawa, Ontario K1A 0R6
Canada                                                                                     | Canada
[hidden email]
tel/tél: (1)613-993-0257

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


Reply | Threaded
Open this post in threaded view
|

Re: a question about some basic algorithms

Sebastien Loriot (GeometryFactory)
There might be a simpler and smarter way to do it but using the dD
triangulation package:

https://doc.cgal.org/latest/Triangulation

You should be able to know if a point location using the locate function:
https://doc.cgal.org/latest/Triangulation/classCGAL_1_1Triangulation.html#af9ea0ceb6cc5c814e4ed63738396a6b6

For the distance to the convex hull, I would first build the
triangulation, extract the vertices on the convex hull
(which are the set of vertices incident to the infinite vertex)
and build a triangulation out of those vertices.

Then doing locate queries, you will


Access the infinite_vertex() using:
https://doc.cgal.org/latest/Triangulation/classCGAL_1_1Triangulation.html#a44e3585e1b8fa31b718310a3f32a92af

Access dimension 1 incident cells (edges):
https://doc.cgal.org/latest/Triangulation/classTriangulationDataStructure.html#a9700c5ae4a6a2af65b002fb1057d47fa

Use the range of vertices in the cells (vertices_begin(),
vertices_end()) + to get the vertex of the edge that is not the infinite
one:
https://doc.cgal.org/latest/Triangulation/classTriangulationDataStructure_1_1FullCell.html


Note that Delaunay_triangulation inherits from Triangulation, that
itself inherits from the TriangulationDataStructure. The
doc of some methods are in the Triangulation or
TriangulationDataStructure doc only.

Sebastien.

On 10/25/19 5:10 PM, Valdes, Julio wrote:

> Dear Sirs:
>
> First of all thank you for the formidable effort that represents the work around the CGAL library.
> I am not an expert in computational geometry, but I need to use some basic algorithms and I have not been able to find my way through the documentation.
> Please excuse me if my questions are too trivial for you.
> The algorithms that I am interested in are related to convex hulls (in d > 3 dimensions):
> 1) distance from a point to a convex hull.
> 2) whether a point is inside/outside with respect to a given convex hull.
>
> I would appreciate if you could direct me to the algorithms in CGAL that approach the aforementioned problems.
> In case that there would not be available algorithms for the general case, references to lower dimension versions would be also helpful.
> Any additional comments that you could provide, given your expertise in the domain would be greatly appreciated.
> Sincerely
>
> Julio J. Valdés
> National Research Council Canada                                    | Conseil National de Recherches Canada
> Digital Technologies Research Centre                               | Centre de Recherche en Technologies Numériques
> Data Science for Complex Systems Group                        | Science des Données pour les Systèmes Complexes
> M-50, 1200 Montreal Road, Ottawa, Ontario K1A 0R6 | M-50, 1200 chemin Montréal, Ottawa, Ontario K1A 0R6
> Canada                                                                                     | Canada
> [hidden email]
> tel/tél: (1)613-993-0257
>

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


Reply | Threaded
Open this post in threaded view
|

RE: a question about some basic algorithms

Valdes, Julio
Hello Dr. Loriot:

Thank you very much for responding my email and for your valuable suggestions.
I shall follow your indications and see if I could produce an implementation of the solutions that you provided.
Once again, thank for your time and advice.
Best regards,
jjv

Julio J. Valdés
National Research Council Canada                                    | Conseil National de Recherches Canada
Digital Technologies Research Centre                               | Centre de Recherche en Technologies Numériques
Data Science for Complex Systems Group                        | Science des Données pour les Systèmes Complexes
M-50, 1200 Montreal Road, Ottawa, Ontario K1A 0R6 | M-50, 1200 chemin Montréal, Ottawa, Ontario K1A 0R6
Canada                                                                                     | Canada
[hidden email]
tel/tél: (1)613-993-0257

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On Behalf Of Sebastien Loriot (GeometryFactory)
Sent: Monday, October 28, 2019 5:05 AM
To: [hidden email]
Subject: Re: [cgal-discuss] a question about some basic algorithms

There might be a simpler and smarter way to do it but using the dD triangulation package:

https://doc.cgal.org/latest/Triangulation

You should be able to know if a point location using the locate function:
https://doc.cgal.org/latest/Triangulation/classCGAL_1_1Triangulation.html#af9ea0ceb6cc5c814e4ed63738396a6b6

For the distance to the convex hull, I would first build the triangulation, extract the vertices on the convex hull (which are the set of vertices incident to the infinite vertex) and build a triangulation out of those vertices.

Then doing locate queries, you will


Access the infinite_vertex() using:
https://doc.cgal.org/latest/Triangulation/classCGAL_1_1Triangulation.html#a44e3585e1b8fa31b718310a3f32a92af

Access dimension 1 incident cells (edges):
https://doc.cgal.org/latest/Triangulation/classTriangulationDataStructure.html#a9700c5ae4a6a2af65b002fb1057d47fa

Use the range of vertices in the cells (vertices_begin(),
vertices_end()) + to get the vertex of the edge that is not the infinite
one:
https://doc.cgal.org/latest/Triangulation/classTriangulationDataStructure_1_1FullCell.html


Note that Delaunay_triangulation inherits from Triangulation, that itself inherits from the TriangulationDataStructure. The doc of some methods are in the Triangulation or TriangulationDataStructure doc only.

Sebastien.

On 10/25/19 5:10 PM, Valdes, Julio wrote:

> Dear Sirs:
>
> First of all thank you for the formidable effort that represents the work around the CGAL library.
> I am not an expert in computational geometry, but I need to use some basic algorithms and I have not been able to find my way through the documentation.
> Please excuse me if my questions are too trivial for you.
> The algorithms that I am interested in are related to convex hulls (in d > 3 dimensions):
> 1) distance from a point to a convex hull.
> 2) whether a point is inside/outside with respect to a given convex hull.
>
> I would appreciate if you could direct me to the algorithms in CGAL that approach the aforementioned problems.
> In case that there would not be available algorithms for the general case, references to lower dimension versions would be also helpful.
> Any additional comments that you could provide, given your expertise in the domain would be greatly appreciated.
> Sincerely
>
> Julio J. Valdés
> National Research Council Canada                                    | Conseil National de Recherches Canada
> Digital Technologies Research Centre                               | Centre de Recherche en Technologies Numériques
> Data Science for Complex Systems Group                        | Science des Données pour les Systèmes Complexes
> M-50, 1200 Montreal Road, Ottawa, Ontario K1A 0R6 | M-50, 1200 chemin Montréal, Ottawa, Ontario K1A 0R6
> Canada                                                                                     | Canada
> [hidden email]
> tel/tél: (1)613-993-0257
>

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



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