Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] surface of a polyhedron embedded on the sphere

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] surface of a polyhedron embedded on the sphere


Chronological Thread 
  • From: "Sebastien Loriot (GeometryFactory)" <>
  • To:
  • Subject: Re: [cgal-discuss] surface of a polyhedron embedded on the sphere
  • Date: Mon, 11 Jul 2011 11:43:35 +0200

Francois Berenger wrote:
On 07/11/2011 03:58 PM, Sebastien Loriot (GeometryFactory) wrote:
Your question is not clear to me. Can you elaborate?

Hello,

1) I would like to know if it is possible to compute the surface
of a Nef polyhedra (I guess yes).
I don't need the exact procedure in fact, but for sure it would
educate me even if some CGAL expert just gives a rough idea.
This code is used to compute the Nef_3 boolean operations for example,
so it is working. I never try to use it with an inexact construction
kernel so I have no idea whether you could use it with such a kernel
(this is not possible for Nef_3 for example)


2) I'd like to have an idea of the complexity of the procedure
(O(n**something)?) to assess if it is worth doing with CGAL
or if an approximation of it would be faster.
This is computing an arrangement of great circle arcs on a sphere.
If I remember correctly, it is using two sweep algorithms, so the theoretical complexity should be something like O( (n+k)log(n) ) n being
the number of input and k the number of intersection points.

Note that there exists an experimental implementation using the CGAL
2D arrangement package doing something similar.
See this paper for example:
http://www.cs.tau.ac.il/~efif/publications/sphere_vor/sphere_vor.pdf

Sebastien.


Regards,
F.

Sebastien.


Francois Berenger wrote:
Hello,

Is it possible to compute the surface
of the selected region as can be seen in
the right hand part of figure Figure 21.1 from
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Nef_S2/Chapter_main.html


Let's say we have N triangles on the sphere, would it be
computationally intensive?

Regards,
F.










Archive powered by MHonArc 2.6.16.

Top of Page