Changeset b32dbb

Timestamp:

May 29, 2010, 12:59:31 PM (15 years ago)

Author:

Frederik Heber <heber@…>

Branches:

Action_Thermostats, Add_AtomRandomPerturbation, Add_FitFragmentPartialChargesAction, Add_RotateAroundBondAction, Add_SelectAtomByNameAction, Added_ParseSaveFragmentResults, AddingActions_SaveParseParticleParameters, Adding_Graph_to_ChangeBondActions, Adding_MD_integration_tests, Adding_ParticleName_to_Atom, Adding_StructOpt_integration_tests, AtomFragments, Automaking_mpqc_open, AutomationFragmentation_failures, Candidate_v1.5.4, Candidate_v1.6.0, Candidate_v1.6.1, ChangeBugEmailaddress, ChangingTestPorts, ChemicalSpaceEvaluator, CombiningParticlePotentialParsing, Combining_Subpackages, Debian_Package_split, Debian_package_split_molecuildergui_only, Disabling_MemDebug, Docu_Python_wait, EmpiricalPotential_contain_HomologyGraph, EmpiricalPotential_contain_HomologyGraph_documentation, Enable_parallel_make_install, Enhance_userguide, Enhanced_StructuralOptimization, Enhanced_StructuralOptimization_continued, Example_ManyWaysToTranslateAtom, Exclude_Hydrogens_annealWithBondGraph, FitPartialCharges_GlobalError, Fix_BoundInBox_CenterInBox_MoleculeActions, Fix_ChargeSampling_PBC, Fix_ChronosMutex, Fix_FitPartialCharges, Fix_FitPotential_needs_atomicnumbers, Fix_ForceAnnealing, Fix_IndependentFragmentGrids, Fix_ParseParticles, Fix_ParseParticles_split_forward_backward_Actions, Fix_PopActions, Fix_QtFragmentList_sorted_selection, Fix_Restrictedkeyset_FragmentMolecule, Fix_StatusMsg, Fix_StepWorldTime_single_argument, Fix_Verbose_Codepatterns, Fix_fitting_potentials, Fixes, ForceAnnealing_goodresults, ForceAnnealing_oldresults, ForceAnnealing_tocheck, ForceAnnealing_with_BondGraph, ForceAnnealing_with_BondGraph_continued, ForceAnnealing_with_BondGraph_continued_betteresults, ForceAnnealing_with_BondGraph_contraction-expansion, FragmentAction_writes_AtomFragments, FragmentMolecule_checks_bonddegrees, GeometryObjects, Gui_Fixes, Gui_displays_atomic_force_velocity, ImplicitCharges, IndependentFragmentGrids, IndependentFragmentGrids_IndividualZeroInstances, IndependentFragmentGrids_IntegrationTest, IndependentFragmentGrids_Sole_NN_Calculation, JobMarket_RobustOnKillsSegFaults, JobMarket_StableWorkerPool, JobMarket_unresolvable_hostname_fix, MoreRobust_FragmentAutomation, ODR_violation_mpqc_open, PartialCharges_OrthogonalSummation, PdbParser_setsAtomName, PythonUI_with_named_parameters, QtGui_reactivate_TimeChanged_changes, Recreated_GuiChecks, Rewrite_FitPartialCharges, RotateToPrincipalAxisSystem_UndoRedo, SaturateAtoms_findBestMatching, SaturateAtoms_singleDegree, StoppableMakroAction, Subpackage_CodePatterns, Subpackage_JobMarket, Subpackage_LinearAlgebra, Subpackage_levmar, Subpackage_mpqc_open, Subpackage_vmg, Switchable_LogView, ThirdParty_MPQC_rebuilt_buildsystem, TrajectoryDependenant_MaxOrder, TremoloParser_IncreasedPrecision, TremoloParser_MultipleTimesteps, TremoloParser_setsAtomName, Ubuntu_1604_changes, stable

Children:

a7c344

Parents:

bfd839

git-author:

Frederik Heber <heber@…> (05/27/10 11:04:42)

git-committer:

Frederik Heber <heber@…> (05/29/10 12:59:31)

Message:

Fixes and changes to tesselation and concavity measurements.

Here, we implement two attempts for a concavity measure:

