This file is indexed.

/usr/include/CGAL/convex_decomposition_3.h is in libcgal-dev 4.2-5ubuntu1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
// Copyright (c) 2005-2008 Max-Planck-Institute Saarbruecken (Germany).
// 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)     :  Peter Hachenberger <hachenberger@mpi-sb.mpg.de>
#ifndef CGAL_CONVEX_DECOMPOSITION_3_H
#define CGAL_CONVEX_DECOMPOSITION_3_H

#include <CGAL/Convex_decomposition_3/Single_wall_creator.h>
#include <CGAL/Convex_decomposition_3/Single_wall_creator2.h>
#include <CGAL/Convex_decomposition_3/Reflex_edge_searcher.h>
#include <CGAL/Convex_decomposition_3/Reflex_vertex_searcher.h>
#include <CGAL/Convex_decomposition_3/YVertical_wall_builder.h>
#include <CGAL/Convex_decomposition_3/Ray_hit_generator2.h>
#include <CGAL/Convex_decomposition_3/External_structure_builder.h>
#include <CGAL/Convex_decomposition_3/SFace_separator.h>
#include <CGAL/Convex_decomposition_3/Edge_sorter.h>
#include <CGAL/Convex_decomposition_3/is_reflex_sedge.h>

/*! 
  \file convex_decomposition_3.h 
*/


