CGAL users discussion list

[Efi Fogel <>]

You can use 2D Arrangements.

Here is one way to accomplish the task you describe (perhaps not the most efficient one though---see below for an alternative).

Extend the face type of the arrangement DCEL type with a boolean flag that indicates whether the point set associated with the face is in the intersection.

Construct as many arrangements as lines and for each arrangement mark the (unbounded) face associated with the halfplane defined by the line.

Overlay pairs of arrangements until you are left with the final one. Use an overlay traits that has the method that handles overlapping faces defined to set the flag of the resulting face based on the flags of the two faces of the overlapping faces.

Another way, which might be more efficient, but is a bit more complicated follows.

Extend the face with an integer that counts the number of covering halfplanes.

Insert the lines into the arrangement.

Initialize the counters of all faces to -infinity.

Traverse the arrangement start with a random face. Set the counter of the face to zero.
When you cross an edge examine the direction of the halfedge and the direction of the line associated with the halfedge. Based on the directions figure out whether you enter a halfplane or exit one and increase or decrease the counter, respectively.

If you have overlapping lines you may either pre-process them (sort them according to their slopes), or also extend the halfedge with a flag that counts, say the net number of lines oriented from left to right.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On 29 April 2018 at 01:48, houes <> wrote:

Dear Efi,

Hello. I basically want to do the halfplane intersection either in 2D or 3D
(in 2D, I have a set of oriented lines, in 3D, I have a set of oriented
planes).

In 3D, I have used CGAL::halfspace_intersection_3() to do halfplane
intersections of a set of planes(all planes pass through the Origin and I
add a cap plane to get a closed polyhedra).

My problem can be also solved in 2D: I intersect each of my 3D planes with
one fixed plane Z=1, and I get a set of oriented 2D line, each of these line
define a halfplane. And the halfplanes intersection of these lines give the
result I want: a convex polyhedon.

The problem is no matter I do 2D or 3D, the polyhedron or polyhedra resulted
from halfplane intersection is not necessarily closed: unbounded either in
2D or 3D. Thus the CGAL::halfspace_intersection_3() will throw exception: no
intersection found. After some research, I found the Nef_polyhedron is the
solution: it deal with polyhegon that can be open. Therefore, I want to
convert my lines/planes to Nef_polyhegron::Line or Nef_polyhegron::Plane to
do the intersection, which is equivalently the halfplane intersectin.

The problem I found with Nef_polyhegron is that there is no documentation
that tell me how to use Real number type instead of integer. All my data is
stored in Epick and use double coordinates. Therefore, if would be great if
you can provide me with some clue on this so I can utilize Nef_polyhedron
either in 2D or 3D using the data from Epick.

The solution provided by Adrien Lefieux works for me, but I have problem
converting data from Epick to Nef_polyhedron::Point or Nef_polyhedron::Line,
do you have a solution?

Thank you very much.

houes

--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

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