polygonTriangulate.H
Go to the documentation of this file.
1 /*---------------------------------------------------------------------------*\
2  ========= |
3  \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
4  \\ / O peration | Website: https://openfoam.org
5  \\ / A nd | Copyright (C) 2021 OpenFOAM Foundation
6  \\/ M anipulation |
7 -------------------------------------------------------------------------------
8 License
9  This file is part of OpenFOAM.
10 
11  OpenFOAM is free software: you can redistribute it and/or modify it
12  under the terms of the GNU General Public License as published by
13  the Free Software Foundation, either version 3 of the License, or
14  (at your option) any later version.
15 
16  OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
17  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
18  FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19  for more details.
20 
21  You should have received a copy of the GNU General Public License
22  along with OpenFOAM. If not, see <http://www.gnu.org/licenses/>.
23 
24 Class
25  Foam::polygonTriangulate
26 
27 Description
28  Triangulation of three-dimensional polygons
29 
30 SourceFiles
31  polygonTriangulate.C
32 
33 \*---------------------------------------------------------------------------*/
34 
35 #ifndef polygonTriangulate_H
36 #define polygonTriangulate_H
37 
38 #include "DynamicList.H"
39 #include "HashSet.H"
40 #include "labelPair.H"
41 #include "triFace.H"
42 
43 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
44 
45 namespace Foam
46 {
47 
48 /*---------------------------------------------------------------------------*\
49  Class polygonTriangulate Declaration
50 \*---------------------------------------------------------------------------*/
51 
53 {
54  // Private Data
55 
56  //- Indirect addressing into point field to form the current as yet
57  // un-triangulated polygon
58  DynamicList<label> pointis_;
59 
60  //- Edge indices of the un-triangulated polygon
61  DynamicList<label> edges_;
62 
63  //- The interior angles of the vertices of the un-triangulated polygon
64  DynamicList<scalar> angle_;
65 
66  //- Flags to denote whether points of the un-triangulated polygon are
67  // "ears"; i.e., that the triangle formed by adding a diagonal between
68  // two adjacent points contains no other point
69  DynamicList<bool> ear_;
70 
71  //- Set of tri-faces used to mark previously considered configurations
72  // in optimisation and prevent unnecessary repetition
73  HashSet<triFace, Hash<triFace>> triPointsSet_;
74 
75  //- Point array. Used if the input points cannot be SubList-d.
76  DynamicList<point> points_;
77 
78  //- Tri-points
79  DynamicList<triFace> triPoints_;
80 
81  //- Tri-edge associations
83 
84  //- Edge-tri associations
85  DynamicList<labelPair> edgeTris_;
86 
87 
88  // Private Static Member Functions
89 
90  // Renumber a polygon label to global indexing
91  static inline label renumberPolyToGlobal
92  (
93  const label triPoly,
94  const UList<label>& polyToGlobal
95  );
96 
97  // Renumber a container of polygon labels to global indexing
98  template<class Type>
99  static inline Type renumberPolyToGlobal
100  (
101  const Type& triPoly,
102  const UList<label>& polyToGlobal
103  );
104 
105  //- Return the area of a triangle projected in a normal direction
106  template<class PointField>
107  static scalar area
108  (
109  const triFace& triPoints,
110  const PointField& points,
111  const vector& normal
112  );
113 
114  //- Return the quality of a triangle projected in a normal direction
115  template<class PointField>
116  static scalar quality
117  (
118  const triFace& triPoints,
119  const PointField& points,
120  const vector& normal
121  );
122 
123  //- Return whether or not two edges intersect in the plane defined by a
124  // normal
125  template<class PointField>
126  static bool intersection
127  (
128  const edge& edgePointsA,
129  const edge& edgePointsB,
130  const PointField& points,
131  const vector& normal
132  );
133 
134  //- Return the number of intersections of an edge within a polygon
135  template<class PointField>
136  static label nIntersections
137  (
138  const edge& edgePoints,
139  const PointField& points,
140  const vector& normal
141  );
142 
143  //- Return the interior angle of the point in a polygon in the plane
144  // defined by a normal
145  template<class PointField>
146  static scalar angle
147  (
148  const label pointi,
149  const PointField& points,
150  const vector& normal
151  );
152 
153  //- Return whether a point in a polygon is an "ear"; i.e., that the
154  // triangle formed by adding a diagonal between the two adjacent
155  // points contains no other point
156  template<class PointField>
157  static bool ear
158  (
159  const label pointi,
160  const PointField& points,
161  const vector& normal
162  );
163 
164 
165  // Private Member Functions
166 
167  //- Optimise the triangulation quality by flipping edges
168  template<class PointField>
169  void optimiseTriangulation
170  (
171  const label trii,
172  const PointField& points,
173  const vector& normal,
174  UList<triFace>& triPoints,
176  UList<labelPair>& edgeTris
177  );
178 
179  //- Perform triangulation of a polygon by ear clipping, assuming that
180  // the polygon is simple/non-intersecting
181  void simpleTriangulate
182  (
183  const UList<point>& points,
184  const vector& normal,
185  UList<triFace>& triPoints,
187  UList<labelPair>& edgeTris,
188  const bool optimal
189  );
190 
191  //- Perform triangulation of a polygon, first by adding a spanning
192  // triangle between a point and an edge, then recursing into the
193  // sub-polygons on either side
194  void partitionTriangulate
195  (
196  const UList<point>& points,
197  const vector& normal,
198  const label spanPointi,
199  const label spanEdgei,
200  UList<triFace>& triPoints,
202  UList<labelPair>& edgeTris,
203  const bool simple,
204  const bool optimal
205  );
206 
207  //- Perform triangulation of the given polygon, detecting self
208  // intersections and resolving them by adding spanning triangles prior
209  // to simple triangulation
210  void complexTriangulate
211  (
212  const UList<point>& points,
213  const vector& normal,
214  UList<triFace>& triPoints,
216  UList<labelPair>& edgeTris,
217  const bool optimal
218  );
219 
220  //- Perform triangulation of the given polygon
221  void triangulate
222  (
223  const UList<point>& points,
224  const vector& normal,
225  UList<triFace>& triPoints,
227  UList<labelPair>& edgeTris,
228  const bool simple = false,
229  const bool optimal = true
230  );
231 
232 
233 public:
234 
235  // Static Member Functions
236 
237  //- Generate a random polygon for testing purposes
239  (
240  Random& rndGen,
241  const label n,
242  const scalar error
243  );
244 
245 
246 
247  // Constructors
248 
249  //- Construct null
251 
252  //- Disallow default bitwise copy construction
253  polygonTriangulate(const polygonTriangulate&) = delete;
254 
255 
256  //- Destructor
258 
259 
260  // Member Functions
261 
262  // Access
263 
264  //- Get the triangles' points
265  inline const UList<triFace>& triPoints() const;
266 
267  //- Get the triangles' renumbered points
268  inline List<triFace> triPoints
269  (
270  const UList<label>& polyPoints
271  ) const;
272 
273  //- Get a triangle's renumbered points
274  inline triFace triPoints
275  (
276  const label trii,
277  const UList<label>& polyPoints
278  ) const;
279 
280  //- Get the triangles' edges
281  inline const UList<FixedList<label, 3>>& triEdges() const;
282 
283  //- Get the triangles' renumbered edges
285  (
286  const UList<label>& polyEdges
287  ) const;
288 
289  //- Get a triangle's renumbered edges
291  (
292  const label trii,
293  const UList<label>& polyEdges
294  ) const;
295 
296 
297  //- Perform triangulation of the given polygon
298  const UList<triFace>& triangulate
299  (
300  const UList<point>& points,
301  const vector& normal,
302  const bool simple = false,
303  const bool optimal = true
304  );
305 
306  //- Perform triangulation of the given polygon
307  const UList<triFace>& triangulate
308  (
309  const UList<point>& points,
310  const bool simple = false,
311  const bool optimal = true
312  );
313 
314  //- Perform triangulation of the given polygon
315  inline const UList<triFace>& triangulate
316  (
317  const UIndirectList<point>& points,
318  const vector& normal,
319  const bool simple = false,
320  const bool optimal = true
321  );
322 
323  //- Perform triangulation of the given polygon
324  inline const UList<triFace>& triangulate
325  (
326  const UIndirectList<point>& points,
327  const bool simple = false,
328  const bool optimal = true
329  );
330 
331 
332  // Member Operators
333 
334  //- Disallow default bitwise assignment
335  void operator=(const polygonTriangulate&) = delete;
336 };
337 
338 
339 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
340 
341 } // End namespace Foam
342 
343 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
344 
345 #include "polygonTriangulateI.H"
346 
347 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
348 
349 #endif
350 
351 // ************************************************************************* //
A HashTable with keys but without contents.
Definition: HashSet.H:59
A 1D array of objects of type <T>, where the size of the vector is known and used for subscript bound...
Definition: HashTable.H:59
const UList< FixedList< label, 3 > > & triEdges() const
Get the triangles&#39; edges.
polygonTriangulate()
Construct null.
Class to handle errors and exceptions in a simple, consistent stream-based manner.
Definition: error.H:67
Random rndGen(label(0))
Foam::intersection.
Definition: intersection.H:49
const pointField & points
A 1D vector of objects of type <T> that resizes itself as necessary to accept the new objects...
Definition: DynamicList.H:56
An edge is a list of two point labels. The functionality it provides supports the discretisation on a...
Definition: edge.H:58
A triangular face using a FixedList of labels corresponding to mesh vertices.
Definition: triFace.H:68
static List< point > randomPolygon(Random &rndGen, const label n, const scalar error)
Generate a random polygon for testing purposes.
void operator=(const polygonTriangulate &)=delete
Disallow default bitwise assignment.
A 1D vector of objects of type <T>, where the size of the vector is known and can be used for subscri...
Definition: HashTable.H:60
Random number generator.
Definition: Random.H:57
Triangulation of three-dimensional polygons.
A List with indirect addressing.
Definition: fvMatrix.H:106
label n
const UList< triFace > & triPoints() const
Get the triangles&#39; points.
Namespace for OpenFOAM.
simpleControl simple(mesh)