Instrument Neutral Distributed Interface INDI  1.9.5
ConvexHull.h
Go to the documentation of this file.
1 
9 #pragma once
10 
11 // This C++ code is based on the c code described below
12 // it was ported to c++ by Roger James in December 2013
13 // !!!!!!!!!!!!!!!!!!!!!!! IMPORTANT !!!!!!!!!!!!!!!!!!
14 // This must code must use integer coordinates. A naive conversion
15 // to floating point WILL NOT work. For the reasons behind this
16 // have a look at at section 4.3.5 of the O'Rourke book. For more
17 // information try http://www.mpi-inf.mpg.de/departments/d1/ClassroomExamples/
18 // For INDI alignment purposes we need to scale floating point coordinates
19 // into the integer space before using this algorithm.
20 
21 /*
22 This code is described in "Computational Geometry in C" (Second Edition),
23 Chapter 4. It is not written to be comprehensible without the
24 explanation in that book.
25 
26 Input: 3n integer coordinates for the points.
27 Output: the 3D convex hull, in postscript with embedded comments
28  showing the vertices and faces.
29 
30 Compile: gcc -o chull chull.c (or simply: make)
31 
32 Written by Joseph O'Rourke, with contributions by
33  Kristy Anderson, John Kutcher, Catherine Schevon, Susan Weller.
34 Last modified: May 2000
35 Questions to orourke@cs.smith.edu.
36 
37 --------------------------------------------------------------------
38 This code is Copyright 2000 by Joseph O'Rourke. It may be freely
39 redistributed in its entirety provided that this copyright notice is
40 not removed.
41 --------------------------------------------------------------------
42 */
43 
44 #include <gsl/gsl_matrix.h>
45 
46 #include <cmath>
47 #include <cstring>
48 #include <fstream>
49 #include <limits>
50 
51 namespace INDI
52 {
53 namespace AlignmentSubsystem
54 {
60 {
61  public:
62  ConvexHull();
63  virtual ~ConvexHull() {}
64 
65  enum
66  {
67  X = 0,
68  Y = 1,
69  Z = 2
70  };
71 
72  template <class Type>
73  static void add(Type &head, Type p)
74  {
75  if (NULL != head)
76  {
77  p->next = head;
78  p->prev = head->prev;
79  head->prev = p;
80  p->prev->next = p;
81  }
82  else
83  {
84  head = p;
85  head->next = head->prev = p;
86  }
87  };
88 
89  template <class Type>
90  static void remove(Type &head, Type p)
91  {
92  if (NULL != head)
93  {
94  if (head == head->next)
95  head = NULL;
96  else if (p == head)
97  head = head->next;
98  p->next->prev = p->prev;
99  p->prev->next = p->next;
100  delete p;
101  }
102  };
103 
104  template <class Type>
105  static void swap(Type &t, Type &x, Type &y)
106  {
107  t = x;
108  x = y;
109  y = t;
110  };
111 
112  // Explicit forward declarations
113  struct tVertexStructure;
114  struct tFaceStructure;
115  struct tEdgeStructure;
116 
117  /* Define structures for vertices, edges and faces */
118  typedef struct tVertexStructure tsVertex;
119  typedef tsVertex *tVertex;
120 
121  typedef struct tEdgeStructure tsEdge;
122  typedef tsEdge *tEdge;
123 
124  typedef struct tFaceStructure tsFace;
125  typedef tsFace *tFace;
126 
128  {
129  int v[3];
130  int vnum;
131  tEdge duplicate; // pointer to incident cone edge (or NULL)
132  bool onhull; // True iff point on hull.
133  bool mark; // True iff point already processed.
135  };
136 
138  {
141  tFace newface; // pointer to incident cone face.
142  bool delete_it; // True iff edge should be delete.
144  };
145 
147  {
148  tFaceStructure() { pMatrix = gsl_matrix_alloc(3, 3); }
149  ~tFaceStructure() { gsl_matrix_free(pMatrix); }
152  bool visible; // True iff face visible from new point.
154  gsl_matrix *pMatrix;
155  };
156 
157  /* Define flags */
158  static const bool ONHULL = true;
159  static const bool REMOVED = true;
160  static const bool VISIBLE = true;
161  static const bool PROCESSED = true;
162  static const int SAFE = 1000000; /* Range of safe coord values. */
163 
167 
174  bool AddOne(tVertex p);
175 
180  void CheckEndpts();
181 
186  void CheckEuler(int V, int E, int F);
187 
191  void Checks();
192 
197  void CleanEdges();
198 
201  void CleanFaces();
202 
207  void CleanUp(tVertex *pvnext);
208 
215  void CleanVertices(tVertex *pvnext);
216 
220  bool Collinear(tVertex a, tVertex b, tVertex c);
221 
226  void Consistency();
227 
231  void ConstructHull();
232 
237  void Convexity();
238 
247  void DoubleTriangle();
248 
253  void EdgeOrderOnFaces();
254 
257  int GetScaleFactor() const { return ScaleFactor; }
258 
268  void MakeCcw(tFace f, tEdge e, tVertex p);
269 
275 
279  tFace MakeFace(tVertex v0, tVertex v1, tVertex v2, tFace f);
280 
283  void MakeNewVertex(double x, double y, double z, int VertexId);
284 
289 
295 
299 
306  void Print();
307 
310  void PrintEdges(std::ofstream &Ofile);
311 
314  void PrintFaces(std::ofstream &Ofile);
315 
320  void PrintObj(const char *FileName = "chull.obj");
321 
324  void PrintOut(const char *FileName, tVertex v);
325 
328  void PrintPoint(tVertex p);
329 
332  void PrintVertices(std::ofstream &Ofile);
333 
339  void ReadVertices();
340 
343  void Reset();
344 
350  void SetScaleFactor(const int NewScaleFactor) { ScaleFactor = NewScaleFactor; }
351 
354  void SubVec(int a[3], int b[3], int c[3]);
355 
359  int Volumei(tFace f, tVertex p);
360 
367  int VolumeSign(tFace f, tVertex p);
368 
369  private:
370  bool debug;
371  bool check;
372 
373  int ScaleFactor; // Scale factor to be used when converting from floating point to integers and vice versa
374 };
375 
376 } // namespace AlignmentSubsystem
377 } // namespace INDI
INDI::AlignmentSubsystem::ConvexHull::Y
@ Y
Definition: ConvexHull.h:68
INDI::AlignmentSubsystem::ConvexHull::tFaceStructure::prev
tFace prev
Definition: ConvexHull.h:153
INDI::AlignmentSubsystem::ConvexHull::SAFE
static const int SAFE
Definition: ConvexHull.h:162
INDI::AlignmentSubsystem::ConvexHull::tFaceStructure
Definition: ConvexHull.h:146
INDI::AlignmentSubsystem::ConvexHull::Collinear
bool Collinear(tVertex a, tVertex b, tVertex c)
Collinear checks to see if the three points given are collinear, by checking to see if each element o...
Definition: ConvexHull.cpp:310
INDI::AlignmentSubsystem::ConvexHull::ReadVertices
void ReadVertices()
ReadVertices: Reads in the vertices, and links them into a circular list with MakeNullVertex....
Definition: ConvexHull.cpp:939
INDI::AlignmentSubsystem::ConvexHull::add
static void add(Type &head, Type p)
Definition: ConvexHull.h:73
INDI::AlignmentSubsystem::ConvexHull::ConstructHull
void ConstructHull()
ConstructHull adds the vertices to the hull one at a time. The hull vertices are those in the list ma...
Definition: ConvexHull.cpp:347
INDI::AlignmentSubsystem::ConvexHull::PrintObj
void PrintObj(const char *FileName="chull.obj")
Outputs the faces in Lightwave obj format for 3d viewing. The files chull.obj and chull....
Definition: ConvexHull.cpp:824
INDI::AlignmentSubsystem::ConvexHull::Print
void Print()
Print: Prints out the vertices and the faces. Uses the vnum indices corresponding to the order in whi...
Definition: ConvexHull.cpp:666
INDI::AlignmentSubsystem::ConvexHull::SubVec
void SubVec(int a[3], int b[3], int c[3])
SubVec: Computes a - b and puts it into c.
Definition: ConvexHull.cpp:1004
INDI::AlignmentSubsystem::ConvexHull::Z
@ Z
Definition: ConvexHull.h:69
INDI::AlignmentSubsystem::ConvexHull::MakeNewVertex
void MakeNewVertex(double x, double y, double z, int VertexId)
Makes a vertex from the supplied information and adds it to the vertices list.
Definition: ConvexHull.cpp:610
INDI::AlignmentSubsystem::ConvexHull::MakeFace
tFace MakeFace(tVertex v0, tVertex v1, tVertex v2, tFace f)
MakeFace creates a new face structure from three vertices (in ccw order). It returns a pointer to the...
Definition: ConvexHull.cpp:570
INDI::AlignmentSubsystem::ConvexHull::MakeCcw
void MakeCcw(tFace f, tEdge e, tVertex p)
MakeCcw puts the vertices in the face structure in counterclock wise order. We want to store the vert...
Definition: ConvexHull.cpp:498
INDI::AlignmentSubsystem::ConvexHull::CheckEndpts
void CheckEndpts()
Checks that, for each face, for each i={0,1,2}, the [i]th vertex of that face is either the [0]th or ...
Definition: ConvexHull.cpp:101
INDI::AlignmentSubsystem::ConvexHull::MakeConeFace
tFace MakeConeFace(tEdge e, tVertex p)
MakeConeFace makes a new face and two new edges between the edge and the point that are passed to it....
Definition: ConvexHull.cpp:532
INDI::AlignmentSubsystem::ConvexHull::tVertexStructure::v
int v[3]
Definition: ConvexHull.h:129
INDI::AlignmentSubsystem::ConvexHull::tVertex
tsVertex * tVertex
Definition: ConvexHull.h:119
INDI::AlignmentSubsystem::ConvexHull::tFaceStructure::pMatrix
gsl_matrix * pMatrix
Definition: ConvexHull.h:154
INDI::AlignmentSubsystem::ConvexHull::tEdgeStructure
Definition: ConvexHull.h:137
INDI::AlignmentSubsystem::ConvexHull::tEdge
tsEdge * tEdge
Definition: ConvexHull.h:122
INDI::AlignmentSubsystem::ConvexHull::Volumei
int Volumei(tFace f, tVertex p)
Volumei returns the volume of the tetrahedron determined by f and p.
Definition: ConvexHull.cpp:1013
INDI::AlignmentSubsystem::ConvexHull::tVertexStructure::duplicate
tEdge duplicate
Definition: ConvexHull.h:131
INDI::AlignmentSubsystem::ConvexHull::PROCESSED
static const bool PROCESSED
Definition: ConvexHull.h:161
INDI::AlignmentSubsystem::ConvexHull::MakeNullEdge
tEdge MakeNullEdge()
MakeNullEdge creates a new cell and initializes all pointers to NULL and sets all flags to off....
Definition: ConvexHull.cpp:626
INDI::AlignmentSubsystem::ConvexHull::edges
tEdge edges
Definition: ConvexHull.h:165
INDI::AlignmentSubsystem::ConvexHull::tVertexStructure
Definition: ConvexHull.h:127
INDI::AlignmentSubsystem::ConvexHull::ONHULL
static const bool ONHULL
Definition: ConvexHull.h:158
INDI::AlignmentSubsystem::ConvexHull::vertices
tVertex vertices
Definition: ConvexHull.h:164
INDI::AlignmentSubsystem::ConvexHull::tFaceStructure::~tFaceStructure
~tFaceStructure()
Definition: ConvexHull.h:149
INDI::AlignmentSubsystem::ConvexHull::tEdgeStructure::next
tEdge next
Definition: ConvexHull.h:143
INDI::AlignmentSubsystem::ConvexHull::ConvexHull
ConvexHull()
Definition: ConvexHull.cpp:44
INDI::AlignmentSubsystem::ConvexHull::~ConvexHull
virtual ~ConvexHull()
Definition: ConvexHull.h:63
INDI::AlignmentSubsystem::ConvexHull::Reset
void Reset()
Frees the vertices edges and faces lists and resets the debug and check flags.
Definition: ConvexHull.cpp:961
INDI::AlignmentSubsystem::ConvexHull::tFace
tsFace * tFace
Definition: ConvexHull.h:125
INDI::AlignmentSubsystem::ConvexHull::AddOne
bool AddOne(tVertex p)
AddOne is passed a vertex. It first determines all faces visible from that point. If none are visible...
Definition: ConvexHull.cpp:49
INDI::AlignmentSubsystem::ConvexHull::VolumeSign
int VolumeSign(tFace f, tVertex p)
VolumeSign returns the sign of the volume of the tetrahedron determined by f and p....
Definition: ConvexHull.cpp:1033
INDI::AlignmentSubsystem::ConvexHull::tVertexStructure::vnum
int vnum
Definition: ConvexHull.h:130
INDI::AlignmentSubsystem::ConvexHull::CleanUp
void CleanUp(tVertex *pvnext)
CleanUp goes through each data structure list and clears all flags and NULLs out some pointers....
Definition: ConvexHull.cpp:255
INDI::AlignmentSubsystem::ConvexHull::MakeNullFace
tFace MakeNullFace()
MakeNullFace creates a new face structure and initializes all of its flags to NULL and sets all the f...
Definition: ConvexHull.cpp:638
INDI::AlignmentSubsystem::ConvexHull::EdgeOrderOnFaces
void EdgeOrderOnFaces()
EdgeOrderOnFaces: puts e0 between v0 and v1, e1 between v1 and v2, e2 between v2 and v0 on each face....
Definition: ConvexHull.cpp:461
INDI::AlignmentSubsystem::ConvexHull::tFaceStructure::tFaceStructure
tFaceStructure()
Definition: ConvexHull.h:148
INDI::AlignmentSubsystem::ConvexHull::swap
static void swap(Type &t, Type &x, Type &y)
Definition: ConvexHull.h:105
INDI::AlignmentSubsystem::ConvexHull::CleanVertices
void CleanVertices(tVertex *pvnext)
CleanVertices runs through the vertex list and deletes the vertices that are marked as processed but ...
Definition: ConvexHull.cpp:262
INDI::AlignmentSubsystem::ConvexHull::tVertexStructure::next
tVertex next
Definition: ConvexHull.h:134
INDI::AlignmentSubsystem::ConvexHull::X
@ X
Definition: ConvexHull.h:67
INDI::AlignmentSubsystem::ConvexHull::CleanFaces
void CleanFaces()
CleanFaces runs through the face list and deletes any face marked visible.
Definition: ConvexHull.cpp:231
INDI::AlignmentSubsystem::ConvexHull::GetScaleFactor
int GetScaleFactor() const
Set the floating point to integer scaling factor.
Definition: ConvexHull.h:257
INDI::AlignmentSubsystem::ConvexHull::Checks
void Checks()
Checks the consistency of the hull and prints the results to the standard error output.
Definition: ConvexHull.cpp:157
INDI::AlignmentSubsystem::ConvexHull::PrintPoint
void PrintPoint(tVertex p)
Prints a single vertex to the standard output.
Definition: ConvexHull.cpp:912
INDI::AlignmentSubsystem::ConvexHull::tVertexStructure::prev
tVertex prev
Definition: ConvexHull.h:134
INDI::AlignmentSubsystem::ConvexHull::VISIBLE
static const bool VISIBLE
Definition: ConvexHull.h:160
INDI::AlignmentSubsystem::ConvexHull::tEdgeStructure::endpts
tVertex endpts[2]
Definition: ConvexHull.h:140
INDI::AlignmentSubsystem::ConvexHull::tEdgeStructure::adjface
tFace adjface[2]
Definition: ConvexHull.h:139
INDI::AlignmentSubsystem::ConvexHull::DoubleTriangle
void DoubleTriangle()
DoubleTriangle builds the initial double triangle. It first finds 3 noncollinear points and makes two...
Definition: ConvexHull.cpp:405
INDI::AlignmentSubsystem::ConvexHull::CheckEuler
void CheckEuler(int V, int E, int F)
CheckEuler checks Euler's relation, as well as its implications when all faces are known to be triang...
Definition: ConvexHull.cpp:136
INDI::AlignmentSubsystem::ConvexHull::PrintEdges
void PrintEdges(std::ofstream &Ofile)
Prints the edges Ofile.
Definition: ConvexHull.cpp:780
INDI::AlignmentSubsystem::ConvexHull::PrintVertices
void PrintVertices(std::ofstream &Ofile)
Prints vertices to Ofile.
Definition: ConvexHull.cpp:920
INDI::AlignmentSubsystem::ConvexHull::faces
tFace faces
Definition: ConvexHull.h:166
INDI::AlignmentSubsystem::ConvexHull::tVertexStructure::mark
bool mark
Definition: ConvexHull.h:133
Type
Holds the connection type.
INDI::AlignmentSubsystem::ConvexHull::tFaceStructure::edge
tEdge edge[3]
Definition: ConvexHull.h:150
INDI::AlignmentSubsystem::ConvexHull::tEdgeStructure::prev
tEdge prev
Definition: ConvexHull.h:143
INDI::AlignmentSubsystem::ConvexHull::Consistency
void Consistency()
Consistency runs through the edge list and checks that all adjacent faces have their endpoints in opp...
Definition: ConvexHull.cpp:317
INDI::AlignmentSubsystem::ConvexHull::PrintFaces
void PrintFaces(std::ofstream &Ofile)
Prints the faces to Ofile.
Definition: ConvexHull.cpp:802
INDI::AlignmentSubsystem::ConvexHull::tFaceStructure::next
tFace next
Definition: ConvexHull.h:153
INDI::AlignmentSubsystem::ConvexHull::tVertexStructure::onhull
bool onhull
Definition: ConvexHull.h:132
INDI::AlignmentSubsystem::ConvexHull::SetScaleFactor
void SetScaleFactor(const int NewScaleFactor)
Set the floating point to integer scaling factor. If you want to tweak this a good value to start fro...
Definition: ConvexHull.h:350
INDI
Namespace to encapsulate INDI client, drivers, and mediator classes.
Definition: AlignmentSubsystemForClients.cpp:11
INDI::AlignmentSubsystem::ConvexHull::CleanEdges
void CleanEdges()
CleanEdges runs through the edge list and cleans up the structure. If there is a newface then it will...
Definition: ConvexHull.cpp:190
INDI::AlignmentSubsystem::ConvexHull::remove
static void remove(Type &head, Type p)
Definition: ConvexHull.h:90
INDI::AlignmentSubsystem::ConvexHull::tEdgeStructure::delete_it
bool delete_it
Definition: ConvexHull.h:142
INDI::AlignmentSubsystem::ConvexHull::Convexity
void Convexity()
Convexity checks that the volume between every face and every point is negative. This shows that each...
Definition: ConvexHull.cpp:373
INDI::AlignmentSubsystem::ConvexHull::PrintOut
void PrintOut(const char *FileName, tVertex v)
Prints vertices, edges and faces to the standard error output.
Definition: ConvexHull.cpp:898
INDI::AlignmentSubsystem::ConvexHull::tEdgeStructure::newface
tFace newface
Definition: ConvexHull.h:141
INDI::AlignmentSubsystem::ConvexHull
This class computes the convex hull of a set of 3d points.
Definition: ConvexHull.h:59
INDI::AlignmentSubsystem::ConvexHull::REMOVED
static const bool REMOVED
Definition: ConvexHull.h:159
INDI::AlignmentSubsystem::ConvexHull::MakeNullVertex
tVertex MakeNullVertex()
MakeNullVertex: Makes a vertex, nulls out fields.
Definition: ConvexHull.cpp:653
INDI::AlignmentSubsystem::ConvexHull::tFaceStructure::vertex
tVertex vertex[3]
Definition: ConvexHull.h:151
INDI::AlignmentSubsystem::ConvexHull::tFaceStructure::visible
bool visible
Definition: ConvexHull.h:152