source: src/tesselation.hpp@ 065e82

/*
 * 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;

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

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


#include "helpers.hpp"
#include "linkedcell.hpp"
#include "tesselationhelpers.hpp"
#include "vector.hpp"

class BoundaryPointSet;
class BoundaryLineSet;
class BoundaryTriangleSet;
class TesselPoint;
class PointCloud;
class Tesselation;

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

#define PointMap map < int, class BoundaryPointSet * >
#define PointPair pair < int, class BoundaryPointSet * >
#define PointTestPair pair < PointMap::iterator, bool >
#define CandidateList list <class CandidateForTesselation *>

#define LineMap multimap < int, class BoundaryLineSet * >
#define LinePair pair < int, class BoundaryLineSet * >
#define LineTestPair pair < LineMap::iterator, bool >

#define TriangleMap map < int, class BoundaryTriangleSet * >
#define TrianglePair pair < int, class BoundaryTriangleSet * >
#define TriangleTestPair pair < TrianglePair::iterator, bool >

#define DistanceMultiMap multimap <double, pair < PointMap::iterator, PointMap::iterator> >
#define DistanceMultiMapPair pair <double, pair < PointMap::iterator, PointMap::iterator> >



template <typename T> void SetEndpointsOrdered(T endpoints[2], T endpoint1, T endpoint2)
{
  if (endpoint1->Nr < endpoint2->Nr) {
    endpoints[0] = endpoint1;
    endpoints[1] = endpoint2;
  } else {
    endpoints[0] = endpoint2;
    endpoints[1] = endpoint1;
  }
};

// ======================================================== class BoundaryPointSet =========================================

class BoundaryPointSet {
  public:
    BoundaryPointSet();
    BoundaryPointSet(TesselPoint *Walker);
    ~BoundaryPointSet();

    void AddLine(class BoundaryLineSet *line);

    LineMap lines;
    int LinesCount;
    TesselPoint *node;
    double value;
    int Nr;
};

ostream & operator << (ostream &ost, BoundaryPointSet &a);

// ======================================================== class BoundaryLineSet ==========================================

class BoundaryLineSet {
  public:
    BoundaryLineSet();
    BoundaryLineSet(class BoundaryPointSet *Point[2], int number);
    ~BoundaryLineSet();

    void AddTriangle(class BoundaryTriangleSet *triangle);
    bool IsConnectedTo(class BoundaryLineSet *line);
    bool ContainsBoundaryPoint(class BoundaryPointSet *point);
    bool CheckConvexityCriterion(ofstream *out);
    class BoundaryPointSet *GetOtherEndpoint(class BoundaryPointSet *);

    class BoundaryPointSet *endpoints[2];
    TriangleMap triangles;
    int Nr;
};

ostream & operator << (ostream &ost, BoundaryLineSet &a);

// ======================================================== class BoundaryTriangleSet =======================================

class BoundaryTriangleSet {
  public:
    BoundaryTriangleSet();
    BoundaryTriangleSet(class BoundaryLineSet *line[3], int number);
    ~BoundaryTriangleSet();

    void GetNormalVector(Vector &NormalVector);
    bool GetIntersectionInsideTriangle(ofstream *out, Vector *MolCenter, Vector *x, Vector *Intersection);
    bool ContainsBoundaryLine(class BoundaryLineSet *line);
    bool ContainsBoundaryPoint(class BoundaryPointSet *point);
    class BoundaryPointSet *GetThirdEndpoint(class BoundaryLineSet *line);
    bool IsPresentTupel(class BoundaryPointSet *Points[3]);
    void GetCenter(Vector *center);

    class BoundaryPointSet *endpoints[3];
    class BoundaryLineSet *lines[3];
    Vector NormalVector;
    int Nr;
};

ostream & operator << (ostream &ost, BoundaryTriangleSet &a);

// =========================================================== class TESSELPOINT ===========================================

/** Is a single point of the set of Vectors, also a super-class to be inherited and and its functions to be implemented.
 */
class TesselPoint {
public:
  TesselPoint();
  virtual ~TesselPoint();

  Vector *node;   // pointer to position of the dot in space
  int nr;       // index to easierly identify
  char *Name;   // some name to reference to on output

  virtual ostream & operator << (ostream &ost);
};

ostream & operator << (ostream &ost, const TesselPoint &a);

// =========================================================== class POINTCLOUD ============================================

/** Super-class for all point clouds structures, also molecules. They have to inherit this structure and implement the virtual function to access the Vectors.
 * This basically encapsulates a list structure.
 */
class PointCloud {
public:
  PointCloud();
  virtual ~PointCloud();

  virtual Vector *GetCenter(ofstream *out) { return NULL; };
  virtual TesselPoint *GetPoint() { return NULL; };
  virtual TesselPoint *GetTerminalPoint() { return NULL; };
  virtual void GoToNext() {};
  virtual void GoToPrevious() {};
  virtual void GoToFirst() {};
  virtual void GoToLast() {};
  virtual bool IsEmpty() { return false; };
  virtual bool IsEnd() { return false; };
};

// ======================================================== class CandidateForTesselation =========================================

class CandidateForTesselation {
  public :
  CandidateForTesselation(TesselPoint* candidate, BoundaryLineSet* currentBaseLine, Vector OptCandidateCenter, Vector OtherOptCandidateCenter);
  ~CandidateForTesselation();

