Changeset 84b811 for molecuilder/src/tesselation.cpp

Timestamp:

Aug 20, 2009, 7:48:07 AM (16 years ago)

Author:

Frederik Heber <heber@…>

Children:

5f4960, 6c6d84

Parents:

78dac6 (diff), d6b011 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

git-author:

Frederik Heber <heber@…> (08/19/09 14:40:33)

git-committer:

Frederik Heber <heber@…> (08/20/09 07:48:07)

Message:

Merge branch 'ConcaveHull' of ​ssh://stud64d-02/home/metzler/workspace/espack into Ticket14

Conflicts:

molecuilder/src/boundary.cpp
molecuilder/src/tesselation.cpp

• in boundary.cpp: FindConvexBorder() - overlay due to PickFarthestofTwoBaselines()
• in tesselation.cpp: CheckConvexityCriterion() - overlay due to verbosity change on return, getAngle() -> GetAngle()

File:

• molecuilder/src/tesselation.cpp (modified) (42 diffs)

molecuilder/src/tesselation.cpp

@@ -219 +219 @@
     return true;
   }
-  double angle = getAngle(helper[0], helper[1], BaseLineNormal);
+  double angle = GetAngle(helper[0], helper[1], BaseLineNormal);
   if ((angle - M_PI) > -MYEPSILON) {
     *out << Verbose(2) << "ACCEPT: Angle is greater than pi: convex." << endl;
@@ -1402 +1402 @@
 
 
-/** Finds the starting triangle for find_non_convex_border().
- * Looks at the outermost point per axis, then Find_second_point_for_Tesselation()
- * for the second and Find_next_suitable_point_via_Angle_of_Sphere() for the third
+/** Finds the starting triangle for FindNonConvexBorder().
+ * Looks at the outermost point per axis, then FindSecondPointForTesselation()
+ * for the second and FindNextSuitablePointViaAngleOfSphere() for the third
  * point are called.
  * \param *out output stream for debugging
@@ -1410 +1410 @@
  * \param *LC LinkedCell structure with neighbouring TesselPoint's
  */
-void Tesselation::Find_starting_triangle(ofstream *out, const double RADIUS, LinkedCell *LC)
-{
-  cout << Verbose(1) << "Begin of Find_starting_triangle\n";
+void Tesselation::FindStartingTriangle(ofstream *out, const double RADIUS, LinkedCell *LC)
+{
+  cout << Verbose(1) << "Begin of FindStartingTriangle\n";
   int i = 0;
   LinkedNodes *List = NULL;
@@ -1418 +1418 @@
   TesselPoint* SecondPoint = NULL;
   TesselPoint* MaxPoint[NDIM];
-  double max_coordinate[NDIM];
+  double maxCoordinate[NDIM];
   Vector Oben;
   Vector helper;
@@ -1428 +1428 @@
   for (i = 0; i < 3; i++) {
     MaxPoint[i] = NULL;
-    max_coordinate[i] = -1;
+    maxCoordinate[i] = -1;
   }
 
@@ -1440 +1440 @@
         if (List != NULL) {
           for (LinkedNodes::iterator Runner = List->begin();Runner != List->end();Runner++) {
-            if ((*Runner)->node->x[i] > max_coordinate[i]) {
+            if ((*Runner)->node->x[i] > maxCoordinate[i]) {
               cout << Verbose(2) << "New maximal for axis " << i << " node is " << *(*Runner) << " at " << *(*Runner)->node << "." << endl;
-              max_coordinate[i] = (*Runner)->node->x[i];
+              maxCoordinate[i] = (*Runner)->node->x[i];
               MaxPoint[i] = (*Runner);
             }
@@ -1458 +1458 @@
 
   BTS = NULL;
-  CandidateList *Opt_Candidates = new CandidateList();
+  CandidateList *OptCandidates = new CandidateList();
   for (int k=0;k<NDIM;k++) {
     Oben.x[k] = 1.;
@@ -1465 +1465 @@
 
     double ShortestAngle;
-    TesselPoint* Opt_Candidate = NULL;
+    TesselPoint* OptCandidate = NULL;
     ShortestAngle = 999999.; // This will contain the angle, which will be always positive (when looking for second point), when looking for third point this will be the quadrant.
 
-    Find_second_point_for_Tesselation(FirstPoint, NULL, Oben, Opt_Candidate, &ShortestAngle, RADIUS, LC); // we give same point as next candidate as its bonds are looked into in find_second_...
-    SecondPoint = Opt_Candidate;
+    FindSecondPointForTesselation(FirstPoint, NULL, Oben, OptCandidate, &ShortestAngle, RADIUS, LC); // we give same point as next candidate as its bonds are looked into in find_second_...
+    SecondPoint = OptCandidate;
     if (SecondPoint == NULL)  // have we found a second point?
       continue;
@@ -1500 +1500 @@
 
     //cout << Verbose(2) << "INFO: OldSphereCenter is at " << helper << ".\n";
-    Find_third_point_for_Tesselation(
-      Oben, SearchDirection, helper, BLS[0], NULL, *&Opt_Candidates, &ShortestAngle, RADIUS, LC
+    FindThirdPointForTesselation(
+      Oben, SearchDirection, helper, BLS[0], NULL, *&OptCandidates, &ShortestAngle, RADIUS, LC
     );
     cout << Verbose(1) << "List of third Points is ";
-    for (CandidateList::iterator it = Opt_Candidates->begin(); it != Opt_Candidates->end(); ++it) {
+    for (CandidateList::iterator it = OptCandidates->begin(); it != OptCandidates->end(); ++it) {
         cout << " " << *(*it)->point;
     }
     cout << endl;
 
-    for (CandidateList::iterator it = Opt_Candidates->begin(); it != Opt_Candidates->end(); ++it) {
+    for (CandidateList::iterator it = OptCandidates->begin(); it != OptCandidates->end(); ++it) {
       // add third triangle point
       AddTesselationPoint((*it)->point, 2);
@@ -1526 +1526 @@
 
       // if we do not reach the end with the next step of iteration, we need to setup a new first line
-      if (it != Opt_Candidates->end()--) {
+      if (it != OptCandidates->end()--) {
         FirstPoint = (*it)->BaseLine->endpoints[0]->node;
         SecondPoint = (*it)->point;
@@ -1541 +1541 @@
       // remove all candidates from the list and then the list itself
       class CandidateForTesselation *remover = NULL;
-      for (CandidateList::iterator it = Opt_Candidates->begin(); it != Opt_Candidates->end(); ++it) {
+      for (CandidateList::iterator it = OptCandidates->begin(); it != OptCandidates->end(); ++it) {
         remover = *it;
         delete(remover);
       }
-      Opt_Candidates->clear();
+      OptCandidates->clear();
     }
   }
@@ -1551 +1551 @@
   // remove all candidates from the list and then the list itself
   class CandidateForTesselation *remover = NULL;
-  for (CandidateList::iterator it = Opt_Candidates->begin(); it != Opt_Candidates->end(); ++it) {
+  for (CandidateList::iterator it = OptCandidates->begin(); it != OptCandidates->end(); ++it) {
     remover = *it;
     delete(remover);
   }
-  delete(Opt_Candidates);
-  cout << Verbose(1) << "End of Find_starting_triangle\n";
+  delete(OptCandidates);
+  cout << Verbose(1) << "End of FindStartingTriangle\n";
 };
 
@@ -1568 +1568 @@
  * @param *LC LinkedCell structure with neighbouring points
  */
-bool Tesselation::Find_next_suitable_triangle(ofstream *out, BoundaryLineSet &Line, BoundaryTriangleSet &T, const double& RADIUS, int N, LinkedCell *LC)
-{
-  cout << Verbose(0) << "Begin of Find_next_suitable_triangle\n";
+bool Tesselation::FindNextSuitableTriangle(ofstream *out, BoundaryLineSet &Line, BoundaryTriangleSet &T, const double& RADIUS, int N, LinkedCell *LC)
+{
+  cout << Verbose(0) << "Begin of FindNextSuitableTriangle\n";
   bool result = true;
-  CandidateList *Opt_Candidates = new CandidateList();
+  CandidateList *OptCandidates = new CandidateList();
 
   Vector CircleCenter;
@@ -1629 +1629 @@
 
     // add third point
-    Find_third_point_for_Tesselation(
-      T.NormalVector, SearchDirection, OldSphereCenter, &Line, ThirdNode, Opt_Candidates,
+    FindThirdPointForTesselation(
+      T.NormalVector, SearchDirection, OldSphereCenter, &Line, ThirdNode, OptCandidates,
       &ShortestAngle, RADIUS, LC
     );
@@ -1638 +1638 @@
   }
 
-  if (Opt_Candidates->begin() == Opt_Candidates->end()) {
+  if (OptCandidates->begin() == OptCandidates->end()) {
     cerr << "WARNING: Could not find a suitable candidate." << endl;
     return false;
   }
   cout << Verbose(1) << "Third Points are ";
-  for (CandidateList::iterator it = Opt_Candidates->begin(); it != Opt_Candidates->end(); ++it) {
+  for (CandidateList::iterator it = OptCandidates->begin(); it != OptCandidates->end(); ++it) {
     cout << " " << *(*it)->point;
   }
@@ -1649 +1649 @@
 
   BoundaryLineSet *BaseRay = &Line;
-  for (CandidateList::iterator it = Opt_Candidates->begin(); it != Opt_Candidates->end(); ++it) {
+  for (CandidateList::iterator it = OptCandidates->begin(); it != OptCandidates->end(); ++it) {
     cout << Verbose(1) << " Third point candidate is " << *(*it)->point
     << " with circumsphere's center at " << (*it)->OptCenter << "." << endl;
@@ -1668 +1668 @@
       AddTesselationPoint(BaseRay->endpoints[1]->node, 2);
 
-      if (CheckLineCriteriaforDegeneratedTriangle(TPS)) {
+      if (CheckLineCriteriaForDegeneratedTriangle(TPS)) {
         AddTesselationLine(TPS[0], TPS[1], 0);
         AddTesselationLine(TPS[0], TPS[2], 1);
@@ -1697 +1697 @@
         // We demand that at most one new degenerate line is created and that this line also already exists (which has to be the case due to existentTrianglesCount == 1)
         // i.e. at least one of the three lines must be present with TriangleCount <= 1
-        if (CheckLineCriteriaforDegeneratedTriangle(TPS)) {
+        if (CheckLineCriteriaForDegeneratedTriangle(TPS)) {
           AddTesselationLine(TPS[0], TPS[1], 0);
           AddTesselationLine(TPS[0], TPS[2], 1);
@@ -1735 +1735 @@
   // remove all candidates from the list and then the list itself
   class CandidateForTesselation *remover = NULL;
-  for (CandidateList::iterator it = Opt_Candidates->begin(); it != Opt_Candidates->end(); ++it) {
+  for (CandidateList::iterator it = OptCandidates->begin(); it != OptCandidates->end(); ++it) {
     remover = *it;
     delete(remover);
   }
-  delete(Opt_Candidates);
-  cout << Verbose(0) << "End of Find_next_suitable_triangle\n";
+  delete(OptCandidates);
+  cout << Verbose(0) << "End of FindNextSuitableTriangle\n";
   return result;
 };
@@ -2047 +2047 @@
  * \param *Candidate pointer to candidate node on return
  * \param Oben vector indicating the outside
- * \param Opt_Candidate reference to recommended candidate on return
+ * \param OptCandidate reference to recommended candidate on return
  * \param Storage[3] array storing angles and other candidate information
  * \param RADIUS radius of virtual sphere
  * \param *LC LinkedCell structure with neighbouring points
  */
-void Tesselation::Find_second_point_for_Tesselation(TesselPoint* a, TesselPoint* Candidate, Vector Oben, TesselPoint*& Opt_Candidate, double Storage[3], double RADIUS, LinkedCell *LC)
-{
-  cout << Verbose(2) << "Begin of Find_second_point_for_Tesselation" << endl;
+void Tesselation::FindSecondPointForTesselation(TesselPoint* a, TesselPoint* Candidate, Vector Oben, TesselPoint*& OptCandidate, double Storage[3], double RADIUS, LinkedCell *LC)
+{
+  cout << Verbose(2) << "Begin of FindSecondPointForTesselation" << endl;
   Vector AngleCheck;
   double norm = -1., angle;
@@ -2092 +2092 @@
             if (a != Candidate) {
               // Calculate center of the circle with radius RADIUS through points a and Candidate
-              Vector OrthogonalizedOben, a_Candidate, Center;
+              Vector OrthogonalizedOben, aCandidate, Center;
               double distance, scaleFactor;
 
               OrthogonalizedOben.CopyVector(&Oben);
-              a_Candidate.CopyVector(a->node);
-              a_Candidate.SubtractVector(Candidate->node);
-              OrthogonalizedOben.ProjectOntoPlane(&a_Candidate);
+              aCandidate.CopyVector(a->node);
+              aCandidate.SubtractVector(Candidate->node);
+              OrthogonalizedOben.ProjectOntoPlane(&aCandidate);
               OrthogonalizedOben.Normalize();
-              distance = 0.5 * a_Candidate.Norm();
+              distance = 0.5 * aCandidate.Norm();
               scaleFactor = sqrt(((RADIUS * RADIUS) - (distance * distance)));
               OrthogonalizedOben.Scale(scaleFactor);
@@ -2111 +2111 @@
               AngleCheck.CopyVector(&Center);
               AngleCheck.SubtractVector(a->node);
-              norm = a_Candidate.Norm();
+              norm = aCandidate.Norm();
               // second point shall have smallest angle with respect to Oben vector
               if (norm < RADIUS*2.) {
@@ -2118 +2118 @@
                   //cout << Verbose(3) << "Old values of Storage: %lf %lf \n", Storage[0], Storage[1]);
                   cout << Verbose(3) << "Current candidate is " << *Candidate << ": Is a better candidate with distance " << norm << " and angle " << angle << " to oben " << Oben << ".\n";
-                  Opt_Candidate = Candidate;
+                  OptCandidate = Candidate;
                   Storage[0] = angle;
                   //cout << Verbose(3) << "Changing something in Storage: %lf %lf. \n", Storage[0], Storage[2]);
                 } else {
-                  //cout << Verbose(3) << "Current candidate is " << *Candidate << ": Looses with angle " << angle << " to a better candidate " << *Opt_Candidate << endl;
+                  //cout << Verbose(3) << "Current candidate is " << *Candidate << ": Looses with angle " << angle << " to a better candidate " << *OptCandidate << endl;
                 }
               } else {
@@ -2135 +2135 @@
         }
       }
-  cout << Verbose(2) << "End of Find_second_point_for_Tesselation" << endl;
+  cout << Verbose(2) << "End of FindSecondPointForTesselation" << endl;
 };
 
@@ -2161 +2161 @@
  * holds. Then, the normalized projection onto the SearchDirection is either +1 or -1 and thus states whether
  * the angle is uniquely in either (0,M_PI] or [M_PI, 2.*M_PI).
- * @param NormalVector normal direction of the base triangle (here the unit axis vector, \sa Find_starting_triangle())
+ * @param NormalVector normal direction of the base triangle (here the unit axis vector, \sa FindStartingTriangle())
  * @param SearchDirection general direction where to search for the next point, relative to center of BaseLine
  * @param OldSphereCenter center of sphere for base triangle, relative to center of BaseLine, giving null angle for the parameter circle
@@ -2167 +2167 @@
  * @param ThirdNode third point to avoid in search
  * @param candidates list of equally good candidates to return
- * @param ShortestAngle the current path length on this circle band for the current Opt_Candidate
+ * @param ShortestAngle the current path length on this circle band for the current OptCandidate
  * @param RADIUS radius of sphere
  * @param *LC LinkedCell structure with neighbouring points
  */
-void Tesselation::Find_third_point_for_Tesselation(Vector NormalVector, Vector SearchDirection, Vector OldSphereCenter, class BoundaryLineSet *BaseLine, class TesselPoint  *ThirdNode, CandidateList* &candidates, double *ShortestAngle, const double RADIUS, LinkedCell *LC)
+void Tesselation::FindThirdPointForTesselation(Vector NormalVector, Vector SearchDirection, Vector OldSphereCenter, class BoundaryLineSet *BaseLine, class TesselPoint  *ThirdNode, CandidateList* &candidates, double *ShortestAngle, const double RADIUS, LinkedCell *LC)
 {
   Vector CircleCenter;  // center of the circle, i.e. of the band of sphere's centers
@@ -2188 +2188 @@
   CandidateForTesselation *optCandidate = NULL;
 
-  cout << Verbose(1) << "Begin of Find_third_point_for_Tesselation" << endl;
+  cout << Verbose(1) << "Begin of FindThirdPointForTesselation" << endl;
 
   //cout << Verbose(2) << "INFO: NormalVector of BaseTriangle is " << NormalVector << "." << endl;
@@ -2345 +2345 @@
   if (candidates->size() > 1) {
     candidates->unique();
-    candidates->sort(sortCandidates);
-  }
-
-  cout << Verbose(1) << "End of Find_third_point_for_Tesselation" << endl;
+    candidates->sort(SortCandidates);
+  }
+
+  cout << Verbose(1) << "End of FindThirdPointForTesselation" << endl;
 };
 
@@ -2397 +2397 @@
   }
 
-  trianglePoints[0] = findClosestPoint(x, SecondPoint, LC);
+  trianglePoints[0] = FindClosestPoint(x, SecondPoint, LC);
   
   // check whether closest point is "too close" :), then it's inside
@@ -2408 +2408 @@
     return NULL;
   }
-  list<TesselPoint*> *connectedPoints = getCircleOfConnectedPoints(out, trianglePoints[0]);
-  list<TesselPoint*> *connectedClosestPoints = getNeighboursonCircleofConnectedPoints(out, connectedPoints, trianglePoints[0], x);
+  list<TesselPoint*> *connectedPoints = GetCircleOfConnectedPoints(out, trianglePoints[0]);
+  list<TesselPoint*> *connectedClosestPoints = GetNeighboursOnCircleOfConnectedPoints(out, connectedPoints, trianglePoints[0], x);
   delete(connectedPoints);
   trianglePoints[1] = connectedClosestPoints->front();
@@ -2497 +2497 @@
  * @return list of the all points linked to the provided one
  */
-list<TesselPoint*> * Tesselation::getCircleOfConnectedPoints(ofstream *out, TesselPoint* Point)
+list<TesselPoint*> * Tesselation::GetCircleOfConnectedPoints(ofstream *out, TesselPoint* Point)
 {
   list<TesselPoint*> *connectedPoints = new list<TesselPoint*>;
@@ -2558 +2558 @@
  * @return list of the two points linked to the provided one and closest to the point to be checked,
  */
-list<TesselPoint*> * Tesselation::getNeighboursonCircleofConnectedPoints(ofstream *out, list<TesselPoint*> *connectedPoints, TesselPoint* Point, Vector* Reference)
+list<TesselPoint*> * Tesselation::GetNeighboursOnCircleOfConnectedPoints(ofstream *out, list<TesselPoint*> *connectedPoints, TesselPoint* Point, Vector* Reference)
 {
   map<double, TesselPoint*> anglesOfPoints;
@@ -2597 +2597 @@
     helper.SubtractVector(Point->node);
     helper.ProjectOntoPlane(&PlaneNormal);
-    double angle = getAngle(helper, AngleZero, OrthogonalVector);
+    double angle = GetAngle(helper, AngleZero, OrthogonalVector);
     *out << Verbose(2) << "INFO: Calculated angle is " << angle << " for point " << **listRunner << "." << endl;
     anglesOfPoints.insert(pair<double, TesselPoint*>(angle, (*listRunner)));
@@ -2644 +2644 @@
     return 0.;
   }
-  list<TesselPoint*> *CircleofPoints = getCircleOfConnectedPoints(out, point->node);
+  list<TesselPoint*> *CircleofPoints = GetCircleOfConnectedPoints(out, point->node);
 
   // remove all triangles
@@ -2716 +2716 @@
  * \return true - there is such a line (i.e. creation of degenerated triangle is valid), false - no such line (don't create)
  */
-bool CheckLineCriteriaforDegeneratedTriangle(class BoundaryPointSet *nodes[3])
+bool CheckLineCriteriaForDegeneratedTriangle(class BoundaryPointSet *nodes[3])
 {
   bool result = false;
@@ -2750 +2750 @@
 /** Sort function for the candidate list.
  */
-bool sortCandidates(CandidateForTesselation* candidate1, CandidateForTesselation* candidate2) 
+bool SortCandidates(CandidateForTesselation* candidate1, CandidateForTesselation* candidate2)
 {
   Vector BaseLineVector, OrthogonalVector, helper;
@@ -2800 +2800 @@
  * @return point which is second closest to the provided one
  */
-TesselPoint* findSecondClosestPoint(const Vector* Point, LinkedCell* LC)
+TesselPoint* FindSecondClosestPoint(const Vector* Point, LinkedCell* LC)
 {
   LinkedNodes *List = NULL;
@@ -2846 +2846 @@
 };
 
-
-
 /**
  * Finds the point which is closest to the provided one.
@@ -2857 +2855 @@
  * @return point which is closest to the provided one, NULL if none found
  */
-TesselPoint* findClosestPoint(const Vector* Point, TesselPoint *&SecondPoint, LinkedCell* LC)
+TesselPoint* FindClosestPoint(const Vector* Point, TesselPoint *&SecondPoint, LinkedCell* LC)
 {
   LinkedNodes *List = NULL;
@@ -2904 +2902 @@
   return closestPoint;
 };
-
 
 /**
@@ -2971 +2968 @@
 }
 
+/**
+ * Finds all degenerated triangles within the tesselation structure.
+ *
+ * @return map of keys of degenerated triangle pairs, each triangle occurs twice
+ *         in the list, once as key and once as value
+ */
+map<int, int> Tesselation::FindAllDegeneratedTriangles()
+{
+  map<int, int> DegeneratedTriangles;
+
+  // sanity check
+  if (LinesOnBoundary.empty()) {
+    cout << Verbose(1) << "Warning: FindAllDegeneratedTriangles() was called without any tesselation structure.";
+    return DegeneratedTriangles;
+  }
+
+  LineMap::iterator LineRunner1, LineRunner2;
+
+  for (LineRunner1 = LinesOnBoundary.begin(); LineRunner1 != LinesOnBoundary.end(); ++LineRunner1) {
+    for (LineRunner2 = LinesOnBoundary.begin(); LineRunner2 != LinesOnBoundary.end(); ++LineRunner2) {
+      if ((LineRunner1->second != LineRunner2->second)
+        && (LineRunner1->second->endpoints[0] == LineRunner2->second->endpoints[0])
+        && (LineRunner1->second->endpoints[1] == LineRunner2->second->endpoints[1])
+      ) {
+        TriangleMap::iterator TriangleRunner1 = LineRunner1->second->triangles.begin(),
+          TriangleRunner2 = LineRunner2->second->triangles.begin();
+
+        for (; TriangleRunner1 != LineRunner1->second->triangles.end(); ++TriangleRunner1) {
+          for (; TriangleRunner2 != LineRunner2->second->triangles.end(); ++TriangleRunner2) {
+            if ((TriangleRunner1->second != TriangleRunner2->second)
+              && (TriangleRunner1->second->endpoints[0] == TriangleRunner2->second->endpoints[0])
+              && (TriangleRunner1->second->endpoints[1] == TriangleRunner2->second->endpoints[1])
+              && (TriangleRunner1->second->endpoints[2] == TriangleRunner2->second->endpoints[2])
+            ) {
+              DegeneratedTriangles[TriangleRunner1->second->Nr] = TriangleRunner2->second->Nr;
+              DegeneratedTriangles[TriangleRunner2->second->Nr] = TriangleRunner1->second->Nr;
+            }
+          }
+        }
+      }
+    }
+  }
+
+  cout << Verbose(1) << "FindAllDegeneratedTriangles() found " << DegeneratedTriangles.size() << " triangles." << endl;
+  map<int,int>::iterator it;
+  for (it = DegeneratedTriangles.begin(); it != DegeneratedTriangles.end(); it++)
+      cout << Verbose(2) << (*it).first << " => " << (*it).second << endl;
+
+  return DegeneratedTriangles;
+}
+
+/**
+ * Purges degenerated triangles from the tesselation structure if they are not
+ * necessary to keep a single point within the structure.
+ */
+void Tesselation::RemoveDegeneratedTriangles()
+{
+  map<int, int> DegeneratedTriangles = FindAllDegeneratedTriangles();
+
+  for (map<int, int>::iterator TriangleKeyRunner = DegeneratedTriangles.begin();
+    TriangleKeyRunner != DegeneratedTriangles.end(); ++TriangleKeyRunner
+  ) {
+    BoundaryTriangleSet *triangle = TrianglesOnBoundary.find(TriangleKeyRunner->first)->second,
+      *partnerTriangle = TrianglesOnBoundary.find(TriangleKeyRunner->second)->second;
+
+    bool trianglesShareLine = false;
+    for (int i = 0; i < 3; ++i)
+      for (int j = 0; j < 3; ++j)
+        trianglesShareLine = trianglesShareLine || triangle->lines[i] == partnerTriangle->lines[j];
+
+    if (trianglesShareLine
+      && (triangle->endpoints[1]->LinesCount > 2)
+      && (triangle->endpoints[2]->LinesCount > 2)
+      && (triangle->endpoints[0]->LinesCount > 2)
+    ) {
+      cout << Verbose(1) << "RemoveDegeneratedTriangles() removes triangle " << *triangle << "." << endl;
+      RemoveTesselationTriangle(triangle);
+      cout << Verbose(1) << "RemoveDegeneratedTriangles() removes triangle " << *partnerTriangle << "." << endl;
+      RemoveTesselationTriangle(partnerTriangle);
+      DegeneratedTriangles.erase(DegeneratedTriangles.find(partnerTriangle->Nr));
+    } else {
+      cout << Verbose(1) << "RemoveDegeneratedTriangles() does not remove triangle " << *triangle
+        << " and its partner " << *partnerTriangle << " because it is essential for at"
+        << " least one of the endpoints to be kept in the tesselation structure." << endl;
+    }
+  }
+}
+
 /** Gets the angle between a point and a reference relative to the provided center.
  * We have two shanks point and reference between which the angle is calculated
@@ -2980 +3065 @@
  * @return angle between point and reference
  */
-double getAngle(const Vector &point, const Vector &reference, const Vector OrthogonalVector)
+double GetAngle(const Vector &point, const Vector &reference, const Vector OrthogonalVector)
 {
   if (reference.IsZero())