1. Measure concavity per point by looking at neighbouring triangles
   • BoundaryLineSet::CheckConvexityCriterion() split up (calculation of angle outsourced to CalculateConvexity())
   • CHANGE: CalculateConcavityPerBoundaryPoint() uses new concavity measure per BoundaryPointSet containing:
     • concavity per line uses angle instead of +/-1 for line, averaged by number of lines
     • also concavity over all attached triangles uses area of triangle and only in case of concavity, averaged by total area
   • new functions
     • BoundaryLineSet::CalculateConvexity() - calculates the angle between two triangles.
     • BoundaryLineSet::GetOtherTriangle() - for a closed line returns the other triangle for a given one
     • BoundaryTriangleSet::GetThirdLine() - for a given boundary point returns the line of the three which does not contain it (opposite line to a point)
     • CalculateAreaofGeneralTriangle() - calculates area of arbitrary triangle

2. Measure concavity by the distance to a more convex envelope (i.e. created with bigger sphere radius)
   • ParseCommandLineOptions(): case 'N' - two envelopes are created and the distance used as concavity measure via CalculateConstrictionPerBoundaryPoint()
   • FIX: CandidateForTesselation::CheckValidity() - checked against OptCenter instead of (*VRunner), animate_sphere line is printed as error, hence always visible
   • FIX: Tesselation::FindThirdPointForTesselation() - error if circumcenter is not the equidistant from each triangle node is now an error mesage
   • BUGFIX: Tesselation::RemoveDegeneratedTriangles() - would fail for more than two degenerate triangles to remove due to faulty loop construction and break instead of continue
   • BUGFIX: GetCenterofCircumcircle() - is numerically unstable (>1e-10) for big sphere radii, there are two other variants, not using angles.
   • FindNonConvexBorder() - RemoveDegeneratedTriangles() commented-out as runs into infinite loop for small radii (<5) for L-shaped cluster

Other unrelated stuff:

• DOCUFIX: CalculateVolumeofGeneralTetraeder() - four times "first vector"
• FIX: Tesselation::FindAllDegeneratedTriangles() - iterator integrated into for-loop statement

Signed-off-by: Frederik Heber <heber@…>

Location:

src

Files:

• boundary.cpp (modified) (1 diff)
• builder.cpp (modified) (2 diffs)
• tesselation.cpp (modified) (10 diffs)
• tesselation.hpp (modified) (2 diffs)
• tesselationhelpers.cpp (modified) (6 diffs)
• tesselationhelpers.hpp (modified) (3 diffs)

src/boundary.cpp

@@ -1041 +1041 @@
 //  // Purges surplus triangles.
 //  TesselStruct->RemoveDegeneratedTriangles();
-
-  // check envelope for consistency
-  status = CheckListOfBaselines(TesselStruct);
+//
+//  // check envelope for consistency
+//  status = CheckListOfBaselines(TesselStruct);
 
   // store before correction

src/builder.cpp

