Revision 2a37790e475d089154fa08c65eb4997c76a72a17 authored by Simon Giraudot on 21 December 2016, 12:50:18 UTC, committed by Simon Giraudot on 21 December 2016, 12:50:18 UTC
1 parent fb9aae7
surface_neighbors_3.h
// Copyright (c) 2003 INRIA Sophia-Antipolis (France).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org).
// You can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation,
// either version 3 of the License, or (at your option) any later version.
//
// 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 DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL$
// $Id$
//
//
// Author(s) : Julia Floetotto
#ifndef CGAL_SURFACE_NEIGHBORS_3_H
#define CGAL_SURFACE_NEIGHBORS_3_H
#include <utility>
#include <CGAL/Voronoi_intersection_2_traits_3.h>
#include <CGAL/Regular_triangulation_2.h>
#include <CGAL/Iterator_project.h>
//contains the definition of the Comparator "closer_to_point" and
// the function object Project_vertex_iterator_to_point
#include <CGAL/surface_neighbor_coordinates_3.h>
namespace CGAL {
//without Delaunay filtering
template <class OutputIterator, class InputIterator, class Kernel>
inline
OutputIterator
surface_neighbors_3(InputIterator first, InputIterator beyond,
const typename Kernel::Point_3& p,
const typename Kernel::Vector_3& normal,
OutputIterator out, const Kernel& )
{
typedef Voronoi_intersection_2_traits_3<Kernel> I_gt;
return surface_neighbors_3(first, beyond, p, out, I_gt(p,normal));
}
template <class OutputIterator, class InputIterator, class ITraits>
OutputIterator
surface_neighbors_3(InputIterator first, InputIterator beyond,
const typename ITraits::Point_2& p,
OutputIterator out, const ITraits& traits)
{
//definition of the Voronoi intersection triangulation:
typedef Regular_triangulation_2< ITraits> I_triangulation;
typedef typename I_triangulation::Vertex_handle Vertex_handle;
typedef typename I_triangulation::Face_handle Face_handle;
typedef typename I_triangulation::Locate_type Locate_type;
//build Voronoi intersection triangulation:
I_triangulation it(traits);
it.insert(first,beyond);
Locate_type lt;
int li;
Face_handle fh = it.locate(p, lt, li);
if(lt == I_triangulation::VERTEX){
*out++ =p;
return out;
}
Vertex_handle vh = it.insert(p, fh);
typename I_triangulation::Vertex_circulator
vc(it.incident_vertices(vh)),
done(vc);
do{
*out++= vc->point();
CGAL_assertion(! it.is_infinite(vc));
}
while(vc++!=done);
return out;
}
//without Delaunay filtering -- certified version:
// a boolean is returned that indicates if a sufficiently large
// neighborhood has been considered so that the
// Voronoi cell of p is not affected by any point outside the smallest
// ball centered on p containing all points in [first,beyond)
template <class OutputIterator, class InputIterator, class Kernel>
std::pair< OutputIterator, bool >
surface_neighbors_certified_3(InputIterator first,
InputIterator beyond,
const typename Kernel::Point_3& p,
const typename Kernel::Vector_3& normal,
OutputIterator out, const Kernel& )
{
typedef Voronoi_intersection_2_traits_3<Kernel> I_gt;
return surface_neighbors_certified_3(first, beyond, p, out, I_gt(p,normal));
}
//this function takes the radius of the sphere centered on p
// containing the points in [first, beyond] (i.e. the maximal
// distance from p to [first,beyond) as add. parameter:
template <class OutputIterator, class InputIterator, class Kernel>
std::pair< OutputIterator, bool >
surface_neighbors_certified_3(InputIterator first,
InputIterator beyond,
const typename Kernel::Point_3& p,
const typename Kernel::Vector_3& normal,
const typename Kernel::FT& radius,
OutputIterator out,
const Kernel& /*K*/)
{
typedef Voronoi_intersection_2_traits_3<Kernel> I_gt;
return surface_neighbors_certified_3(first, beyond, p, radius,
out, I_gt(p,normal));
}
// Versions with instantiated traits class:
template <class OutputIterator, class InputIterator, class ITraits>
std::pair< OutputIterator, bool >
surface_neighbors_certified_3(InputIterator first,
InputIterator beyond,
const typename ITraits::Point_2& p,
OutputIterator out,
const ITraits& traits)
{
//find the point in [first,beyond) furthest from p:
InputIterator furthest = std::max_element(first, beyond,
closer_to_point<ITraits>(p, traits));
return surface_neighbors_certified_3
(first, beyond, p,
traits.compute_squared_distance_2_object()(p,*furthest),
out, traits);
}
template <class OutputIterator, class InputIterator, class ITraits>
std::pair< OutputIterator, bool >
surface_neighbors_certified_3(InputIterator first,
InputIterator beyond,
const typename ITraits::Point_2& p,
const typename ITraits::FT& radius,
OutputIterator out,
const ITraits& traits)
{
//definition of the Voronoi intersection triangulation:
typedef Regular_triangulation_2< ITraits> I_triangulation;
typedef typename I_triangulation::Vertex_handle Vertex_handle;
typedef typename I_triangulation::Face_handle Face_handle;
typedef typename I_triangulation::Vertex_circulator Vertex_circulator;
typedef typename I_triangulation::Face_circulator Face_circulator;
typedef typename I_triangulation::Locate_type Locate_type;
//build Voronoi intersection triangulation:
I_triangulation it(traits);
it.insert(first,beyond);
Locate_type lt;
int li;
Face_handle fh = it.locate(p, lt, li);
if(lt == I_triangulation::VERTEX){
*out++ =p;
return std::make_pair(out,true);
}
Vertex_handle vh = it.insert(p, fh);
CGAL_assertion(vh->is_valid());
//determine the furthest distance from p to a vertex of its cell
bool valid(false);
Face_circulator fc(it.incident_faces(vh)), fdone(fc);
do
valid = (!it.is_infinite(fc) &&
(4*radius > traits.compute_squared_distance_2_object()
(p, it.dual(fc))));
while(!valid && ++fc!=fdone);
//get the neighbor points:
Vertex_circulator
vc(it.incident_vertices(vh)),
vdone(vc);
do
*out++= vc->point();
while(++vc!=vdone);
return std::make_pair(out, valid);
}
//using Delaunay triangulation for candidate point filtering:
// => no certification is necessary
template <class Dt, class OutputIterator>
inline
OutputIterator
surface_neighbors_3(const Dt& dt,
const typename Dt::Geom_traits::Point_3& p,
const typename Dt::Geom_traits::Vector_3& normal,
OutputIterator out,
typename Dt::Cell_handle start =typename Dt::Cell_handle())
{
typedef Voronoi_intersection_2_traits_3<typename Dt::Geom_traits> I_gt;
return surface_neighbors_3(dt, p, out, I_gt(p,normal),start);
}
template <class Dt, class OutputIterator, class ITraits>
OutputIterator
surface_neighbors_3(const Dt& dt,
const typename ITraits::Point_2& p,
OutputIterator out, const ITraits& traits,
typename Dt::Cell_handle start
= typename Dt::Cell_handle())
{
typedef typename ITraits::Point_2 Point_3;
typedef typename Dt::Cell_handle Cell_handle;
typedef typename Dt::Vertex_handle Vertex_handle;
typedef typename Dt::Locate_type Locate_type;
//the Vertex_handle is, in fact, an iterator over vertex:
typedef Project_vertex_iterator_to_point< Vertex_handle> Proj_point;
typedef Iterator_project<
typename std::list< Vertex_handle >::iterator,
Proj_point,
const Point_3&,
const Point_3*,
std::ptrdiff_t,
std::forward_iterator_tag> Point_iterator;
Locate_type lt;
int li, lj ;
Cell_handle c = dt.locate(p, lt, li,lj,start);
//if p is located on a vertex: the only neighbor is found
if(lt == Dt::VERTEX){
*out++= (c->vertex(li))->point();
return out;
}
//otherwise get vertices in conflict
typename std::list< Vertex_handle > conflict_vertices;
dt.vertices_on_conflict_zone_boundary(p,c,
std::back_inserter(conflict_vertices));
for (typename std::list< Vertex_handle >::iterator it = conflict_vertices.begin();
it != conflict_vertices.end();){
if(dt.is_infinite(*it)){
typename std::list< Vertex_handle >::iterator itp = it;
it++;
conflict_vertices.erase(itp);
} else {
it++;
}
}
return surface_neighbors_3(Point_iterator(conflict_vertices.begin()),
Point_iterator(conflict_vertices.end()),
p, out, traits);
}
} //namespace CGAL
#endif // CGAL_SURFACE_NEIGHBORS_3_H
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...