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://cgaldiscuss.949826.n4.nabble.com/  You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss 
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:
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, 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 
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:

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://cgaldiscuss.949826.n4.nabble.com/  You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss 
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://cgaldiscuss.949826.n4.nabble.com/  You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss 
You can use 2D Arrangements. Here is one way to accomplish the task you describe (perhaps not the most efficient one thoughsee 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 preprocess 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, 
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://cgaldiscuss.949826.n4.nabble.com/  You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss 
Free forum by Nabble  Edit this page 