@@ -2103 +2103 @@
               } else {
                 class Tesselation *T = NULL;
+                class Tesselation *Convex = NULL;
                 const LinkedCell *LCList = NULL;
+                const LinkedCell *LCListConvex = NULL;
                 molecule * Boundary = NULL;
                 //string filename(argv[argptr+1]);
@@ -2123 +2125 @@
                 if (!FindNonConvexBorder(Boundary, T, LCList, atof(argv[argptr]), argv[argptr+1]))
                   ExitFlag = 255;
+                const double ConvexRadius = 20.;
+                LCListConvex = new LinkedCell(Boundary, 2.*ConvexRadius);
+//                setVerbosity(3);
+                if (!FindNonConvexBorder(Boundary, Convex, LCListConvex, ConvexRadius, "ConvexEnvelope"))
+                  ExitFlag = 255;
+                CalculateConstrictionPerBoundaryPoint(T, Convex);
+                StoreTrianglesinFile(mol, (const Tesselation *&)T, argv[argptr+1], "");
                 //FindDistributionOfEllipsoids(T, &LCList, N, number, filename.c_str());
                 end = clock();

src/tesselation.cpp

@@ -229 +229 @@
 {
   Info FunctionInfo(__func__);
+  double angle = CalculateConvexity();
+  if (angle > -MYEPSILON) {
+    DoLog(0) && (Log() << Verbose(0) << "ACCEPT: Angle is greater than pi: convex." << endl);
+    return true;
+  } else {
+    DoLog(0) && (Log() << Verbose(0) << "REJECT: Angle is less than pi: concave." << endl);
+    return false;
+  }
+}
+
+
+/** Calculates the angle between two triangles with respect to their normal vector.
+ * We sum the two angles of each height vector with respect to the center of the baseline.
+ * \return angle > 0 then convex, if < 0 then concave
+ */
+double BoundaryLineSet::CalculateConvexity() const
+{
+  Info FunctionInfo(__func__);
   Vector BaseLineCenter, BaseLineNormal, BaseLine, helper[2], NormalCheck;
   // get the two triangles
@@ -277 +295 @@
   BaseLineNormal.Scale(-1.);
   double angle = GetAngle(helper[0], helper[1], BaseLineNormal);
-  if ((angle - M_PI) > -MYEPSILON) {
-    DoLog(0) && (Log() << Verbose(0) << "ACCEPT: Angle is greater than pi: convex." << endl);
-    return true;
-  } else {
-    DoLog(0) && (Log() << Verbose(0) << "REJECT: Angle is less than pi: concave." << endl);
-    return false;
-  }
+  return (angle - M_PI);
 }
 
@@ -302 +314 @@
 /** Returns other endpoint of the line.
  * \param *point other endpoint
- * \return NULL - if endpoint not contained in BoundaryLineSet, or pointer to BoundaryPointSet otherwise
+ * \return NULL - if endpoint not contained in BoundaryLineSet::lines, or pointer to BoundaryPointSet otherwise
  */
 class BoundaryPointSet *BoundaryLineSet::GetOtherEndpoint(const BoundaryPointSet * const point) const
@@ -313 +325 @@
   else
     return NULL;
+}
+;
+
+/** Returns other triangle of the line.
+ * \param *point other endpoint
+ * \return NULL - if triangle not contained in BoundaryLineSet::triangles, or pointer to BoundaryTriangleSet otherwise
+ */
+class BoundaryTriangleSet *BoundaryLineSet::GetOtherTriangle(const BoundaryTriangleSet * const triangle) const
+{
+  Info FunctionInfo(__func__);
+  if (triangles.size() == 2) {
+    for (TriangleMap::const_iterator TriangleRunner = triangles.begin(); TriangleRunner != triangles.end(); ++TriangleRunner)
+      if (TriangleRunner->second != triangle)
+        return TriangleRunner->second;
+  }
+  return NULL;
 }
 ;
@@ -669 +697 @@
 ;
 