  TesselPoint *point;
  BoundaryLineSet *BaseLine;
  Vector OptCenter;
  Vector OtherOptCenter;
};

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

/** Contains the envelope to a PointCloud.
 */
class Tesselation : public PointCloud {
  public:

    Tesselation();
    virtual ~Tesselation();

    void AddTesselationPoint(TesselPoint* Candidate, int n);
    void AddTesselationLine(class BoundaryPointSet *a, class BoundaryPointSet *b, int n);
    void AlwaysAddTesselationTriangleLine(class BoundaryPointSet *a, class BoundaryPointSet *b, int n);
    void AddTesselationTriangle();
    void RemoveTesselationTriangle(class BoundaryTriangleSet *triangle);
    void RemoveTesselationLine(class BoundaryLineSet *line);
    void RemoveTesselationPoint(class BoundaryPointSet *point);

    bool IsInside(Vector *pointer);
    class BoundaryPointSet *GetCommonEndpoint(class BoundaryLineSet * line1, class BoundaryLineSet * line2);

    // concave envelope
    void FindStartingTriangle(ofstream *out, const double RADIUS, class LinkedCell *LC);
    void FindSecondPointForTesselation(class TesselPoint* a, class TesselPoint* Candidate, Vector Oben, class TesselPoint*& OptCandidate, double Storage[3], double RADIUS, class LinkedCell *LC);
    void FindThirdPointForTesselation(Vector NormalVector, Vector SearchDirection, Vector OldSphereCenter, class BoundaryLineSet *BaseLine, class TesselPoint *ThirdNode, CandidateList* &candidates, double *ShortestAngle, const double RADIUS, class LinkedCell *LC);
    bool FindNextSuitableTriangle(ofstream *out, BoundaryLineSet &Line, BoundaryTriangleSet &T, const double& RADIUS, int N, LinkedCell *LC);
    int CheckPresenceOfTriangle(ofstream *out, class TesselPoint *Candidates[3]);
    class BoundaryTriangleSet * GetPresentTriangle(ofstream *out, TesselPoint *Candidates[3]);

    // convex envelope
    void TesselateOnBoundary(ofstream *out, PointCloud *cloud);
    void GuessStartingTriangle(ofstream *out);
    bool InsertStraddlingPoints(ofstream *out, PointCloud *cloud, LinkedCell *LC);
    double RemovePointFromTesselatedSurface(ofstream *out, class BoundaryPointSet *point);
    bool FlipBaseline(ofstream *out, class BoundaryLineSet *Base);
    bool PickFarthestofTwoBaselines(ofstream *out, class BoundaryLineSet *Base);
    class BoundaryPointSet *IsConvexRectangle(ofstream *out, class BoundaryLineSet *Base);
    map<int, int> FindAllDegeneratedTriangles();
    void RemoveDegeneratedTriangles();

    set<TesselPoint*> * GetAllConnectedPoints(ofstream *out, TesselPoint* Point);
    set<BoundaryTriangleSet*> *GetAllTriangles(ofstream *out, class BoundaryPointSet *Point);
    list<list<TesselPoint*> *> * GetPathsOfConnectedPoints(ofstream *out, TesselPoint* Point);
    list<list<TesselPoint*> *> * GetClosedPathsOfConnectedPoints(ofstream *out, TesselPoint* Point);
    list<TesselPoint*> * GetCircleOfConnectedPoints(ofstream *out, TesselPoint* Point, Vector *Reference = NULL);
    list<BoundaryTriangleSet*> *FindTriangles(TesselPoint* Points[3]);
    list<BoundaryTriangleSet*> * FindClosestTrianglesToPoint(ofstream *out, Vector *x, LinkedCell* LC);
    class BoundaryTriangleSet * FindClosestTriangleToPoint(ofstream *out, Vector *x, LinkedCell* LC);
    bool IsInnerPoint(ofstream *out, Vector Point, LinkedCell* LC);
    bool IsInnerPoint(ofstream *out, TesselPoint *Point, LinkedCell* LC);
    bool AddBoundaryPoint(TesselPoint *Walker, int n);

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


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

    // PointCloud implementation for PointsOnBoundary
    virtual Vector *GetCenter(ofstream *out);
    virtual TesselPoint *GetPoint();
    virtual TesselPoint *GetTerminalPoint();
    virtual void GoToNext();
    virtual void GoToPrevious();
    virtual void GoToFirst();
    virtual void GoToLast();
    virtual bool IsEmpty();
    virtual bool IsEnd();

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

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

    PointMap::iterator InternalPointer;
};

bool CheckLineCriteriaForDegeneratedTriangle(class BoundaryPointSet *nodes[3]);
bool SortCandidates(class CandidateForTesselation* candidate1, class CandidateForTesselation* candidate2);
TesselPoint* FindClosestPoint(const Vector* Point, TesselPoint *&SecondPoint, LinkedCell* LC);
TesselPoint* FindSecondClosestPoint(const Vector*, LinkedCell*);
double GetAngle(const Vector &point, const Vector &reference, const Vector OrthogonalVector);
Vector * GetClosestPointBetweenLine(ofstream *out, class BoundaryLineSet *Base, class BoundaryLineSet *OtherBase);

#endif /* TESSELATION_HPP_ */