CGAL users discussion list

[Peter Hachenberger <>]

Here it is. I hope it works nicely.

Peter

On Wed, 2008-01-30 at 11:06 -0800, Stephen Wong wrote:
> Hi Peter,
> 
> I have found the call, that you have described, in Nef_polyhedron_3.h.  
> However one of the files that it requires, 
> CGAL/Nef_3/Combine_with_halfspace.h, is not included (at least not in my 
> version of CGAL).
> 
> Can you please provide this file?  I can only assume it was implemented but 
> not included because the functionality was not required.
> 
> Thank you!
> 
> Stephen
> 
> -----Original Message-----
> From: Peter Hachenberger 
> [mailto:]
> Sent: January-30-08 2:07 AM
> To: 
> 
> Subject: RE: [cgal-discuss] [Nef_polyhedron_3] Creation of half-planes
> 
> The function is only in CGAL 3.3.1. Just call
> 
> N = N.intersection(Plane_3(a,b,c,d));
> 
> Peter
> 
> On Wed, 2008-01-30 at 01:52 -0800, Stephen Wong wrote:
> > ________________________________________
> > From: Peter Hachenberger 
> > []
> > Sent: Wednesday, January 30, 2008 1:31 AM
> > To: 
> > 
> > Hi Peter,
> >
> > Thank you for your quick response. You are absolutely right - I am 
> > looking at performing an intersection with a half-plane.  Can you please 
> > let me know of this undocumented function? The fact that I won't need to 
> > switch to a another (slower) kernel for this functionality is pleasing to 
> > hear!
> >
> > Regards,
> >
> > Stephen
> >
> > Subject: Re: [cgal-discuss] [Nef_polyhedron_3] Creation of half-planes
> >
> > Hi Stephen,
> >
> > I somehow neglected the Extended_cartesian kernel for a while and
> > therefore it is not compiling at the current release. Usually nobody
> > uses the extended kernels, but recently somebody wanted to work with the
> > Extended_cartesian_kernel and I fixed it. So, if you want to use it, I
> > can send you 2-3 updated files that will fix the problems.
> >
> > Before you do that, I want to find out, whether you really need an
> > extended kernel. They are pretty slow and not often needed. In the
> > latest release there is an undocumented function that allows
> > intersection with a halfspace without constructing the halfspace
> > explicitly. If that is the only reason why you need halfspaces, then you
> > don't need the extended kernels.
> >
> > Thanks for the note on the Extended_XXX_3 kernels. That's an error. In
> > the beginning I thought I need separate kernels for different
> > dimensions, but that is not true. These kernels do not exist. Use
> > Extended_homogeneous and Extended_cartesian.
> >
> > Peter
> >
> > On Tue, 2008-01-29 at 18:03 -0800, Stephen Wong wrote:
> > > Hi there,
> > >
> > >
> > >
> > > Another quick question for you guys.  In Section 18.5.1 in the
> > > documentation where a Extended_homogeneous<Gmpz> kernel is used to
> > > demonstrate construction of Nef_polyhedron_3 using a half-plane
> > > definition, I tried the same with Extended_cartesian<Gmpq> but this
> > > did not work – compiler errors resulted.  This documentation is found
> > > here:
> > >
> > >
> > >
> > > http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Nef_3/Chapter_main.html#Subsection_18.5.1
> > >
> > >
> > >
> > > It is also note worthy to mention that in the reference to
> > > Nef_polyhedron_3, there is a reference to a Extended_homogeneous_3
> > > (presumably 3D version of the Extended homogeneous) and
> > > Extended_cartesian_3, but none of these two kernels seem to actually
> > > exist.  In the example of 18.5.1, the Extended_homogeneous (w/o “_3”)
> > >  is used to initialize a 3D plane in Nef_polyhedron_3 with success.
> > > What am I not doing correctly to obtain the same results with
> > > Extended_cartesian<Gmpq>?
> > >
> > >
> > >
> > > Thanks,
> > >
> > >
> > >
> > > Stephen
> > >
> > >
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://lists-sop.inria.fr/wws/info/cgal-discuss
> >
> 
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
> 
> -- 
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
// Copyright (c) 1997-2002  Max-Planck-Institute Saarbruecken (Germany).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESISGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh:///svn/cgal/trunk/Nef_3/include/CGAL/Nef_3/Combine_with_halfspace.h $
// $Id: Combine_with_halfspace.h 39612 2007-07-31 11:35:46Z hachenb $
// 
//
// Author(s)     : Michael Seel    <>
//                 Miguel Granados <>
//                 Susan Hert      <>
//                 Lutz Kettner    <>
#ifndef CGAL_COMBINE_WITH_HALFSPACE_H
#define CGAL_COMBINE_WITH_HALFSPACE_H