+/** Returns the baseline which does not contain the given boundary point \a *point.
+ * \param *point endpoint which is neither endpoint of the desired line
+ * \return pointer to desired third baseline
+ */
+class BoundaryLineSet *BoundaryTriangleSet::GetThirdLine(const BoundaryPointSet * const point) const
+{
+  Info FunctionInfo(__func__);
+  // sanity check
+  if (!ContainsBoundaryPoint(point))
+    return NULL;
+  for (int i = 0; i < 3; i++)
+    if (!lines[i]->ContainsBoundaryPoint(point))
+      return lines[i];
+  // actually, that' impossible :)
+  return NULL;
+}
+;
+
 /** Calculates the center point of the triangle.
  * Is third of the sum of all endpoints.
@@ -1106 +1152 @@
     TesselPointList *ListofPoints = LC->GetPointsInsideSphere(RADIUS, (*VRunner));
 
-    DoLog(1) && (Log() << Verbose(1) << "The following atoms are inside sphere at " << OtherOptCenter << ":" << endl);
+    DoLog(1) && (Log() << Verbose(1) << "The following atoms are inside sphere at " << (*VRunner) << ":" << endl);
     for (TesselPointList::const_iterator Runner = ListofPoints->begin(); Runner != ListofPoints->end(); ++Runner)
-      DoLog(1) && (Log() << Verbose(1) << "  " << *(*Runner) << " with distance " << (*Runner)->node->distance(OtherOptCenter) << "." << endl);
+      DoLog(1) && (Log() << Verbose(1) << "  " << *(*Runner) << " with distance " << (*Runner)->node->distance(*(*VRunner)) << "." << endl);
 
     // remove baseline's endpoints and candidates
@@ -1124 +1170 @@
       DoeLog(1) && (eLog() << Verbose(1) << "External atoms inside of sphere at " << *(*VRunner) << ":" << endl);
       for (TesselPointList::const_iterator Runner = ListofPoints->begin(); Runner != ListofPoints->end(); ++Runner)
-        DoeLog(1) && (eLog() << Verbose(1) << "  " << *(*Runner) << endl);
+        DoeLog(1) && (eLog() << Verbose(1) << "  " << *(*Runner) << " at distance " << setprecision(13) << (*Runner)->node->distance(*(*VRunner)) << setprecision(6) << "." << endl);
+
+      // check with animate_sphere.tcl VMD script
+      if (ThirdPoint != NULL) {
+        DoeLog(1) && (eLog() << Verbose(1) << "Check by: animate_sphere 0 " << BaseLine->endpoints[0]->Nr + 1 << " " << BaseLine->endpoints[1]->Nr + 1 << " " << ThirdPoint->Nr + 1 << " " << RADIUS << " " << OldCenter[0] << " " << OldCenter[1] << " " << OldCenter[2] << " " << (*VRunner)->at(0) << " " << (*VRunner)->at(1) << " " << (*VRunner)->at(2) << endl);
+      } else {
+        DoeLog(1) && (eLog() << Verbose(1) << "Check by: ... missing third point ..." << endl);
+        DoeLog(1) && (eLog() << Verbose(1) << "Check by: animate_sphere 0 " << BaseLine->endpoints[0]->Nr + 1 << " " << BaseLine->endpoints[1]->Nr + 1 << " ??? " << RADIUS << " " << OldCenter[0] << " " << OldCenter[1] << " " << OldCenter[2] << " " << (*VRunner)->at(0) << " " << (*VRunner)->at(1) << " " << (*VRunner)->at(2) << endl);
+      }
     }
     delete (ListofPoints);
 
-    // check with animate_sphere.tcl VMD script
-    if (ThirdPoint != NULL) {
-      DoLog(1) && (Log() << Verbose(1) << "Check by: animate_sphere 0 " << BaseLine->endpoints[0]->Nr + 1 << " " << BaseLine->endpoints[1]->Nr + 1 << " " << ThirdPoint->Nr + 1 << " " << RADIUS << " " << OldCenter[0] << " " << OldCenter[1] << " " << OldCenter[2] << " " << (*VRunner)->at(0) << " " << (*VRunner)->at(1) << " " << (*VRunner)->at(2) << endl);
-    } else {
-      DoLog(1) && (Log() << Verbose(1) << "Check by: ... missing third point ..." << endl);
-      DoLog(1) && (Log() << Verbose(1) << "Check by: animate_sphere 0 " << BaseLine->endpoints[0]->Nr + 1 << " " << BaseLine->endpoints[1]->Nr + 1 << " ??? " << RADIUS << " " << OldCenter[0] << " " << OldCenter[1] << " " << OldCenter[2] << " " << (*VRunner)->at(0) << " " << (*VRunner)->at(1) << " " << (*VRunner)->at(2) << endl);
-    }
   }
   return flag;
@@ -3313 +3360 @@
                         }
                       } else {
-                        DoLog(1) && (Log() << Verbose(1) << "REJECT: Distance to center of circumcircle is not the same from each corner of the triangle: " << fabs(radius - otherradius) << endl);
+                        DoeLog(0) && (eLog() << Verbose(1) << "REJECT: Distance to center of circumcircle is not the same from each corner of the triangle: " << fabs(radius - otherradius) << endl);
                       }
                     } else {
@@ -4613 +4660 @@
 
   DoLog(0) && (Log() << Verbose(0) << "FindAllDegeneratedTriangles() found " << DegeneratedTriangles->size() << " triangles:" << endl);
-  IndexToIndex::iterator it;
-  for (it = DegeneratedTriangles->begin(); it != DegeneratedTriangles->end(); it++)
+  for (IndexToIndex::iterator it = DegeneratedTriangles->begin(); it != DegeneratedTriangles->end(); it++)
     DoLog(0) && (Log() << Verbose(0) << (*it).first << " => " << (*it).second << endl);
 
@@ -4632 +4678 @@
   int count = 0;
 
-  for (IndexToIndex::iterator TriangleKeyRunner = DegeneratedTriangles->begin(); TriangleKeyRunner != DegeneratedTriangles->end(); ++TriangleKeyRunner) {
+  // iterate over all degenerated triangles
+  for (IndexToIndex::iterator TriangleKeyRunner = DegeneratedTriangles->begin(); !DegeneratedTriangles->empty(); TriangleKeyRunner = DegeneratedTriangles->begin()) {
+    DoLog(0) && (Log() << Verbose(0) << "Checking presence of triangles " << TriangleKeyRunner->first << " and " << TriangleKeyRunner->second << "." << endl);
+    // both ways are stored in the map, only use one
+    if (TriangleKeyRunner->first > TriangleKeyRunner->second)
+      continue;
+
+    // determine from the keys in the map the two _present_ triangles
     finder = TrianglesOnBoundary.find(TriangleKeyRunner->first);
     if (finder != TrianglesOnBoundary.end())
       triangle = finder->second;
     else
-      break;
+      continue;
     finder = TrianglesOnBoundary.find(TriangleKeyRunner->second);
     if (finder != TrianglesOnBoundary.end())
       partnerTriangle = finder->second;
     else
-      break;
-
+      continue;
+
+    // determine which lines are shared by the two triangles
     bool trianglesShareLine = false;
     for (int i = 0; i < 3; ++i)

src/tesselation.hpp

@@ -138 +138 @@
     bool ContainsBoundaryPoint(const BoundaryPointSet * const point) const;
     bool CheckConvexityCriterion() const;
+    double CalculateConvexity() const;
     class BoundaryPointSet *GetOtherEndpoint(const BoundaryPointSet * const point) const;
+    class BoundaryTriangleSet *GetOtherTriangle(const BoundaryTriangleSet * const triangle) const;
 
     class BoundaryPointSet *endpoints[2];
@@ -164 +166 @@
     bool ContainsBoundaryPoint(const TesselPoint * const point) const;
     class BoundaryPointSet *GetThirdEndpoint(const BoundaryLineSet * const line) const;
+    class BoundaryLineSet *GetThirdLine(const BoundaryPointSet * const point) const;
     bool IsPresentTupel(const BoundaryPointSet * const Points[3]) const;
     bool IsPresentTupel(const BoundaryTriangleSet * const T) const;

src/tesselationhelpers.cpp

@@ -10 +10 @@
 #include "info.hpp"
 #include "linkedcell.hpp"
+#include "linearsystemofequations.hpp"
 #include "log.hpp"
 #include "tesselation.hpp"
@@ -182 +183 @@
   beta = M_PI - SideC.Angle(SideA);
   gamma = M_PI - SideA.Angle(SideB);
-  //Log() << Verbose(1) << "INFO: alpha = " << alpha/M_PI*180. << ", beta = " << beta/M_PI*180. << ", gamma = " << gamma/M_PI*180. << "." << endl;
+  Log() << Verbose(1) << "INFO: alpha = " << alpha/M_PI*180. << ", beta = " << beta/M_PI*180. << ", gamma = " << gamma/M_PI*180. << "." << endl;
   if (fabs(M_PI - alpha - beta - gamma) > HULLEPSILON) {
     DoeLog(2) && (eLog()<< Verbose(2) << "GetCenterofCircumcircle: Sum of angles " << (alpha+beta+gamma)/M_PI*180. << " > 180 degrees by " << fabs(M_PI - alpha - beta - gamma)/M_PI*180. << "!" << endl);
@@ -195 +196 @@
   (*Center) += helper;
   Center->Scale(1./(sin(2.*alpha) + sin(2.*beta) + sin(2.*gamma)));
+  Log() << Verbose(1) << "INFO: Center (1st algo) is at " << *Center << "." << endl;
+
+//  LinearSystemOfEquations LSofEq(NDIM,NDIM);
+//  double *matrix = new double[NDIM*NDIM];
+//  matrix[0] = 0.;
+//  matrix[1] = a.DistanceSquared(b);
+//  matrix[2] = a.DistanceSquared(c);
+//  matrix[3] = a.DistanceSquared(b);
+//  matrix[4] = 0.;
+//  matrix[5] = b.DistanceSquared(c);
+//  matrix[6] = a.DistanceSquared(c);
+//  matrix[7] = b.DistanceSquared(c);
+//  matrix[8] = 0.;
+//  cout << "Matrix is: ";
+//  for (int i=0;i<NDIM*NDIM;i++)
+//    cout << matrix[i] << "\t";
+//  cout << endl;
+//  LSofEq.SetA(matrix);
+//  delete[](matrix);
+//  LSofEq.Setb(new Vector(1.,1.,1.));
+//  LSofEq.SetSymmetric(true);
+//  helper.Zero();
+//  if (!LSofEq.GetSolutionAsVector(helper)) {
+//    DoLog(0) && (eLog()<< Verbose(0) << "Could not solve the linear system in GetCenterofCircumCircle()!" << endl);
+//  }
+//  cout << "Solution is " << helper << endl;
+  // is equivalent to the three lines below
+  helper[0] = SideA.NormSquared()*(SideB.NormSquared()+SideC.NormSquared() - SideA.NormSquared());
+  helper[1] = SideB.NormSquared()*(SideC.NormSquared()+SideA.NormSquared() - SideB.NormSquared());
+  helper[2] = SideC.NormSquared()*(SideA.NormSquared()+SideB.NormSquared() - SideC.NormSquared());
+
+  Center->Zero();
+  *Center += helper[0] * a;
+  *Center += helper[1] * b;
+  *Center += helper[2] * c;
+  Center->Scale(1./(helper[0]+helper[1]+helper[2]));
+  Log() << Verbose(1) << "INFO: Center (2nd algo) is at " << *Center << "." << endl;
 };
 
@@ -416 +454 @@
 /** Calculates the volume of a general tetraeder.
  * \param *a first vector
- * \param *a first vector
- * \param *a first vector
- * \param *a first vector
+ * \param *b second vector
+ * \param *c third vector
+ * \param *d fourth vector
  * \return \f$ \frac{1}{6} \cdot ((a-d) \times (a-c) \cdot  (a-b)) \f$
  */
