CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

If you have a patch I can review it and integrate it in CGAL.

Thanks,

Sebastien.

On 01/26/2012 10:56 PM, erickee wrote:
> I think that I have solved this problem.  In case there's a problem or anyone
> else needs this solution... here it is.
>
> Solution first.  Here is an example.  To create a Nef_polyhedron_2 that
> describes the first quadrant:
>    CGAL::Filtered_extended_homogeneous<int>  K;
>    typedef CGAL::Filtered_extended_homogeneous<int>::Point_2 Point_2;
>
>    Point_2 r1[4] = { K.construct_point(Point( 0, 0, 1) ),
>                            K.construct_point( Line( 0, 1, 0) ),
>                            K.construct_point( Line(-1, 1, 0) ),
>                            K.construct_point( Line(-1, 0, 0) )
>                          };
>
>    std::list<std::pair&lt;Point_2*,Point_2*>  >  polylines;
>    polylines.push_back(std::make_pair(r1+0, r1+4));
>    Nef_polyhedron RST(polylines.begin(), polylines.end(),
> Nef_polyhedron::POLYGONS);
>
> This code requires that you add an overloaded function to
> Filtered_extended_homogeneous.h
> At line 1053, there are a few construct_point() functions.  Add another:
>    Point_2 construct_point(const Point_2&  p) const
>    { return p; }
>
> Here is the code output:
> The face of the Nef_polyhedron_2, RST, is:
>    Edge 1: (0, 0, 1) --->  (1, 0, 0)
>    Edge 2: (1, 0, 0) --->  (1, 1, 0)
>    Edge 3: (1, 1, 0) --->  (0, 1, 0)
>    Edge 4: (0, 1, 0) --->  (0, 0, 1)
>
> This is the first quadrant.  This is also the same output that we would get
> if we had intersected two half-planes:
>    Edge 1: (0, 0, 1) --->  (1, 0, 0)
>    Edge 2: (1, 0, 0) --->  (1, 1, 0)
>    Edge 3: (1, 1, 0) --->  (0, 1, 0)
>    Edge 4: (0, 1, 0) --->  (0, 0, 1)
>    (code for this sanity check is below)
>
> There are two other faces that I did not print here and they also match
> between the solution and the sanity check.
>
>
> Why does this work?
>     -- Nef_polyhedron_2 knows how to construct points at infinity from lines
>
>     -- Nef_polyhedron_2 has public functions to construct points at infinity
> from lines
>
>     -- These construction functions return points of type Point_2
>
>     -- We can convert our points at infinity into lines
>            e.g. infinite point (1,1,0) corresponds to the homogeneous line
> (-1,1,0)
>
>     -- Therefore we can construct points of type Point_2 for our points at
> infinity
>
>     -- Nef_polyhedron_2 also has public functions to construct points of type
> Point_2 from standard points
>
>     -- So we can convert all points, whether standard or non-standard
> (infinite) to type Point_2
>
>     -- The polygon constructor for Nef_polyhedron_2 is generic and can accept
> type Point_2
>
>     -- The polygon constructor converts all points into type Point_2, anyway
>
>     -- So we convert our points to Point_2 and pass them to the Nef
> constructor
>
>
> Why add something to Nef_polyhedron_2.h?
>
>     -- The constructors in Nef_polyhedron_2 use convert all points to type
> Point_2
>
>     -- This is done by functions named construct_point()  (there are 2 or 3
> of these)
>
>     -- But, we already converted our points to Point_2
>
>     -- So we need add another overload of construct_point that constructs
> Point_2 into Point_2
>
>     -- The function we added does just that:
>            Point_2 construct_point(const Point_2&  p) const
>            { return p; }
>
>     -- Line 1053 in Nef_polyhedron_2.h is where the other construct_point
> functions are defined.
>
>
>
>
> Code for the sanity check:
>    typedef CGAL::Gmpz RT;
>    typedef CGAL::Filtered_extended_homogeneous<int>  Extended_kernel;
>    typedef CGAL::Nef_polyhedron_2<Extended_kernel>  Nef_polyhedron;
>    typedef Nef_polyhedron::Point Point;
>    typedef Nef_polyhedron::Line  Line;
>    typedef Nef_polyhedron::Direction Direction;
>    typedef Nef_polyhedron::Explorer Explorer;
>
>    // Intersect two half-planes to specify the first quadrant
>    Line ly(0, 1, 0);
>    Nef_polyhedron N1(ly,Nef_polyhedron::EXCLUDED);
>    Line lx(1, 0, 0);
>    Nef_polyhedron N2(lx,Nef_polyhedron::EXCLUDED);
>    Nef_polyhedron RST = N1.intersection(N2);
>
>
>
> --
> View this message in context: 
> http://cgal-discuss.949826.n4.nabble.com/Constructing-Nef-polyhedra-from-polygons-with-points-at-infinity-tp4327351p4331942.html
> Sent from the cgal-discuss mailing list archive at Nabble.com.