Changeset d6b011 for molecuilder/src

Timestamp:

Aug 18, 2009, 1:59:11 PM (16 years ago)

Author:

Saskia Metzler <metzler@…>

Children:

84b811

Parents:

48cd93

Message:

Ticket 15: new function RemoveDegeneratedTriangles()
Added functions to find and remove surplus degenerated triangles.

Location:

molecuilder/src

Files:

• boundary.cpp (modified) (2 diffs)
• tesselation.cpp (modified) (3 diffs)
• tesselation.hpp (modified) (2 diffs)

molecuilder/src/boundary.cpp

@@ -1216 +1216 @@
   }
 
+  // Purges surplus triangles.
+  mol->TesselStruct->RemoveDegeneratedTriangles();
+
   // write final envelope
   if (filename != 0) {
@@ -1282 +1285 @@
 //    << "for atom " << a << " (inside)." << endl;
 
-
   if (freeLC)
     delete(LCList);

molecuilder/src/tesselation.cpp

@@ -2802 +2802 @@
 };
 
-
-
 /**
  * Finds the point which is closest to the provided one.
@@ -2860 +2858 @@
   return closestPoint;
 };
-
 
 /**
@@ -2927 +2924 @@
 }
 
+/**
+ * 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

molecuilder/src/tesselation.hpp

@@ -20 +20 @@
 #include <map>
 #include <list>
+#include <set>
 
 
@@ -217 +218 @@
     bool PickFarthestofTwoBaselines(ofstream *out, class BoundaryLineSet *Base);
     class BoundaryPointSet *IsConvexRectangle(ofstream *out, class BoundaryLineSet *Base);
-
+    map<int, int> FindAllDegeneratedTriangles();
+    void RemoveDegeneratedTriangles();
 
     list<TesselPoint*> * GetCircleOfConnectedPoints(ofstream *out, TesselPoint* Point);