@@ -436 +474 @@
   volume = 1./6. * fabs(Point.ScalarProduct(TetraederVector[2]));
   return volume;
+};
+
+/** Calculates the area of a general triangle.
+ * We use the Heron's formula of area, [Bronstein, S. 138]
+ * \param &A first vector
+ * \param &B second vector
+ * \param &C third vector
+ * \return \f$ \frac{1}{6} \cdot ((a-d) \times (a-c) \cdot  (a-b)) \f$
+ */
+double CalculateAreaofGeneralTriangle(const Vector &A, const Vector &B, const Vector &C)
+{
+  Info FunctionInfo(__func__);
+
+  const double sidea = B.distance(C);
+  const double sideb = A.distance(C);
+  const double sidec = A.distance(B);
+  const double s = (sidea+sideb+sidec)/2.;
+
+  const double area = sqrt(s*(s-sidea)*(s-sideb)*(s-sidec));
+  return area;
 };
 
@@ -870 +928 @@
   class BoundaryPointSet *point = NULL;
   class BoundaryLineSet *line = NULL;
-
-  // calculate remaining concavity
+  class BoundaryTriangleSet *triangle = NULL;
+  double ConcavityPerLine = 0.;
+  double ConcavityPerTriangle = 0.;
+  double area = 0.;
+  double totalarea = 0.;
+
   for (PointMap::const_iterator PointRunner = TesselStruct->PointsOnBoundary.begin(); PointRunner != TesselStruct->PointsOnBoundary.end(); PointRunner++) {
     point = PointRunner->second;
     DoLog(1) && (Log() << Verbose(1) << "INFO: Current point is " << *point << "." << endl);
-    point->value = 0;
+
+    // calculate mean concavity over all connected line
+    ConcavityPerLine = 0.;
     for (LineMap::iterator LineRunner = point->lines.begin(); LineRunner != point->lines.end(); LineRunner++) {
       line = LineRunner->second;
       //Log() << Verbose(1) << "INFO: Current line of point " << *point << " is " << *line << "." << endl;
-      if (!line->CheckConvexityCriterion())
-        point->value += 1;
-    }
-  }
-};
-
+      ConcavityPerLine -= line->CalculateConvexity();
+    }
+    ConcavityPerLine /= point->lines.size();
+
+    // weigh with total area of the surrounding triangles
+    totalarea  = 0.;
+    TriangleSet *triangles = TesselStruct->GetAllTriangles(PointRunner->second);
+    for (TriangleSet::iterator TriangleRunner = triangles->begin(); TriangleRunner != triangles->end(); ++TriangleRunner) {
+      totalarea += CalculateAreaofGeneralTriangle(*(*TriangleRunner)->endpoints[0]->node->node, *(*TriangleRunner)->endpoints[1]->node->node, *(*TriangleRunner)->endpoints[2]->node->node);
+    }
+    ConcavityPerLine *= totalarea;
+
+    // calculate mean concavity over all attached triangles
+    ConcavityPerTriangle = 0.;
+    for (TriangleSet::const_iterator TriangleRunner = triangles->begin(); TriangleRunner != triangles->end(); ++TriangleRunner) {
+      line = (*TriangleRunner)->GetThirdLine(PointRunner->second);
+      triangle = line->GetOtherTriangle(*TriangleRunner);
+      area = CalculateAreaofGeneralTriangle(*triangle->endpoints[0]->node->node, *triangle->endpoints[1]->node->node, *triangle->endpoints[2]->node->node);
+      area += CalculateAreaofGeneralTriangle(*(*TriangleRunner)->endpoints[0]->node->node, *(*TriangleRunner)->endpoints[1]->node->node, *(*TriangleRunner)->endpoints[2]->node->node);
+      area *= -line->CalculateConvexity();
+      if (area > 0)
+        ConcavityPerTriangle += area;
+//      else
+//        ConcavityPerTriangle -= area;
+    }
+    ConcavityPerTriangle /= triangles->size()/totalarea;
+    delete(triangles);
+
+    // add up
+    point->value = ConcavityPerLine + ConcavityPerTriangle;
+  }
+};
+
+
+
+/** Calculates the concavity for each of the BoundaryPointSet's in a Tesselation.
+ * Sets BoundaryPointSet::value equal to the nearest distance to convex envelope.
+ * \param *out output stream for debugging
+ * \param *TesselStruct pointer to Tesselation structure
+ * \param *Convex pointer to convex Tesselation structure as reference
+ */
+void CalculateConstrictionPerBoundaryPoint(const Tesselation * const TesselStruct, const Tesselation * const Convex)
+{
+  Info FunctionInfo(__func__);
+  double distance = 0.;
+
+  for (PointMap::const_iterator PointRunner = TesselStruct->PointsOnBoundary.begin(); PointRunner != TesselStruct->PointsOnBoundary.end(); PointRunner++) {
+    DoeLog(1) && (eLog() << Verbose(1) << "INFO: Current point is " << * PointRunner->second << "." << endl);
+
+    distance = 0.;
+    for (TriangleMap::const_iterator TriangleRunner = Convex->TrianglesOnBoundary.begin(); TriangleRunner != Convex->TrianglesOnBoundary.end(); TriangleRunner++) {
+      const double CurrentDistance = Convex->GetDistanceSquaredToTriangle(*PointRunner->second->node->node, TriangleRunner->second);
+      if (CurrentDistance < distance)
+        distance = CurrentDistance;
+    }
+
+    PointRunner->second->value = distance;
+  }
+};
 
 /** Checks whether each BoundaryLineSet in the Tesselation has two triangles.

src/tesselationhelpers.hpp

@@ -43 +43 @@
 /********************************************** definitions *********************************/
 
-#define HULLEPSILON 1e-10
+#define HULLEPSILON 1e-9 //!< TODO: Get rid of HULLEPSILON, points to numerical instabilities
 
 /********************************************** declarations *******************************/
@@ -55 +55 @@
 bool existsIntersection(const Vector &point1, const Vector &point2, const Vector &point3, const Vector &point4);
 double CalculateVolumeofGeneralTetraeder(const Vector &a, const Vector &b, const Vector &c, const Vector &d);
+double CalculateAreaofGeneralTriangle(const Vector &A, const Vector &B, const Vector &C);
 double GetAngle(const Vector &point, const Vector &reference, const Vector &OrthogonalVector);
 
@@ -68 +69 @@
 void WriteVrmlFile(ofstream * const vrmlfile, const Tesselation * const Tess, const PointCloud * const cloud);
 void CalculateConcavityPerBoundaryPoint(const Tesselation * const TesselStruct);
+void CalculateConstrictionPerBoundaryPoint(const Tesselation * const TesselStruct, const Tesselation * const Convex);
 double DistanceToTrianglePlane(const Vector *x, const BoundaryTriangleSet * const triangle);