DivideAndConquer.h 4.86 KB
Newer Older
Tristan Carrier Baudouin's avatar
Tristan Carrier Baudouin committed
1
// Gmsh - Copyright (C) 1997-2010 C. Geuzaine, J.-F. Remacle
Christophe Geuzaine's avatar
Christophe Geuzaine committed
2 3
//
// See the LICENSE.txt file for license information. Please report all
Christophe Geuzaine's avatar
Christophe Geuzaine committed
4
// bugs and problems to the public mailing list <gmsh@onelab.info>.
Christophe Geuzaine's avatar
Christophe Geuzaine committed
5

6 7
#ifndef _DIVIDE_AND_CONQUER_H_
#define _DIVIDE_AND_CONQUER_H_
8

9 10 11 12
#include <vector>
#include <algorithm>
#include "fullMatrix.h"
#include "SPoint2.h"
13
#include "simpleFunction.h"
14
#include "Octree.h"
15
#include "MElement.h"
16

17
class GFace;
18 19 20 21 22 23
typedef struct _CDLIST DListRecord, *DListPeek;
typedef int PointNumero;

typedef struct{
  double v;
  double h;
24
}DPoint;
25

Christophe Geuzaine's avatar
Christophe Geuzaine committed
26
struct PointRecord {
27
  DPoint where;
28
  DListPeek adjacent;
29
  void *data;
30
  int flag; //0:to be kept, 1:to be removed
Tristan Carrier Baudouin's avatar
Tristan Carrier Baudouin committed
31
  int identificator;
Tristan Carrier Baudouin's avatar
Tristan Carrier Baudouin committed
32
  std::vector<void*> vicinity;
33 34 35 36
  PointRecord() : adjacent(0), data(0), flag(0), identificator(0)
  {
    where.v = where.h = 0.;
  }
37
};
38 39

struct _CDLIST{
40
  PointNumero point_num;
41 42 43 44 45
  DListPeek next, prev;
};

typedef struct{
  PointNumero *t;
46
  int t_length;
47
}STriangle;
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

typedef struct{
  PointNumero begin;
  PointNumero end;
}DT;

typedef struct{
  PointNumero from;
  PointNumero to;
}Segment;

typedef struct{
  PointNumero a, b, c;
}Triangle;

