source: molecuilder/src/tesselation.hpp@ f7490d

Last change on this file since f7490d was f7490d, checked in by Frederik Heber <heber@…>, 16 years ago

First compiling version of CorrectDegeneratedPolygons.
  • Property mode set to 100644
File size: 13.8 KB
Line 
1/*
2 * tesselation.hpp
3 *
4 * The tesselation class is meant to contain the envelope (concave, convex or neither) of a set of Vectors. As we actually mean this stuff for atoms, we have to encapsulate it all a bit.
5 *
6 * Created on: Aug 3, 2009
7 * Author: heber
8 */
9
10#ifndef TESSELATION_HPP_
11#define TESSELATION_HPP_
12
13using namespace std;
14
15/*********************************************** includes ***********************************/
16
17// include config.h
18#ifdef HAVE_CONFIG_H
19#include <config.h>
20#endif
21
22#include <map>
23#include <list>
24#include <set>
25
26#include "atom_particleinfo.hpp"
27#include "helpers.hpp"
28#include "vector.hpp"
29
30/****************************************** forward declarations *****************************/
31
32class BoundaryPointSet;
33class BoundaryLineSet;
34class BoundaryTriangleSet;
35class LinkedCell;
36class TesselPoint;
37class PointCloud;
38class Tesselation;
39
40/********************************************** definitions *********************************/
41
42#define DoTecplotOutput 1
43#define DoRaster3DOutput 1
44#define DoVRMLOutput 1
45#define TecplotSuffix ".dat"
46#define Raster3DSuffix ".r3d"
47#define VRMLSUffix ".wrl"
48
49// ======================================================= some template functions =========================================
50
51#define PointMap map < int, class BoundaryPointSet * >
52#define PointSet set < class BoundaryPointSet * >
53#define PointList list < class BoundaryPointSet * >
54#define PointPair pair < int, class BoundaryPointSet * >
55#define PointTestPair pair < PointMap::iterator, bool >
56
57#define CandidateList list <class CandidateForTesselation *>
58#define CandidateMap map <class BoundaryLineSet *, class CandidateForTesselation *>
59
60#define LineMap multimap < int, class BoundaryLineSet * >
61#define LineSet set < class BoundaryLineSet * >
62#define LineList list < class BoundaryLineSet * >
63#define LinePair pair < int, class BoundaryLineSet * >
64#define LineTestPair pair < LineMap::iterator, bool >
65
66#define TriangleMap map < int, class BoundaryTriangleSet * >
67#define TriangleSet set < class BoundaryTriangleSet * >
68#define TriangleList list < class BoundaryTriangleSet * >
69#define TrianglePair pair < int, class BoundaryTriangleSet * >
70#define TriangleTestPair pair < TrianglePair::iterator, bool >
71
72#define PolygonMap map < int, class BoundaryPolygonSet * >
73#define PolygonSet set < class BoundaryPolygonSet * >
74#define PolygonList list < class BoundaryPolygonSet * >
75
76#define DistanceMultiMap multimap <double, pair < PointMap::iterator, PointMap::iterator> >
77#define DistanceMultiMapPair pair <double, pair < PointMap::iterator, PointMap::iterator> >
78
79#define TesselPointList list <TesselPoint *>
80#define TesselPointSet set <TesselPoint *>
81
82/********************************************** declarations *******************************/
83
84template <typename T> void SetEndpointsOrdered(T endpoints[2], T endpoint1, T endpoint2)
85{
86 if (endpoint1->Nr < endpoint2->Nr) {
87 endpoints[0] = endpoint1;
88 endpoints[1] = endpoint2;
89 } else {
90 endpoints[0] = endpoint2;
91 endpoints[1] = endpoint1;
92 }
93};
94
95// ======================================================== class BoundaryPointSet =========================================
96
97class BoundaryPointSet {
98 public:
99 BoundaryPointSet();
100 BoundaryPointSet(TesselPoint * Walker);
101 ~BoundaryPointSet();
102
103 void AddLine(class BoundaryLineSet *line);
104
105 LineMap lines;
106 int LinesCount;
107 TesselPoint *node;
108 double value;
109 int Nr;
110};
111
112ostream & operator << (ostream &ost, const BoundaryPointSet &a);
113
114// ======================================================== class BoundaryLineSet ==========================================
115
116class BoundaryLineSet {
117 public:
118 BoundaryLineSet();
119 BoundaryLineSet(class BoundaryPointSet *Point[2], const int number);
120 ~BoundaryLineSet();
121
122 void AddTriangle(class BoundaryTriangleSet *triangle);
123 bool IsConnectedTo(class BoundaryLineSet *line);
124 bool ContainsBoundaryPoint(class BoundaryPointSet *point);
125 bool CheckConvexityCriterion();
126 class BoundaryPointSet *GetOtherEndpoint(class BoundaryPointSet *);
127
128 class BoundaryPointSet *endpoints[2];
129 TriangleMap triangles;
130 int Nr;
131 bool skipped;
132};
133
134ostream & operator << (ostream &ost, const BoundaryLineSet &a);
135
136// ======================================================== class BoundaryTriangleSet =======================================
137
138class BoundaryTriangleSet {
139 public:
140 BoundaryTriangleSet();
141 BoundaryTriangleSet(class BoundaryLineSet *line[3], int number);
142 ~BoundaryTriangleSet();
143
144 void GetNormalVector(Vector &NormalVector);
145 void GetCenter(Vector *center);
146 bool GetIntersectionInsideTriangle(Vector *MolCenter, Vector *x, Vector *Intersection);
147 bool ContainsBoundaryLine(class BoundaryLineSet *line);
148 bool ContainsBoundaryPoint(class BoundaryPointSet *point);
149 bool ContainsBoundaryPoint(class TesselPoint *point);
150 class BoundaryPointSet *GetThirdEndpoint(class BoundaryLineSet *line);
151 bool IsPresentTupel(class BoundaryPointSet *Points[3]);
152 bool IsPresentTupel(class BoundaryTriangleSet *T);
153
154 class BoundaryPointSet *endpoints[3];
155 class BoundaryLineSet *lines[3];
156 Vector NormalVector;
157 int Nr;
158};
159
160ostream & operator << (ostream &ost, const BoundaryTriangleSet &a);
161
162
163// ======================================================== class BoundaryTriangleSet =======================================
164
165/** Set of BoundaryPointSet.
166 * This is just meant as a container for a group of endpoints, extending the node, line, triangle concept. However, this has
167 * only marginally something to do with the tesselation. Hence, there is no incorporation into the bookkeeping of the Tesselation
168 * class (i.e. no allocation, no deletion).
169 * \note we assume that the set of endpoints reside (more or less) on a plane.
170 */
171class BoundaryPolygonSet {
172 public:
173 BoundaryPolygonSet();
174 ~BoundaryPolygonSet();
175
176 Vector * GetNormalVector(const Vector &NormalVector) const;
177 void GetCenter(Vector *center) const;
178 bool ContainsBoundaryLine(const BoundaryLineSet * const line) const;
179 bool ContainsBoundaryPoint(const BoundaryPointSet * const point) const;
180 bool ContainsBoundaryPoint(const TesselPoint * const point) const;
181 bool ContainsBoundaryTriangle(const BoundaryTriangleSet * const point) const;
182 bool ContainsPresentTupel(const BoundaryPointSet * const * Points, const int dim) const;
183 bool ContainsPresentTupel(const BoundaryPolygonSet * const P) const;
184 bool ContainsPresentTupel(const PointSet &endpoints) const;
185 TriangleSet * GetAllTrianglesFromEndpoints() const;
186 bool FillPolygonFromTrianglesOfLine(const BoundaryLineSet * const line);
187
188 PointSet endpoints;
189 int Nr;
190};
191
192ostream & operator << (ostream &ost, const BoundaryPolygonSet &a);
193
194// =========================================================== class TESSELPOINT ===========================================
195
196/** Is a single point of the set of Vectors, also a super-class to be inherited and and its functions to be implemented.
197 */
198class TesselPoint : virtual public ParticleInfo {
199public:
200 TesselPoint();
201 virtual ~TesselPoint();
202
203 Vector *node; // pointer to position of the dot in space
204
205 virtual ostream & operator << (ostream &ost);
206};
207
208ostream & operator << (ostream &ost, const TesselPoint &a);
209
210// =========================================================== class POINTCLOUD ============================================
211
212/** Super-class for all point clouds structures, also molecules. They have to inherit this structure and implement the virtual function to access the Vectors.
213 * This basically encapsulates a list structure.
214 */
215class PointCloud {
216public:
217 PointCloud();
218 virtual ~PointCloud();
219
220 virtual const char * const GetName() const { return "unknown"; };
221 virtual Vector *GetCenter() const { return NULL; };
222 virtual TesselPoint *GetPoint() const { return NULL; };
223 virtual TesselPoint *GetTerminalPoint() const { return NULL; };
224 virtual void GoToNext() const {};
225 virtual void GoToPrevious() const {};
226 virtual void GoToFirst() const {};
227 virtual void GoToLast() const {};
228 virtual bool IsEmpty() const { return true; };
229 virtual bool IsEnd() const { return true; };
230};
231
232// ======================================================== class CandidateForTesselation =========================================
233
234class CandidateForTesselation {
235 public :
236 CandidateForTesselation(BoundaryLineSet* currentBaseLine);
237 CandidateForTesselation(TesselPoint* candidate, BoundaryLineSet* currentBaseLine, Vector OptCandidateCenter, Vector OtherOptCandidateCenter);
238 ~CandidateForTesselation();
239
240 TesselPointList pointlist;
241 BoundaryLineSet *BaseLine;
242 Vector OptCenter;
243 Vector OtherOptCenter;
244 double ShortestAngle;
245 double OtherShortestAngle;
246};
247
248ostream & operator <<(ostream &ost, const CandidateForTesselation &a);
249
250// =========================================================== class TESSELATION ===========================================
251
252/** Contains the envelope to a PointCloud.
253 */
254class Tesselation : public PointCloud {
255 public:
256
257 Tesselation();
258 virtual ~Tesselation();
259
260 void AddTesselationPoint(TesselPoint* Candidate, const int n);
261 void SetTesselationPoint(TesselPoint* Candidate, const int n) const;
262 void AddTesselationLine(class BoundaryPointSet *a, class BoundaryPointSet *b, const int n);
263 void AlwaysAddTesselationTriangleLine(class BoundaryPointSet *a, class BoundaryPointSet *b, const int n);
264 void AddTesselationTriangle();
265 void AddTesselationTriangle(const int nr);
266 void AddCandidateTriangle(CandidateForTesselation CandidateLine);
267 void RemoveTesselationTriangle(class BoundaryTriangleSet *triangle);
268 void RemoveTesselationLine(class BoundaryLineSet *line);
269 void RemoveTesselationPoint(class BoundaryPointSet *point);
270
271
272 // concave envelope
273 void FindStartingTriangle(const double RADIUS, const LinkedCell *LC);
274 void FindSecondPointForTesselation(class TesselPoint* a, Vector Oben, class TesselPoint*& OptCandidate, double Storage[3], double RADIUS, const LinkedCell *LC);
275 void FindThirdPointForTesselation(Vector &NormalVector, Vector &SearchDirection, Vector &OldSphereCenter, CandidateForTesselation &CandidateLine, const class TesselPoint * const ThirdNode, const double RADIUS, const LinkedCell *LC) const;
276 bool FindNextSuitableTriangle(CandidateForTesselation &CandidateLine, BoundaryTriangleSet &T, const double& RADIUS, const LinkedCell *LC);
277 int CheckPresenceOfTriangle(class TesselPoint *Candidates[3]) const;
278 class BoundaryTriangleSet * GetPresentTriangle(TesselPoint *Candidates[3]);
279
280 // convex envelope
281 void TesselateOnBoundary(const PointCloud * const cloud);
282 void GuessStartingTriangle();
283 bool InsertStraddlingPoints(const PointCloud *cloud, const LinkedCell *LC);
284 double RemovePointFromTesselatedSurface(class BoundaryPointSet *point);
285 class BoundaryLineSet * FlipBaseline(class BoundaryLineSet *Base);
286 double PickFarthestofTwoBaselines(class BoundaryLineSet *Base);
287 class BoundaryPointSet *IsConvexRectangle(class BoundaryLineSet *Base);
288 map<int, int> * FindAllDegeneratedTriangles();
289 map<int, int> * FindAllDegeneratedLines();
290 void RemoveDegeneratedTriangles();
291 void AddBoundaryPointByDegeneratedTriangle(class TesselPoint *point, LinkedCell *LC);
292 int CorrectAllDegeneratedPolygons();
293
294 set<TesselPoint*> * GetAllConnectedPoints(const TesselPoint* const Point) const;
295 set<BoundaryTriangleSet*> *GetAllTriangles(const BoundaryPointSet * const Point) const;
296 list<list<TesselPoint*> *> * GetPathsOfConnectedPoints(const TesselPoint* const Point) const;
297 list<list<TesselPoint*> *> * GetClosedPathsOfConnectedPoints(const TesselPoint* const Point) const;
298 list<TesselPoint*> * GetCircleOfSetOfPoints(set<TesselPoint*> *SetOfNeighbours, const TesselPoint* const Point, const Vector * const Reference = NULL) const;
299 class BoundaryPointSet *GetCommonEndpoint(const BoundaryLineSet * line1, const BoundaryLineSet * line2) const;
300 list<BoundaryTriangleSet*> *FindTriangles(const TesselPoint* const Points[3]) const;
301 list<BoundaryTriangleSet*> * FindClosestTrianglesToPoint(const Vector *x, const LinkedCell* LC) const;
302 class BoundaryTriangleSet * FindClosestTriangleToPoint(const Vector *x, const LinkedCell* LC) const;
303 bool IsInnerPoint(const Vector &Point, const LinkedCell* const LC) const;
304 bool IsInnerPoint(const TesselPoint * const Point, const LinkedCell* const LC) const;
305 bool AddBoundaryPoint(TesselPoint * Walker, const int n);
306
307 // print for debugging
308 void PrintAllBoundaryPoints(ofstream *out) const;
309 void PrintAllBoundaryLines(ofstream *out) const;
310 void PrintAllBoundaryTriangles(ofstream *out) const;
311
312 // store envelope in file
313 void Output(const char *filename, const PointCloud * const cloud);
314
315 PointMap PointsOnBoundary;
316 LineMap LinesOnBoundary;
317 CandidateMap OpenLines;
318 TriangleMap TrianglesOnBoundary;
319 int PointsOnBoundaryCount;
320 int LinesOnBoundaryCount;
321 int TrianglesOnBoundaryCount;
322
323 // PointCloud implementation for PointsOnBoundary
324 virtual Vector *GetCenter(ofstream *out) const;
325 virtual TesselPoint *GetPoint() const;
326 virtual TesselPoint *GetTerminalPoint() const;
327 virtual void GoToNext() const;
328 virtual void GoToPrevious() const;
329 virtual void GoToFirst() const;
330 virtual void GoToLast() const;
331 virtual bool IsEmpty() const;
332 virtual bool IsEnd() const;
333
334 class BoundaryPointSet *BPS[2];
335 class BoundaryLineSet *BLS[3];
336 class BoundaryTriangleSet *BTS;
337 class BoundaryTriangleSet *LastTriangle;
338 int TriangleFilesWritten;
339
340 private:
341 mutable class BoundaryPointSet *TPS[3]; //this is a Storage for pointers to triangle points, this and BPS[2] needed due to AddLine restrictions
342
343 mutable PointMap::const_iterator InternalPointer;
344
345 //bool HasOtherBaselineBetterCandidate(const BoundaryLineSet * const BaseRay, const TesselPoint * const OptCandidate, double ShortestAngle, double RADIUS, const LinkedCell * const LC) const;
346};
347
348
349#endif /* TESSELATION_HPP_ */
Note: See TracBrowser for help on using the repository browser.