Changeset 70c4567 for molecuilder/src/boundary.cpp

Timestamp:

Aug 10, 2009, 4:11:47 PM (16 years ago)

Author:

Frederik Heber <heber@…>

Children:

ada6d2

Parents:

0cf171

Message:

New function ConvexizeNonconvexEnvelope() to calculate the volume of a non-convex envelope.

The central idea is that the volume of a convex envelope is easy to determine as a sum of pyramids with respect to a center inside the envelope. Hence, if we can "reduce" the non-convex envelope to a convex one in such a way that we know the added volume, we may determine the volume of a non-convex envelope.
The nice side effect is that we may use our Find_non_convex_border() algorithm to calculate also the convex envelope.

• We go through all BoundaryPoints and check whether one of its Baselines does not fulfill the ConvexCriterion. If so, we remove it, as it can not be a boundary point on the convex envelope, and re-construct the attached triangles. The added volume is a general tetraeder, whose formula is known.
• FIX: Find_convex_border() - We check whether AddPoint is successful or not.
• builder.cpp: case 'o' - changed to use ConvexizeNonconvexEnvelope() instead of Find_convex_border()
• Tesselation:AddPoint() - now takes second argument which is the index for BPS and always set BPS to either the newly created or the already present point. Return argument discerns between new and already present point.
• Tesselation::BPS, BLS, BTS are now public not private. We have to access them from ConvexizeNonconvexEnvelope()

File:

• molecuilder/src/boundary.cpp (modified) (2 diffs)

molecuilder/src/boundary.cpp

@@ -476 +476 @@
   for (int axis = 0; axis < NDIM; axis++)
     for (Boundaries::iterator runner = BoundaryPoints[axis].begin(); runner != BoundaryPoints[axis].end(); runner++)
-        mol->TesselStruct->AddPoint(runner->second.second);
+        if (!mol->TesselStruct->AddPoint(runner->second.second, 0))
+          *out << Verbose(3) << "WARNING: Point " << *(runner->second.second) << " is already present!" << endl;
 
   *out << Verbose(2) << "I found " << mol->TesselStruct->PointsOnBoundaryCount << " points on the convex boundary." << endl;
@@ -560 +561 @@
 };
 