Christophe Geuzaine's avatar
Christophe Geuzaine committed
63
class DocRecord{
64
 private:
65 66
  int _hullSize;
  PointNumero *_hull;
67 68 69 70 71 72 73 74 75 76 77
  PointNumero Predecessor(PointNumero a, PointNumero b);
  PointNumero Successor(PointNumero a, PointNumero b);
  int FixFirst(PointNumero x, PointNumero f);
  PointNumero First(PointNumero x);
  int IsLeftOf(PointNumero x, PointNumero y, PointNumero check);
  int IsRightOf(PointNumero x, PointNumero y, PointNumero check);
  Segment LowerCommonTangent(DT vl, DT vr);
  Segment UpperCommonTangent(DT vl, DT vr);
  int Qtest(PointNumero h, PointNumero i, PointNumero j, PointNumero k);
  int Merge(DT vl, DT vr);
  DT RecurTrig(PointNumero left, PointNumero right);
78
  int DListInsert(PointNumero centerPoint, PointNumero newPoint);
79 80 81
  int Insert(PointNumero a, PointNumero b);
  int DListDelete(DListPeek *dlist, PointNumero oldPoint);
  int Delete(PointNumero a, PointNumero b);
82
  void ConvertDListToVoronoiData();
Tristan Carrier Baudouin's avatar
Tristan Carrier Baudouin committed
83
  int ConvertDListToTriangles();
84
  void RemoveAllDList();
85 86 87
  int BuildDelaunay();
  int CountPointsOnHull();
  void ConvexHull();
Christophe Geuzaine's avatar
Christophe Geuzaine committed
88
 public:
89
  STriangle *_adjacencies;
Christophe Geuzaine's avatar
Christophe Geuzaine committed
90
  int numPoints;        // number of points
Tristan Carrier Baudouin's avatar
Tristan Carrier Baudouin committed
91
  int size_points;
Christophe Geuzaine's avatar
Christophe Geuzaine committed
92 93 94 95
  PointRecord *points;  // points to triangulate
  int numTriangles;     // number of triangles
  Triangle *triangles;  // 2D results
  DocRecord(int n);
96 97 98
  double &x(int i){ return points[i].where.h; }
  double &y(int i){ return points[i].where.v; }
  void*  &data(int i){ return points[i].data; }
Tristan Carrier Baudouin's avatar
Tristan Carrier Baudouin committed
99
  void setPoints(fullMatrix<double> *p);
Christophe Geuzaine's avatar
Christophe Geuzaine committed
100 101
  ~DocRecord();
  void MakeMeshWithPoints();
102 103
  void Voronoi ();
  int hullSize() {return _hullSize;}
Christophe Geuzaine's avatar
Christophe Geuzaine committed
104
  int onHull(PointNumero i) { return std::binary_search(_hull, _hull+_hullSize, i); }
105
  void makePosView(std::string, GFace *gf=NULL);
106
  void printMedialAxis(Octree *_octree, std::string, GFace *gf=NULL, GEdge *ge=NULL);
107
  void voronoiCell(PointNumero pt, std::vector<SPoint2> &pts) const;
108

Tristan Carrier Baudouin's avatar
Tristan Carrier Baudouin committed
109 110
  std::set<std::pair<void*,void*> > boundaryEdges;

Christophe Geuzaine's avatar
Christophe Geuzaine committed
111 112 113 114 115
  void addBoundaryEdge(void* p1,void* p2)
  {
    void *a = (p1 < p2) ? p1 : p2;
    void *b = (p1 > p2) ? p1 : p2;
    boundaryEdges.insert(std::make_pair(a,b));
Tristan Carrier Baudouin's avatar
Tristan Carrier Baudouin committed
116
  }
Christophe Geuzaine's avatar
Christophe Geuzaine committed
117 118 119 120
  bool lookForBoundaryEdge(void* p1,void* p2)
  {
    void *a = (p1 < p2) ? p1 : p2;
    void *b = (p1 > p2) ? p1 : p2;
121
    std::set<std::pair<void*,void*> >::iterator it =
Christophe Geuzaine's avatar
Christophe Geuzaine committed
122 123
      boundaryEdges.find(std::make_pair(a,b));
    return it != boundaryEdges.end();
124 125
  }

Christophe Geuzaine's avatar
Christophe Geuzaine committed
126 127
  void recur_tag_triangles(int, std::set<int>&, std::map<std::pair<void*,void*>,
                           std::pair<int,int> >&);
Tristan Carrier Baudouin's avatar
Tristan Carrier Baudouin committed
128 129 130 131
  std::set<int> tagInterior(double,double);
  void concave(double,double,GFace*);
  bool contain(int,int,int);
  void add(int,int);
Christophe Geuzaine's avatar
Christophe Geuzaine committed
132

133 134 135
  void initialize();
  bool remove_point(int);
  void remove_all();
Tristan Carrier Baudouin's avatar
Tristan Carrier Baudouin committed
136
  void add_point(double,double,GFace*);
137

Tristan Carrier Baudouin's avatar
Tristan Carrier Baudouin committed
138
  std::set<std::pair<void*,void*> > mesh_edges;
139

Christophe Geuzaine's avatar
Christophe Geuzaine committed
140 141 142 143 144
  void add_edge(void* p1,void* p2)
  {
    void *a = (p1 < p2) ? p1 : p2;
    void *b = (p1 > p2) ? p1 : p2;
    mesh_edges.insert(std::make_pair(a,b));
Tristan Carrier Baudouin's avatar
Tristan Carrier Baudouin committed
145
  }
Christophe Geuzaine's avatar
Christophe Geuzaine committed
146 147 148 149
  bool find_edge(void* p1,void* p2)
  {
    void *a = (p1 < p2) ? p1 : p2;
    void *b = (p1 > p2) ? p1 : p2;
150
    std::set<std::pair<void*,void*> >::iterator it =
Christophe Geuzaine's avatar
Christophe Geuzaine committed
151 152
      mesh_edges.find(std::make_pair(a,b));
    return it != mesh_edges.end();
153 154
  }

Tristan Carrier Baudouin's avatar
Tristan Carrier Baudouin committed
155 156
  void build_edges();
  void clear_edges();
157 158
  bool delaunay_conformity(GFace*);

159
  PointNumero *ConvertDlistToArray(DListPeek *dlist, int *n);
160 161
};

162
void centroidOfOrientedBox(std::vector<SPoint2> &pts,
Christophe Geuzaine's avatar
Christophe Geuzaine committed
163
                           const double &angle,
164 165 166
                           double &xc,
                           double &yc,
                           double &inertia,
167
			   double &area);
168
void centroidOfPolygon(SPoint2 &pc,
Christophe Geuzaine's avatar
Christophe Geuzaine committed
169
                       std::vector<SPoint2> &pts,
170
                       double &xc,
Christophe Geuzaine's avatar
Christophe Geuzaine committed
171 172
                       double &yc,
                       double &inertia,
173
		       double &areaCell,
Christophe Geuzaine's avatar
Christophe Geuzaine committed
174
                       simpleFunction<double> *bgm = 0);
175

176
#endif