source: src/Tesselation/tesselation.hpp@ 3400bb

/*
 * tesselation.hpp
 *
 *  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.
 *
 *  Created on: Aug 3, 2009
 *      Author: heber
 */

#ifndef TESSELATION_HPP_
#define TESSELATION_HPP_

using namespace std;

/*********************************************** includes ***********************************/

// include config.h
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <map>
#include <list>
#include <set>
#include <stack>

#include "Atom/atom_particleinfo.hpp"
#include "BoundaryMaps.hpp"
#include "BoundaryPointSet.hpp"
#include "LinearAlgebra/Vector.hpp"
#include "Atom/TesselPoint.hpp"


/****************************************** forward declarations *****************************/

class BoundaryPointSet;
class BoundaryLineSet;
class BoundaryTriangleSet;
class CandidateForTesselation;
class IPointCloud;
class LinkedCell_deprecated;
class Plane;
class Tesselation;

/********************************************** definitions *********************************/

enum { DoTecplotOutput=1 };
enum { DoRaster3DOutput=1 };
enum { DoVRMLOutput=0 };

extern "C" const char *TecplotSuffix;
extern "C" const char *Raster3DSuffix;
extern "C" const char *VRMLSUffix;

extern "C" const double ParallelEpsilon;

// ======================================================= some template functions =========================================

/********************************************** declarations *******************************/

// =========================================================== class TESSELATION ===========================================

/** Is iterable container of TesselPoints.
 */
class Tesselation {
  public:

    Tesselation();
    virtual ~Tesselation();

    void operator()(IPointCloud & cloud, const double SPHERERADIUS);
    double getVolumeOfConvexEnvelope(const bool IsAngstroem) const;
    double getAreaOfEnvelope(const bool IsAngstroem) const;

    void AddTesselationPoint(TesselPoint* Candidate, const int n);
    void SetTesselationPoint(TesselPoint* Candidate, const int n) const;
    bool AddTesselationLine(const Vector * OptCenter, const BoundaryPointSet * const candidate, class BoundaryPointSet *a, class BoundaryPointSet *b, const int n);
    void AddNewTesselationTriangleLine(class BoundaryPointSet *a, class BoundaryPointSet *b, const int n);
    void AddExistingTesselationTriangleLine(class BoundaryLineSet *FindLine, int n);
    void AddTesselationTriangle();
    void AddTesselationTriangle(const int nr);
    void AddCandidateTriangle(CandidateForTesselation &CandidateLine, enum centers type);
    void AddDegeneratedTriangle(CandidateForTesselation &CandidateLine, const double RADIUS, const LinkedCell_deprecated *LC);
    void AddCandidatePolygon(CandidateForTesselation CandidateLine, const double RADIUS, const LinkedCell_deprecated *LC);
    void RemoveTesselationTriangle(class BoundaryTriangleSet *triangle);
    void RemoveTesselationLine(class BoundaryLineSet *line);
    void RemoveTesselationPoint(class BoundaryPointSet *point);
    bool CheckDegeneracy(CandidateForTesselation &CandidateLine, const double RADIUS, const LinkedCell_deprecated *LC) const;
    bool isConvex() const;

    // concave envelope
    bool FindStartingTriangle(const double RADIUS, const LinkedCell_deprecated *LC);
    void FindSecondPointForTesselation(class TesselPoint* a, Vector Oben, class TesselPoint*& OptCandidate, double Storage[3], double RADIUS, const LinkedCell_deprecated *LC);
    void FindThirdPointForTesselation(const Vector &NormalVector, const Vector &SearchDirection, const Vector &OldSphereCenter, CandidateForTesselation &CandidateLine, const class BoundaryPointSet  * const ThirdNode, const double RADIUS, const LinkedCell_deprecated *LC) const;
    bool FindNextSuitableTriangle(CandidateForTesselation &CandidateLine, const BoundaryTriangleSet &T, const double& RADIUS, const LinkedCell_deprecated *LC);
    bool FindCandidatesforOpenLines(const double RADIUS, const LinkedCell_deprecated *&LCList);
    int CheckPresenceOfTriangle(class TesselPoint *Candidates[3]) const;
    class BoundaryTriangleSet * GetPresentTriangle(TesselPoint *Candidates[3]);