#include <CGAL/Nef_S2/Normalizing.h>
#include <CGAL/Unique_hash_map.h>
#include <CGAL/Nef_3/SNC_const_decorator.h>
#include <CGAL/Nef_S2/SM_decorator.h>
#include <CGAL/Nef_3/SNC_SM_overlayer.h>
#include <CGAL/Nef_3/SNC_constructor.h>
#include <CGAL/Nef_3/SNC_external_structure.h>
#include <CGAL/Nef_3/ID_support_handler.h>
#include <CGAL/Nef_3/Binary_operation.h>

#undef CGAL_NEF_DEBUG
#define CGAL_NEF_DEBUG 19
#include <CGAL/Nef_2/debug.h>

CGAL_BEGIN_NAMESPACE

template <typename Map, typename SNC_point_locator>
class Combine_with_halfspace : public SNC_decorator<Map> { 
 public:
  typedef Map SNC_structure;
  typedef typename SNC_structure::Items                Items;
  typedef typename Map::Sphere_map                     Sphere_map;
  typedef CGAL::Combine_with_halfspace
    <SNC_structure, SNC_point_locator>  Self;
  typedef CGAL::SNC_decorator<SNC_structure>           Base;
  typedef Base                                         SNC_decorator;
  typedef CGAL::SNC_constructor<Items, SNC_structure>  SNC_constructor;
  typedef CGAL::SNC_external_structure<Items, SNC_structure> 
    SNC_external_structure;
  typedef CGAL::SM_decorator<Sphere_map>               SM_decorator;
  typedef CGAL::SM_const_decorator<Sphere_map>         SM_const_decorator;
  typedef CGAL::Binary_operation<SNC_structure>        Binary_operation;

  typedef typename SNC_structure::Vertex_handle Vertex_handle;

  typedef typename SNC_structure::Vertex_const_iterator Vertex_const_iterator;
  typedef typename SNC_structure::Halfedge_const_iterator Halfedge_const_iterator;

  typedef typename Base::SHalfedge_iterator SHalfedge_iterator;
  typedef typename Base::SHalfedge_const_iterator SHalfedge_const_iterator;
  typedef typename Base::SHalfloop_const_iterator SHalfloop_const_iterator;

  typedef typename Base::Point_3 Point_3;
  typedef typename Base::Segment_3 Segment_3;
  typedef typename Base::Plane_3 Plane_3;

  typedef typename Base::Mark Mark;

  typedef CGAL::ID_support_handler<Items, Base> Association;

  SNC_point_locator* pl;

 public:
  Combine_with_halfspace(SNC_structure& W, SNC_point_locator* pl_) 
    : Base(W), pl(pl_) {}
    
  template <typename Selection>
  void combine_with_halfspace(const SNC_structure& snc,
			      const Plane_3& plane,
			      const Selection& BOP,
			      bool with_boundary = true) {
    
    Association A;
    SHalfedge_const_iterator sei;
    CGAL_forall_shalfedges(sei, snc)
      A.initialize_hash(sei);
    SHalfloop_const_iterator sli;
    CGAL_forall_shalfloops(sli, snc)
      A.initialize_hash(sli);
    
    Binary_operation bo(*this->sncp());
    Vertex_const_iterator v0;
    CGAL_forall_vertices( v0, snc) {
      Oriented_side os = plane.oriented_side(v0->point());
      if(os == ON_ORIENTED_BOUNDARY) {
	SNC_constructor C(*this->sncp());
	Vertex_handle vp =
	  C.create_from_plane(plane, v0->point(),
			      with_boundary, true, false);
	Vertex_handle vr = 
	  bo.binop_local_views(v0, vp, BOP, *this->sncp(), A);
	this->sncp()->delete_vertex(vp);
      } else if(os == ON_NEGATIVE_SIDE) {
	SNC_constructor C(*this->sncp());
	Vertex_handle v1 = C.clone_SM(v0);	
      }
    }

    Halfedge_const_iterator e0;
    CGAL_forall_edges(e0, snc) {
      Segment_3 seg(e0->source()->point(), 
		    e0->twin()->source()->point());
      Object o = intersection(plane, seg);
      Point_3 ip;
      if(!assign(ip,o)) continue;
      // TODO: optimize for filtering
      ip = normalized(ip);
      if(ip == e0->source()->point() ||
	 ip == e0->twin()->source()->point()) continue;
      SNC_constructor C(*this->sncp());
      Vertex_handle vp = 
	C.create_from_plane(plane, ip,
			    with_boundary, true, false);
      Vertex_handle ve = C.create_from_edge(e0, ip);
      
      Vertex_handle vr = 
	bo.binop_local_views(ve, vp, BOP, *this->sncp(), A);
      this->sncp()->delete_vertex(vp);
      this->sncp()->delete_vertex(ve);
    }
    
    SHalfedge_iterator se;
    CGAL_forall_sedges(se, *this->sncp()) {
      se->circle() = normalized(se->circle());
      se->twin()->circle() = se->circle().opposite();
    }

    SNC_external_structure es(*this->sncp(), pl);
    es.build_after_binary_operation(A);
  }
};

CGAL_END_NAMESPACE
#endif //CGAL_COMBINE_WITH_HALFSPACE_H