/// The CGAL namespace.
namespace CGAL {

/*!
\ingroup PkgConvexDecomposition3

The function `convex_decomposition_3()` inserts additional facets 
into the given `Nef_polyhedron_3` `N`, such that each bounded 
marked volume (the outer volume is unbounded) is subdivided into convex 
pieces. The modified polyhedron represents a decomposition into 
\f$ O(r^2)\f$ convex pieces, where \f$ r\f$ is the number of edges that have two 
adjacent facets that span an angle of more than 180 degrees with 
respect to the interior of the polyhedron. 

The worst-case running time of our implementation is 
\f$ O(n^2r^4\sqrt[3]{nr^2}\log{(nr)})\f$, where \f$ n\f$ is the complexity of 
the polyhedron (the complexity of a `Nef_polyhedron_3` is the sum 
of its `Vertices`, `Halfedges` and `SHalfedges`) and \f$ r\f$ 
is the number of reflex edges. 

\pre The polyhedron `N` is bounded. Otherwise, the outer volume is ignored. 

\post If the polyhedron `N` is non-convex, it is modified to represent the 
convex decomposition. If `N` is convex, it is not modified. 

\sa `CGAL::Nef_polyhedron_3<Traits>` 

*/
template<typename Nef_polyhedron>
void convex_decomposition_3(Nef_polyhedron& N) 
{
  typedef typename Nef_polyhedron::SNC_structure  SNC_structure;
  typedef typename SNC_structure::Halfedge_handle Halfedge_handle;
  typedef typename Nef_polyhedron::Point_3            Point_3;
  typedef typename Nef_polyhedron::Vector_3           Vector_3;
  typedef typename Nef_polyhedron::Sphere_point   Sphere_point;
  typedef typename Nef_polyhedron::FT FT;

  typedef typename CGAL::Single_wall_creator<Nef_polyhedron>  Single_wall;
  typedef typename CGAL::YVertical_wall_builder<Nef_polyhedron> YVertical_wall_builder;
  typedef typename CGAL::Reflex_vertex_searcher<Nef_polyhedron>  Reflex_vertex_searcher;
  typedef typename CGAL::Ray_hit_generator2<Nef_polyhedron> Ray_hit2;
  typedef typename CGAL::External_structure_builder<Nef_polyhedron> External_structure_builder;
  typedef typename CGAL::SFace_separator<Nef_polyhedron> SFace_separator;

  typedef Compare_halfedges_in_reflex_edge_sorter<Halfedge_handle, std::less<Point_3> >
	  Less_edges;
  typedef Compare_halfedges_in_reflex_edge_sorter<Halfedge_handle, std::greater<Point_3> >
	  Greater_edges;

  typedef typename std::multiset<Halfedge_handle, Less_edges> Negatively_sorted_set;
  typedef typename std::multiset<Halfedge_handle, Greater_edges> Positively_sorted_set;
  typedef typename Positively_sorted_set::const_iterator  Positive_reflex_edge_iterator;
  typedef typename Negatively_sorted_set::const_iterator  Negative_reflex_edge_iterator;

  typedef typename CGAL::Reflex_edge_searcher<Nef_polyhedron, Positively_sorted_set, Negatively_sorted_set>
	  Reflex_edge_searcher;

  typedef typename CGAL::Edge_sorter<Nef_polyhedron, std::less<FT>, Negatively_sorted_set> Edge_sorter;
  typedef typename CGAL::Edge_sorter<Nef_polyhedron, std::greater<FT>, Positively_sorted_set> Edge_sorter2;

  External_structure_builder esb;
  SFace_separator sf_sep;
  N.delegate(sf_sep,false, false);

  Reflex_edge_searcher res(Sphere_point(1,0,0));
  N.delegate(res,false,false);
  
  Edge_sorter es(res.get_negative_redges());
  N.delegate(es);
  
  Negative_reflex_edge_iterator nrei;
  for(nrei=res.negative_redges_begin(); nrei!=res.negative_redges_end(); ++nrei) {
    Halfedge_handle e = (*nrei);
    
    Single_wall W(e,Vector_3(-1,0,0));
    if(!W.need_to_create_wall()) continue;
    
    Reflex_vertex_searcher rvs(Sphere_point(1,0,0));
    if(rvs.need_to_shoot(e, true)) {
      Ray_hit2 rh2a(Vector_3(-1,0,0), e->source());
      N.delegate(rh2a);
    }
    if(rvs.need_to_shoot(e->twin(), true)) {
      Ray_hit2 rh2a(Vector_3(-1,0,0), e->twin()->source());
      N.delegate(rh2a);
    }  
  }
  
  // int i=0;
  for(nrei=res.negative_redges_begin(); nrei!=res.negative_redges_end(); ++nrei) {
    Halfedge_handle e = (*nrei);
    if(e->point().hx() > 0)
      e = e->twin();
    Single_wall W(e,Vector_3(-1,0,0));
    if(!W.need_to_create_wall()) continue;    
    N.delegate(W);
  }
  
  N.delegate(esb);
  N.delegate(res, false, false);
  
  CGAL_assertion(N.is_valid(0,0));
  
  Reflex_edge_searcher& res2 = res;
  
  Edge_sorter2 es2(res2.get_positive_redges());
  N.delegate(es2);
  
  Positive_reflex_edge_iterator prei;
  for(prei=res2.positive_redges_begin(); prei!=res2.positive_redges_end(); ++prei) {
    Halfedge_handle e = (*prei);
    
    CGAL_assertion(e->source()->point() >
		   e->twin()->source()->point());
    Single_wall W(e,Vector_3(1,0,0));
    if(!W.need_to_create_wall()) continue;
    
    Reflex_vertex_searcher rvs(Sphere_point(1,0,0));
    if(rvs.need_to_shoot(e, false)) {
      Ray_hit2 rh2a(Vector_3(1,0,0), e->source());
      N.delegate(rh2a);
    }
    if(rvs.need_to_shoot(e->twin(), false)) {
      Ray_hit2 rh2a(Vector_3(1,0,0), e->twin()->source());
      N.delegate(rh2a);
    }
  }
  
  // i=0;
  for(prei=res2.positive_redges_begin(); prei!=res2.positive_redges_end(); ++prei) {
    Halfedge_handle e = (*prei);
    Single_wall W(e,Vector_3(1,0,0));
    if(!W.need_to_create_wall()) continue;
    N.delegate(W);
  }
  
  N.delegate(esb);    
  CGAL_assertion(N.is_valid(0,0));
  
  YVertical_wall_builder Y;
  N.delegate(Y,false,false);
  
  N.delegate(esb);

  CGAL_assertion_code(typename Nef_polyhedron::SHalfedge_const_iterator cse);
  CGAL_assertion_code(CGAL_forall_shalfedges(cse, N)
    if(cse->incident_sface()->mark())
      CGAL_assertion(!CGAL::is_reflex_sedge_in_any_direction<Nef_polyhedron>(cse)));
}

} //namespace CGAL
#endif // CGAL_CONVEX_DECOMPOSITION_3_H