    // convex envelope
    void TesselateOnBoundary(IPointCloud & cloud);
    void GuessStartingTriangle();
    bool InsertStraddlingPoints(IPointCloud & cloud, const LinkedCell_deprecated *LC);
    double RemovePointSurroundedByPolygon(
        TesselPointList *connectedPath,
        BoundaryPointSet *point);
    bool CheckAllConcaveInPolygon(
        const TesselPointList *connectedPath,
        const BoundaryPointSet *point
        );
    double RemoveFullConcavePointFromTesselatedSurface(class BoundaryPointSet *point);
    double RemovePointFromTesselatedSurface(class BoundaryPointSet *point);
    class BoundaryLineSet * FlipBaseline(class BoundaryLineSet *Base);
    double PickFarthestofTwoBaselines(class BoundaryLineSet *Base);
    class BoundaryPointSet *IsConvexRectangle(class BoundaryLineSet *Base);
    IndexToIndex * FindAllDegeneratedTriangles();
    IndexToIndex * FindAllDegeneratedLines();
    void RemoveDegeneratedTriangles();
    void AddBoundaryPointByDegeneratedTriangle(class TesselPoint *point, LinkedCell_deprecated *LC);
    int CorrectAllDegeneratedPolygons();

    TesselPointSet * GetAllConnectedPoints(const TesselPoint* const Point) const;
    TriangleSet * GetAllTriangles(const BoundaryPointSet * const Point) const;
    ListOfTesselPointList * GetPathsOfConnectedPoints(const TesselPoint* const Point) const;
    ListOfTesselPointList * GetClosedPathsOfConnectedPoints(const TesselPoint* const Point) const;
    TesselPointList * GetCircleOfSetOfPoints(TesselPointSet *SetOfNeighbours, const TesselPoint* const Point, const Vector &Reference) const;
    TesselPointList * GetCircleOfConnectedTriangles(TesselPointSet *SetOfNeighbours, const TesselPoint* const Point, const Vector &Reference) const;
    class BoundaryPointSet * GetCommonEndpoint(const BoundaryLineSet * line1, const BoundaryLineSet * line2) const;
    TriangleList * FindTriangles(const TesselPoint* const Points[3]) const;
    TriangleList * FindClosestTrianglesToVector(const Vector &x, const LinkedCell_deprecated* LC) const;
    BoundaryTriangleSet * FindClosestTriangleToVector(const Vector &x, const LinkedCell_deprecated* LC) const;
    bool IsInnerPoint(const Vector &Point, const LinkedCell_deprecated* const LC) const;
    Vector getNormal(const Vector &Point, const LinkedCell_deprecated* const LC) const;
    double GetDistanceSquaredToTriangle(const Vector &Point, const BoundaryTriangleSet* const triangle) const;
    double GetDistanceToSurface(const Vector &Point, const LinkedCell_deprecated* const LC) const;
    BoundaryTriangleSet * GetClosestTriangleOnSurface(const Vector &Point, const LinkedCell_deprecated* const LC) const;
    bool AddBoundaryPoint(TesselPoint * Walker, const int n);
    DistanceToPointMap * FindClosestBoundaryPointsToVector(const Vector &x, const LinkedCell_deprecated* LC) const;
    BoundaryLineSet * FindClosestBoundaryLineToVector(const Vector &x, const LinkedCell_deprecated* LC) const;

    bool IsPointBelowSurroundingPolygon(const BoundaryPointSet *_point) const;

    // print for debugging
    void PrintAllBoundaryPoints(ofstream *out) const;
    void PrintAllBoundaryLines(ofstream *out) const;
    void PrintAllBoundaryTriangles(ofstream *out) const;

    // store envelope in file
    void Output(const char *filename, IPointCloud & cloud);

    PointMap PointsOnBoundary;
    LineMap LinesOnBoundary;
    CandidateMap OpenLines;
    TriangleMap TrianglesOnBoundary;
    int PointsOnBoundaryCount;
    int LinesOnBoundaryCount;
    int TrianglesOnBoundaryCount;

    typedef PointMap::iterator iterator;
    typedef PointMap::const_iterator const_iterator;
    iterator begin() { return PointsOnBoundary.begin(); }
    const_iterator begin() const { return PointsOnBoundary.begin(); }
    iterator end() { return PointsOnBoundary.end(); }
    const_iterator end() const { return PointsOnBoundary.end(); }

    class BoundaryPointSet *BPS[2];
    class BoundaryLineSet *BLS[3];
    class BoundaryTriangleSet *BTS;
    class BoundaryTriangleSet *LastTriangle;
    int TriangleFilesWritten;

  private:
    static const double HULLEPSILON; //!< TODO: Get rid of HULLEPSILON, points to numerical instabilities

    mutable class BoundaryPointSet *TPS[3]; //this is a Storage for pointers to triangle points, this and BPS[2] needed due to AddLine restrictions

    mutable PointMap::const_iterator InternalPointer;

    //bool HasOtherBaselineBetterCandidate(const BoundaryLineSet * const BaseRay, const TesselPoint * const OptCandidate, double ShortestAngle, double RADIUS, const LinkedCell_deprecated * const LC) const;
    void FindDegeneratedCandidatesforOpenLines(TesselPoint * const Sprinter, const Vector * const OptCenter);
};

#endif /* TESSELATION_HPP_ */