Nef_polyhedron_2 with Epick kernel

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

Nef_polyhedron_2 with Epick kernel

houes
Hello. I encountered 2D polygons that are not closed. These polygons are
formed by the intersection of a set of oriented lines. And I want to
construct Nef_polyhedron_2 to represent them. So I can use the new
representation to do union operations among open/closed polygons.

The problem I found with Nef_polyhedron_2 is that it only support *integer*
construction.
What I want to do is define two lines, and define two Nef_Polygons using
these two lines, and do the intersection, just as in the sample
nef_2_intersection.cpp, but with *double number type*.
Suppose my lines are l1=(1.5, 2.4 , 3.1), l2=(-1.1, 2.3, 5.7). I have found
no way to represent them using Nef_polyhedron_2::Line, since in the example:

typedef CGAL::*Exact_integer *RT;
typedef CGAL::Filtered_extended_homogeneous<RT> Extended_kernel;
typedef CGAL::Nef_polyhedron_2<Extended_kernel> Nef_polyhedron;

only Exact_integer seems to work. I change this to CGAL::Gmpq,
CGAL::M_float, etc. all gives compiling error.

So is it that Nef_polygon only work with integer number type?  Since all my
lines, planes using Epick kernel, I really want Nef_polygon to work with
double coordinates.

I also checked the sample code in Nef_3/handling_double_coordinates.cpp,
however it needs to first define a CGAL::Polyhedron_3<Epeck>. In my case,
the intersections of my planes are open, I cannot obtain a Polyhedron_3
first, so this does not solve my problem.

Hope some one could help me.
Thank you very much.



--
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


Reply | Threaded
Open this post in threaded view
|

Re: Nef_polyhedron_2 with Epick kernel

aleph
Dear Houes,

I spent a couple of hours on this one.

The good news is that Nef_2 are not restricted to integers but it is not as straightforward as with Nef_3. You have to define the kernel yourself.

What I did was, something of the sort:

#include <CGAL/Gmpq.h>
#include <CGAL/Lazy_exact_nt.h>
#include <CGAL/Extended_cartesian.h>
#include <CGAL/Nef_polyhedron_2.h>

typedef CGAL::Extended_cartesian< CGAL::Lazy_exact_nt<CGAL::Gmpq> > Kernel;
//typedef CGAL::Extended_cartesian< CGAL::Lazy_exact_nt<CGAL::Quotient<CGAL::MP_Float> > > Kernel; // CGAL alternative without GMP

typedef CGAL::Nef_polyhedron_2<Kernel>   Nef_polyhedron;

...

  Point p1(0.0,0.0), p2(0.5,0.0), p3(0.0,0.5);
  Point triangle[3] = { p1, p2, p3 };
  Nef_polyhedron N(triangle, triangle+3);

...

I do not know if it is the most efficient method though, but it worked for me so far.

Best,
Adrien

Adrien Lefieux, PhD

Postdoctoral Fellow,

School of Medicine,

Department of Mathematics and Computer Science,
Emory University, Atlanta, USA


E-mail: [hidden email]emory.edu







On Fri, Apr 27, 2018 at 8:37 PM, houes <[hidden email]> wrote:
Hello. I encountered 2D polygons that are not closed. These polygons are
formed by the intersection of a set of oriented lines. And I want to
construct Nef_polyhedron_2 to represent them. So I can use the new
representation to do union operations among open/closed polygons.

The problem I found with Nef_polyhedron_2 is that it only support *integer*
construction.
What I want to do is define two lines, and define two Nef_Polygons using
these two lines, and do the intersection, just as in the sample
nef_2_intersection.cpp, but with *double number type*.
Suppose my lines are l1=(1.5, 2.4 , 3.1), l2=(-1.1, 2.3, 5.7). I have found
no way to represent them using Nef_polyhedron_2::Line, since in the example:

typedef CGAL::*Exact_integer *RT;
typedef CGAL::Filtered_extended_homogeneous<RT> Extended_kernel;
typedef CGAL::Nef_polyhedron_2<Extended_kernel> Nef_polyhedron;

only Exact_integer seems to work. I change this to CGAL::Gmpq,
CGAL::M_float, etc. all gives compiling error.

So is it that Nef_polygon only work with integer number type?  Since all my
lines, planes using Epick kernel, I really want Nef_polygon to work with
double coordinates.

I also checked the sample code in Nef_3/handling_double_coordinates.cpp,
however it needs to first define a CGAL::Polyhedron_3<Epeck>. In my case,
the intersections of my planes are open, I cannot obtain a Polyhedron_3
first, so this does not solve my problem.

Hope some one could help me.
Thank you very much.



--
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



Reply | Threaded
Open this post in threaded view
|

Re: Nef_polyhedron_2 with Epick kernel

Efi Fogel
What are you trying to do?
Why have you chosen to use 2D Nef to start with?

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



On 28 April 2018 at 16:10, Adrien Lefieux <[hidden email]> wrote:
Dear Houes,

I spent a couple of hours on this one.

The good news is that Nef_2 are not restricted to integers but it is not as straightforward as with Nef_3. You have to define the kernel yourself.

What I did was, something of the sort:

#include <CGAL/Gmpq.h>
#include <CGAL/Lazy_exact_nt.h>
#include <CGAL/Extended_cartesian.h>
#include <CGAL/Nef_polyhedron_2.h>

typedef CGAL::Extended_cartesian< CGAL::Lazy_exact_nt<CGAL::Gmpq> > Kernel;
//typedef CGAL::Extended_cartesian< CGAL::Lazy_exact_nt<CGAL::Quotient<CGAL::MP_Float> > > Kernel; // CGAL alternative without GMP

typedef CGAL::Nef_polyhedron_2<Kernel>   Nef_polyhedron;

...

  Point p1(0.0,0.0), p2(0.5,0.0), p3(0.0,0.5);
  Point triangle[3] = { p1, p2, p3 };
  Nef_polyhedron N(triangle, triangle+3);

...

I do not know if it is the most efficient method though, but it worked for me so far.

Best,
Adrien

Adrien Lefieux, PhD

Postdoctoral Fellow,

School of Medicine,

Department of Mathematics and Computer Science,
Emory University, Atlanta, USA


E-mail: [hidden email]emory.edu







On Fri, Apr 27, 2018 at 8:37 PM, houes <[hidden email]> wrote:
Hello. I encountered 2D polygons that are not closed. These polygons are
formed by the intersection of a set of oriented lines. And I want to
construct Nef_polyhedron_2 to represent them. So I can use the new
representation to do union operations among open/closed polygons.

The problem I found with Nef_polyhedron_2 is that it only support *integer*
construction.
What I want to do is define two lines, and define two Nef_Polygons using
these two lines, and do the intersection, just as in the sample
nef_2_intersection.cpp, but with *double number type*.
Suppose my lines are l1=(1.5, 2.4 , 3.1), l2=(-1.1, 2.3, 5.7). I have found
no way to represent them using Nef_polyhedron_2::Line, since in the example:

typedef CGAL::*Exact_integer *RT;
typedef CGAL::Filtered_extended_homogeneous<RT> Extended_kernel;
typedef CGAL::Nef_polyhedron_2<Extended_kernel> Nef_polyhedron;

only Exact_integer seems to work. I change this to CGAL::Gmpq,
CGAL::M_float, etc. all gives compiling error.

So is it that Nef_polygon only work with integer number type?  Since all my
lines, planes using Epick kernel, I really want Nef_polygon to work with
double coordinates.

I also checked the sample code in Nef_3/handling_double_coordinates.cpp,
however it needs to first define a CGAL::Polyhedron_3<Epeck>. In my case,
the intersections of my planes are open, I cannot obtain a Polyhedron_3
first, so this does not solve my problem.

Hope some one could help me.
Thank you very much.



--
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




Reply | Threaded
Open this post in threaded view
|

Re: Nef_polyhedron_2 with Epick kernel

houes
In reply to this post by aleph
Dear Adrien,

Thank you very much! Your method works well for me!

A follow up question:

If I use the definition you provide:
/typedef CGAL::Extended_cartesian< CGAL::Lazy_exact_nt<CGAL::Gmpq> > Kernel;
typedef CGAL::Nef_polyhedron_2<Kernel>   Nef_polyhedron;
typedef Nef_polyhedron::Line  Line;
typedef Nef_polyhedron::Point Point;/

I notice I cannot convert from Kernel::Point_2 to Nef_polyhedron::Point or
Kernel::Line_2 to Nef_polyhedron::Line. It seems the point and line type are
different. If there any way to do the cast?

In fact, I am using Epick::Point_2 and Epick::Line_2, neither of them can be
directly assigned to Nef_polyhedron::Point or Nef_polyhedron::Line, I wonder
if any type cast can do the trick.

The reason I need to do the type cast is that all my data is in stored Epick
kernel and I need to transfer them into the Nef_polyhedron Kernel type to do
polygon union/intersection.

One last question, does your method also applies to Nef_polyhedron_3?

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


Reply | Threaded
Open this post in threaded view
|

Re: Nef_polyhedron_2 with Epick kernel

houes
In reply to this post by Efi Fogel
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


Reply | Threaded
Open this post in threaded view
|

Re: Nef_polyhedron_2 with Epick kernel

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 <[hidden email]> 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



Reply | Threaded
Open this post in threaded view
|

Re: Nef_polyhedron_2 with Epick kernel

houes
Dear Efi,

Thank you very much for providing the solution!

I kind of understood your first solution: the halfplane intersection is the
face that is on the positive direction of all lines in 2D arrangment. So in
each overlay, if the new face is on the negative side of any line, then it
is not in the intersection, otherwise the face is the intersection. Time
complexity is O(n*n) for arrangement, n is the number of lines.

I am not very clear with the second solution. But I guess the intersection
face should be the one with the highest count? Since when you are at the
intersection, you go to the highest place. The max count difference among
all faces is n (supposing we have n lines).

Both solution seem good to me. The only thing is that I am kind of new to
CGAL, and am not very familiar about how to define and use extend data
structure like the face in DCEL or the triats class. So I wonder if the
above solution has better performance than the Nef_polygon_2 data structure?
Since it looks like, Nef_2 can just do the intersection and save me some
time to write my own arraignment code.

Thank you.




--
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