/usr/include/libwildmagic/Wm5IncrementalDelaunay2.h is in libwildmagic-dev 5.13-1+b2.
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 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 | // Geometric Tools, LLC
// Copyright (c) 1998-2014
// Distributed under the Boost Software License, Version 1.0.
// http://www.boost.org/LICENSE_1_0.txt
// http://www.geometrictools.com/License/Boost/LICENSE_1_0.txt
//
// File Version: 5.0.1 (2010/10/01)
#ifndef WM5INCREMENTALDELAUNAY2_H
#define WM5INCREMENTALDELAUNAY2_H
#include "Wm5MathematicsLIB.h"
#include "Wm5RVector2.h"
#include "Wm5MinHeap.h"
#include "Wm5Vector2.h"
#include "Wm5VEManifoldMesh.h"
namespace Wm5
{
template <typename Real>
class WM5_MATHEMATICS_ITEM IncrementalDelaunay2
{
public:
// Construction and destruction. The bounding rectangle for the data
// points must be specified. Each (x,y) must satisfy xmin <= x <= xmax
// and ymin <= y <= ymax. If 'uncertainty' is set to 0, then the
// geometric computations involve only floating-point arithmetic. If
// 'uncertainty' is in (0,1), then filtered predicates are used to
// compute the signs of quantities of interest. If 'uncertainty' is
// set to 1, then exact rational arithmetic is used.
IncrementalDelaunay2 (Real xmin, Real ymin, Real xmax, Real ymax,
Real uncertainty = (Real)0);
~IncrementalDelaunay2 ();
// Insert a point into the triangulation. The return value is the index
// associated with the vertex in the vertex map. The supertriangle
// vertices are at indices 0, 1, and 2. If the input point already
// exists, its vertex-map index is simply returned. If the position
// is outside the domain specified in the constructor, the return value
// is -1.
int Insert (const Vector2<Real>& position);
// Remove a point from the triangulation. The return value is the index
// associated with the vertex in the vertex map when that vertex exists.
// If the vertex does not exist, the return value is -1.
int Remove (const Vector2<Real>& position);
// Support for debugging. Return an index array of all the triangles,
// including those that connect to vertices of the supertriangle. The
// caller is responsible for deleting the raiIndices output.
void GetAllTriangles (int& numTriangles, int*& indices);
//========================================================================
// Generate a compactified representation of the triangulation. After
// this call, the functions following this one are valid to call. Also,
// if you call Insert and/or Remove after calling GenerateRepresentation,
// the functions following this one are invalid to call, and if you are
// hanging onto pointers and/or references produced by these functions,
// they are now invalid. You may, however, call GenerateRepresentation
// again at which time the functions following this one are once again
// valid to call.
void GenerateRepresentation ();
// N = GetNumTriangles() is the number of triangles in the mesh. The
// array returned by I = GetIndices() contains N tuples, each tuple
// having 3 elements and representing a triangle. An index I[*] is
// relative to the vertex array V. The array returned by
// A = GetAdjacencies() contains N tuples, each tuple having 3 elements
// and representing those triangles adjacent to the 3 edges of a triangle.
// An index A[*] is relative to the index array I.
int GetNumTriangles () const;
const int* GetIndices () const;
const int* GetAdjacencies () const;
// The input vertex array. The array includes all unique points passed
// to Insert, even if Remove was called later for any inserted points.
// The points at indices 0, 1, and 2 are always the vertices of the
// supertriangle.
const std::vector<Vector2<Real> >& GetVertices () const;
// The unique vertices processed. These are the actual vertices in the
// triangulation. The 'int' value is the index associated with the
// vertex.
const std::map<Vector2<Real>,int>& GetUniqueVertices () const;
// Locate those triangle edges that do not share other triangles. The
// returned quantity is the number of edges in the hull. The returned
// array has 2*quantity indices, each pair representing an edge. The
// edges are not ordered, but the pair of vertices for an edge is ordered
// so that they conform to a counterclockwise traversal of the hull. The
// return value is 'true' iff the dimension is 2.
bool GetHull (int& numEdges, int*& indices);
// Support for searching the triangulation for a triangle that contains
// a point. If there is a containing triangle, the returned value is a
// triangle index i with 0 <= i < GetNumTriangles(). If there is not a
// containing triangle, -1 is returned.
int GetContainingTriangle (const Vector2<Real>& p) const;
// If GetContainingTriangle returns a nonnegative value, the path of
// triangles searched for the containing triangles is stored in an array.
// The last index of the array is returned by GetPathLast; it is one
// less than the number of array elements. The array itself is returned
// by GetPath.
int GetPathLast () const;
const int* GetPath () const;
// If GetContainingTriangle returns -1, the path of triangles searched
// may be obtained by GetPathLast and GetPath. The input point is outside
// an edge of the last triangle in the path. This function returns the
// vertex indices <v0,v1> of the edge, listed in counterclockwise order
// relative to the convex hull of the data points. The final output is
// the index of the vertex v2 opposite the edge. The return value of
// the function is the index of the triple of vertex indices; the value
// is 0, 1, or 2.
int GetLastEdge (int& v0, int& v1, int& v2) const;
// Get the vertices for triangle i. The function returns 'true' if i is
// a valid triangle index, in which case the vertices are valid.
// Otherwise, the function returns 'false' and the vertices are invalid.
bool GetVertexSet (int i, Vector2<Real> vertices[3]) const;
// Get the vertex indices for triangle i. The function returns 'true' if
// i is a valid triangle index, in which case the vertices are valid.
// Otherwise, the function returns 'false' and the vertices are invalid.
bool GetIndexSet (int i, int indices[3]) const;
// Get the indices for triangles adjacent to triangle i. The function
// returns 'true' if i is a valid triangle index, in which case the
// adjacencies are valid. Otherwise, the function returns 'false' and
// the adjacencies are invalid.
bool GetAdjacentSet (int i, int adjacencies[3]) const;
// Compute the barycentric coordinates of P with respect to triangle i.
// The function returns 'true' if i is a valid triangle index, in which
// case the coordinates are valid. Otherwise, the function returns
// 'false' and the coordinate array is invalid.
bool GetBarycentricSet (int i, const Vector2<Real>& p, Real bary[3])
const;
//========================================================================
private:
// Convenient type definitions.
typedef std::map<Vector2<Real>,int> VertexMap;
typedef Rational<4*sizeof(Real)> QRational;
typedef RVector2<4*sizeof(Real)> QRVector;
class Triangle
{
public:
Triangle (int v0, int v1, int v2);
bool IsInsertionComponent (int posIndex, const Vector2<Real>& test,
Triangle* adj, const IncrementalDelaunay2* delaunay);
int DetachFrom (int adjIndex, Triangle* adj);
int V[3];
Triangle* Adj[3];
int Time;
bool IsComponent;
bool OnStack;
};
class Edge : public VEManifoldMesh::Edge
{
public:
Edge (int v0 = -1, int v1 = -1, int nullIndex = -1,
Triangle* tri = 0);
static VEManifoldMesh::EPtr ECreator (int v0, int v1);
int NullIndex;
Triangle* Tri;
};
// Support for the removal polygon and its triangulation.
class RPVertex
{
public:
RPVertex (int index = -1, Triangle* tri = 0, Triangle* adj = 0);
// The index into the vertex pool of the position.
int Index;
// The triangle sharing edge <Index,NextIndex> and inside the
// removal polygon.
Triangle* Tri;
// The triangle sharing edge <PrevIndex,Index> and inside the
// removal polygon.
Triangle* Adj;
// A vertex is either convex or reflex. Its condition is stored by
// the following member.
bool IsConvex;
// A convex vertex is either an ear tip or it is not. Its condition
// is stored by the following member.
bool IsEarTip;
// The removal polygon will contain supervertices when the removal
// point is on the boundary of the convex hull of the triangulation.
bool IsSuperVertex;
// Let V0 be the position of 'this' vertex. If V0 is a supervertex or
// is not an ear, its weight is +INFINITY. Otherwise, let Vp be its
// predecessor and let Vn be its successor when traversing the polygon
// counterclockwise. Let P be the removal point. The weight is the
// ratio
// Weight = H(Vp,V0,Vn,P)/D(Vp,V0,Vn)
// where
// + -+
// D = det | Vp.x Vp.y 1 |
// | V0.x V0.y 1 |
// | Vn.x Vn.y 1 |
// +- -+
// and
// +- -+
// H = det | Vp.x Vp.y Vp.x^2+Vp.y^2 1 |
// | V0.x V0.y V0.x^2+V0.y^2 1 |
// | Vn.x Vn.y Vn.x^2+Vn.y^2 1 |
// | P.x P.y P.x^2+P.y^2 1 |
// +- -+
Real Weight;
// Vertex links for polygon.
int VPrev, VNext;
// Convex/reflex vertex links (disjoint lists).
int SPrev, SNext;
// Ear tip record.
const MinHeapRecord<int,Real>* EarRecord;
};
class Triangulate
{
public:
Triangulate (std::vector<RPVertex>& polygon, int removal,
IncrementalDelaunay2* delaunay);
private:
// Prevent MSVC warning C4512 (assignment operator could not be
// generated). No assignment is needed by this class.
Triangulate& operator= (const Triangulate&) { return *this; }
RPVertex& V (int i);
bool IsConvex (int i);
bool IsEarTip (int i);
void InsertAfterC (int i); // insert convex vertex
void InsertAfterR (int i); // insert reflex vertesx
void RemoveV (int i); // remove vertex
void RemoveR (int i); // remove reflex vertex
Real ComputeWeight (int v0, int p);
std::vector<RPVertex>& mPolygon;
int mNumVertices;
IncrementalDelaunay2* mDelaunay;
int mCFirst, mCLast; // linear list of convex vertices
int mRFirst, mRLast; // linear list of reflex vertices
MinHeap<int,Real> mEHeap; // priority queue of ear tips
};
// The directed line is <V0,V1>. The return value is +1 when 'test' is
// to the right of the line, -1 when 'test' is to the left of the line,
// or 0 when 'test' is exactly on the line.
int ToLine (const Vector2<Real>& test, int v0, int v1) const;
// The triangle is <V0,V1,V2>. The return value is +1 when 'test' is
// outside the triangle, -1 when 'test' is inside the triangle, or 0 when
// 'test' is exactly on the triangle.
int ToTriangle (const Vector2<Real>& test, int v0, int v1, int v2) const;
// The triangle of the circumcircle is <V0,V1,V2>. The return value is
// +1 when 'test' is outside the circle, -1 when 'test' is inside the
// circle, or 0 when 'test' is exactly on the circle.
int ToCircumcircle (const Vector2<Real>& test, int v0, int v1,
int v2) const;
// Use a linear walk to find the triangle containing the point.
Triangle* GetContainingTriangleInternal (const Vector2<Real>& position)
const;
// Return 'true' iff the specified triangle contains a supervertex. This
// function is used by GenerateRepresentation.
bool ContainsSupervertex (Triangle* tri) const;
// Swap the shared edge with the other diagonal of the quadrilateral
// union of the two triangles.
void SwapEdge (Triangle* tri0, Triangle* tri1);
private:
// The rectangular domain in which all input points live.
Real mXMin, mXMax, mYMin, mYMax;
// The vertices of the triangulation. The vertex pool stores the unique
// positions that were passed to the Insert function. This allows for a
// fast look-up of vertices by the GetContainingTriangle function.
VertexMap mVMap;
std::vector<Vector2<Real> > mVertexPool;
// This member is used to decide whether or not to accept the results of
// ToLine when computed using floating-point arithmetic. The test
// involves a determinant sign. When the determinant is sufficiently
// small, the result is uncertain and the determinant is recomputed using
// exact rational arithmetic.
Real mUncertainty;
// When the uncertainty is positive, filtered predicate queries are used
// and storage is needed for rational vectors to minimize the computation
// of such vectors.
mutable std::vector<QRVector>* mRatVertexPool;
mutable std::vector<bool>* mRatVertexEvaluated;
// The current triangulation.
std::set<Triangle*> mTriangle;
// Compacted informatoin about the triangulation.
// N = number of triangles
// I = Array of 3-tuples of indices into V that represent the
// triangles (3*N total elements).
// A = Array of 3-tuples of indices into I that represent the
// adjacent triangles (3*N total elements).
// The i-th triangle has vertices
// vertex[0] = V[I[3*i+0]]
// vertex[1] = V[I[3*i+1]]
// vertex[2] = V[I[3*i+2]]
// and edge index pairs
// edge[0] = <I[3*i+0],I[3*i+1]>
// edge[1] = <I[3*i+1],I[3*i+2]>
// edge[2] = <I[3*i+2],I[3*i+0]>
// The triangles adjacent to these edges have indices
// adjacent[0] = A[3*i+0] is the triangle sharing edge[0]
// adjacent[1] = A[3*i+1] is the triangle sharing edge[1]
// adjacent[2] = A[3*i+2] is the triangle sharing edge[2]
// If there is no adjacent triangle, the A[*] value is set to -1. The
// triangle adjacent to edge[j] has vertices
// adjvertex[0] = V[I[3*adjacent[j]+0]]
// adjvertex[1] = V[I[3*adjacent[j]+1]]
// adjvertex[2] = V[I[3*adjacent[j]+2]]
int mNumTriangles;
int* mIndices;
int* mAdjacencies;
// Store the path of triangles visited in a GetContainingTriangle
// function call.
mutable int mPathLast;
mutable int* mPath;
// If a query point is not in the convex hull of the input points, the
// point is outside an edge of the last triangle in the search path.
// These are the vertex indices for that edge.
mutable int mLastEdgeV0, mLastEdgeV1;
mutable int mLastEdgeOpposite, mLastEdgeOppositeIndex;
};
typedef IncrementalDelaunay2<float> IncrementalDelaunay2f;
typedef IncrementalDelaunay2<double> IncrementalDelaunay2d;
}
#endif
|