+/** Creates a convex envelope from a given non-convex one.
+ * -# We go through all PointsOnBoundary.
+ * -# We look at each of its lines and CheckConvexityCriterion().
+ * -# If any returns concave, this Point cannot be on the final convex envelope.
+ * -# Hence, we remove it and re-create all its triangles from its getCircleOfConnectedPoints()
+ * -# We calculate the additional volume
+ * -# We go over the points until none yields a concave spot anymore.
+ * 
+ * Note: This routine - for free - calculates the difference in volume between convex and
+ * non-convex envelope, as the former is easy to calculate - VolumeOfConvexEnvelope() - it
+ * can be used to compute volumes of arbitrary shapes.
+ * \param *out output stream for debugging
+ * \param *TesselStruct non-convex envelope, is changed in return!
+ * \param *configuration contains IsAngstroem()
+ * \return volume difference between the non- and the created convex envelope
+ */
+double ConvexizeNonconvexEnvelope(ofstream *out, class Tesselation *TesselStruct)
+{
+  double volume = 0;
+  class BoundaryPointSet *point = NULL;
+  class BoundaryLineSet *line = NULL;
+  class BoundaryTriangleSet *triangle = NULL;
+  Vector OldPoint, TetraederVector[3];
+  *out << Verbose(0) << "Begin of ConvexizeNonconvexEnvelope" << endl;
+
+  if (TesselStruct == NULL) {
+    *out << Verbose(1) << "ERROR: TesselStruct is empty!" << endl;
+    return volume;
+  }
+
+  bool AllConvex = true;
+  bool Convexity = false;
+  do {
+    AllConvex = true;
+    for (PointMap::iterator PointRunner = TesselStruct->PointsOnBoundary.begin(); PointRunner != TesselStruct->PointsOnBoundary.end(); PointRunner++) {
+      point = PointRunner->second;
+      *out << Verbose(1) << "INFO: Current point is " << *point << "." << endl;
+      Convexity = true;
+      for (LineMap::iterator LineRunner = point->lines.begin(); LineRunner != point->lines.end(); LineRunner++) {
+        line = LineRunner->second;
+        *out << Verbose(2) << "INFO: Current line is " << *line << "." << endl;
+        if (line->CheckConvexityCriterion(out)) { 
+          // convex
+        } else { // concave
+          Convexity = false; // we have to go again through all ...
+          break;  // no need to check the others too
+        }
+      }
+      AllConvex = AllConvex && Convexity;
+      if (!Convexity) {
+        *out << Verbose(1) << "... point cannot be on convex envelope." << endl;
+        OldPoint.CopyVector(point->node->node);
+        // get list of connected points
+        BoundaryPointSet *Otherpoint = line->GetOtherEndpoint(point);
+        list<TesselPoint*> *CircleofPoints = TesselStruct->getCircleOfConnectedPoints(out, point->node, Otherpoint->node->node);
+        // remove all triangles
+        int *numbers = NULL;
+        int count = 0;
+        int i=0;
+        for (LineMap::iterator LineRunner = point->lines.begin(); LineRunner != point->lines.end(); LineRunner++)
+          count+=LineRunner->second->triangles.size();
+        numbers = new int[count];
+        for (LineMap::iterator LineRunner = point->lines.begin(); LineRunner != point->lines.end(); LineRunner++) {
+          line = LineRunner->second;
+          for (TriangleMap::iterator TriangleRunner = line->triangles.begin(); TriangleRunner != line->triangles.end(); TriangleRunner++) {
+            triangle = TriangleRunner->second;
+            *out << Verbose(2) << "Erasing triangle " << *triangle << "." << endl;
+            numbers[i] = triangle->Nr;
+            TesselStruct->TrianglesOnBoundary.erase(triangle->Nr);
+            delete(triangle);
+            i++;
+          }
+        }
+        *out << Verbose(1) << i << " triangles were removed." << endl;
+
+        // re-create all triangles by going through connected points list
+        list<TesselPoint*>::iterator OtherCircleRunner = CircleofPoints->end();
+        OtherCircleRunner--;
+        i=0;
+        for (list<TesselPoint*>::iterator CircleRunner = CircleofPoints->begin(); CircleRunner != CircleofPoints->end(); CircleRunner++) {
+          *out << Verbose(2) << "Adding new triangle points."<< endl;
+          TesselStruct->AddPoint(point->node, 0);
+          TesselStruct->AddPoint(*CircleRunner, 1);
+          TesselStruct->AddPoint(*OtherCircleRunner, 2);
+          *out << Verbose(2) << "Adding new triangle lines."<< endl;
+          TesselStruct->AddTriangleLine(TesselStruct->BPS[0], TesselStruct->BPS[1], 0); 
+          TesselStruct->AddTriangleLine(TesselStruct->BPS[0], TesselStruct->BPS[2], 1); 
+          TesselStruct->AddTriangleLine(TesselStruct->BPS[1], TesselStruct->BPS[2], 2); 
+          TesselStruct->BTS = new class BoundaryTriangleSet(TesselStruct->BLS, numbers[i]);
+          TesselStruct->TrianglesOnBoundary.insert(TrianglePair(numbers[i], triangle));
+          *out << Verbose(2) << "Created triangle " << *TesselStruct->BTS << "." << endl;
+          // calculate volume summand as a general tetraeder
+          for (int j=0;j<3;j++) {
+            TetraederVector[j].CopyVector(TesselStruct->BPS[j]->node->node);
+            TetraederVector[j].SubtractVector(&OldPoint);
+          }
+          OldPoint.CopyVector(&TetraederVector[0]);
+          OldPoint.VectorProduct(&TetraederVector[1]);
+          volume += 1./6. * fabs(OldPoint.ScalarProduct(&TetraederVector[2]));
+          // advance other shank
+          OtherCircleRunner++;
+          if (OtherCircleRunner == CircleofPoints->end())
+            OtherCircleRunner = CircleofPoints->begin();
+          // advance number
+          i++;
+          if (i > count)
+            *out << Verbose(2) << "WARNING: Maximum of numbers reached!" << endl;
+        }
+        *out << Verbose(1) << i << " triangles were created." << endl;
+        
+        delete[](numbers);
+      }
+    }
+  } while (!AllConvex);
+  *out << Verbose(0) << "End of ConvexizeNonconvexEnvelope" << endl;
+
+  // end
+  return volume;
+};
 
 /** Determines the volume of a cluster.