Instrument Neutral Distributed Interface INDI  2.0.2
Classes | Public Types | Public Member Functions | Static Public Member Functions | Public Attributes | Static Public Attributes | List of all members
INDI::AlignmentSubsystem::ConvexHull Class Reference

This class computes the convex hull of a set of 3d points. More...

#include <ConvexHull.h>

Classes

struct  tEdgeStructure
 
struct  tFaceStructure
 
struct  tVertexStructure
 

Public Types

enum  { X = 0 , Y = 1 , Z = 2 }
 
typedef struct tVertexStructure tsVertex
 
typedef tsVertextVertex
 
typedef struct tEdgeStructure tsEdge
 
typedef tsEdgetEdge
 
typedef struct tFaceStructure tsFace
 
typedef tsFacetFace
 

Public Member Functions

 ConvexHull ()
 
virtual ~ConvexHull ()
 
bool AddOne (tVertex p)
 AddOne is passed a vertex. It first determines all faces visible from that point. If none are visible then the point is marked as not onhull. Next is a loop over edges. If both faces adjacent to an edge are visible, then the edge is marked for deletion. If just one of the adjacent faces is visible then a new face is constructed. More...
 
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 [1]st endpoint of the [ith] edge of the face. More...
 
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 triangles. Only prints positive information when debug is true, but always prints negative information. More...
 
void Checks ()
 Checks the consistency of the hull and prints the results to the standard error output. More...
 
void CleanEdges ()
 CleanEdges runs through the edge list and cleans up the structure. If there is a newface then it will put that face in place of the visible face and NULL out newface. It also deletes so marked edges. More...
 
void CleanFaces ()
 CleanFaces runs through the face list and deletes any face marked visible. More...
 
void CleanUp (tVertex *pvnext)
 CleanUp goes through each data structure list and clears all flags and NULLs out some pointers. The order of processing (edges, faces, vertices) is important. More...
 
void CleanVertices (tVertex *pvnext)
 CleanVertices runs through the vertex list and deletes the vertices that are marked as processed but are not incident to any undeleted edges. The pointer to vnext, pvnext, is used to alter vnext in ConstructHull() if we are about to delete vnext. More...
 
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 of the cross product is zero. More...
 
void Consistency ()
 Consistency runs through the edge list and checks that all adjacent faces have their endpoints in opposite order. This verifies that the vertices are in counterclockwise order. More...
 
void ConstructHull ()
 ConstructHull adds the vertices to the hull one at a time. The hull vertices are those in the list marked as onhull. More...
 
void Convexity ()
 Convexity checks that the volume between every face and every point is negative. This shows that each point is inside every face and therefore the hull is convex. More...
 
bool DoubleTriangle ()
 DoubleTriangle builds the initial double triangle. It first finds 3 noncollinear points and makes two faces out of them, in opposite order. It then finds a fourth point that is not coplanar with that face. The vertices are stored in the face structure in counterclockwise order so that the volume between the face and the point is negative. Lastly, the 3 newfaces to the fourth point are constructed and the data structures are cleaned up. More...
 
void EdgeOrderOnFaces ()
 EdgeOrderOnFaces: puts e0 between v0 and v1, e1 between v1 and v2, e2 between v2 and v0 on each face. This should be unnecessary, alas. Not used in code, but useful for other purposes. More...
 
int GetScaleFactor () const
 Set the floating point to integer scaling factor. More...
 
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 vertices in the same order as in the visible face. The third vertex is always p. Although no specific ordering of the edges of a face are used by the code, the following condition is maintained for each face f: one of the two endpoints of f->edge[i] matches f->vertex[i]. But note that this does not imply that f->edge[i] is between f->vertex[i] and f->vertex[(i+1)%3]. (Thanks to Bob Williamson.) More...
 
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. It returns a pointer to the new face. More...
 
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 face. More...
 
void MakeNewVertex (double x, double y, double z, int VertexId)
 Makes a vertex from the supplied information and adds it to the vertices list. More...
 
tEdge MakeNullEdge ()
 MakeNullEdge creates a new cell and initializes all pointers to NULL and sets all flags to off. It returns a pointer to the empty cell. More...
 
tFace MakeNullFace ()
 MakeNullFace creates a new face structure and initializes all of its flags to NULL and sets all the flags to off. It returns a pointer to the empty cell. More...
 
tVertex MakeNullVertex ()
 MakeNullVertex: Makes a vertex, nulls out fields. More...
 
void Print ()
 Print: Prints out the vertices and the faces. Uses the vnum indices corresponding to the order in which the vertices were input. Output is in PostScript format. This code ignores the Z component of all vertices and does not scale the output to fit the page. It use on 3D hulls is not recommended. More...
 
void PrintEdges (std::ofstream &Ofile)
 Prints the edges Ofile. More...
 
void PrintFaces (std::ofstream &Ofile)
 Prints the faces to Ofile. More...
 
void PrintObj (const char *FileName="chull.obj")
 Outputs the faces in Lightwave obj format for 3d viewing. The files chull.obj and chull.mtl are written to the current working directory. More...
 
void PrintOut (const char *FileName, tVertex v)
 Prints vertices, edges and faces to the standard error output. More...
 
void PrintPoint (tVertex p)
 Prints a single vertex to the standard output. More...
 
void PrintVertices (std::ofstream &Ofile)
 Prints vertices to Ofile. More...
 
void ReadVertices ()
 ReadVertices: Reads in the vertices, and links them into a circular list with MakeNullVertex. There is no need for the # of vertices to be the first line: the function looks for EOF instead. Sets the global variable vertices via the add<> template function. More...
 
void Reset ()
 Frees the vertices edges and faces lists and resets the debug and check flags. More...
 
void SetScaleFactor (const int NewScaleFactor)
 Set the floating point to integer scaling factor. If you want to tweak this a good value to start from may well be a little bit more than the resolution of the mounts encoders. Whatever is used must not exceed the default value which is set to the constant SAFE. More...
 
void SubVec (int a[3], int b[3], int c[3])
 SubVec: Computes a - b and puts it into c. More...
 
int Volumei (tFace f, tVertex p)
 Volumei returns the volume of the tetrahedron determined by f and p. More...
 
int VolumeSign (tFace f, tVertex p)
 VolumeSign returns the sign of the volume of the tetrahedron determined by f and p. VolumeSign is +1 iff p is on the negative side of f, where the positive side is determined by the rh-rule. So the volume is positive if the ccw normal to f points outside the tetrahedron. The final fewer-multiplications form is due to Bob Williamson. More...
 

Static Public Member Functions

template<class Type >
static void add (Type &head, Type p)
 
template<class Type >
static void remove (Type &head, Type p)
 
template<class Type >
static void swap (Type &t, Type &x, Type &y)
 

Public Attributes

tVertex vertices
 
tEdge edges
 
tFace faces
 

Static Public Attributes

static const bool ONHULL = true
 
static const bool REMOVED = true
 
static const bool VISIBLE = true
 
static const bool PROCESSED = true
 
static const int SAFE = 1000000
 

Detailed Description

This class computes the convex hull of a set of 3d points.

Definition at line 59 of file ConvexHull.h.

Member Typedef Documentation

◆ tEdge

Definition at line 122 of file ConvexHull.h.

◆ tFace

Definition at line 125 of file ConvexHull.h.

◆ tsEdge

Definition at line 119 of file ConvexHull.h.

◆ tsFace

Definition at line 122 of file ConvexHull.h.

◆ tsVertex

Definition at line 105 of file ConvexHull.h.

◆ tVertex

Definition at line 119 of file ConvexHull.h.

Member Enumeration Documentation

◆ anonymous enum

anonymous enum
Enumerator

Definition at line 65 of file ConvexHull.h.

Constructor & Destructor Documentation

◆ ConvexHull()

INDI::AlignmentSubsystem::ConvexHull::ConvexHull ( )

Definition at line 44 of file ConvexHull.cpp.

◆ ~ConvexHull()

virtual INDI::AlignmentSubsystem::ConvexHull::~ConvexHull ( )
inlinevirtual

Definition at line 63 of file ConvexHull.h.

Member Function Documentation

◆ add()

template<class Type >
static void INDI::AlignmentSubsystem::ConvexHull::add ( Type head,
Type  p 
)
inlinestatic

Definition at line 73 of file ConvexHull.h.

◆ AddOne()

bool INDI::AlignmentSubsystem::ConvexHull::AddOne ( tVertex  p)

AddOne is passed a vertex. It first determines all faces visible from that point. If none are visible then the point is marked as not onhull. Next is a loop over edges. If both faces adjacent to an edge are visible, then the edge is marked for deletion. If just one of the adjacent faces is visible then a new face is constructed.

Definition at line 49 of file ConvexHull.cpp.

◆ CheckEndpts()

void INDI::AlignmentSubsystem::ConvexHull::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 [1]st endpoint of the [ith] edge of the face.

Definition at line 103 of file ConvexHull.cpp.

◆ CheckEuler()

void INDI::AlignmentSubsystem::ConvexHull::CheckEuler ( int  V,
int  E,
int  F 
)

CheckEuler checks Euler's relation, as well as its implications when all faces are known to be triangles. Only prints positive information when debug is true, but always prints negative information.

Definition at line 139 of file ConvexHull.cpp.

◆ Checks()

void INDI::AlignmentSubsystem::ConvexHull::Checks ( )

Checks the consistency of the hull and prints the results to the standard error output.

Definition at line 160 of file ConvexHull.cpp.

◆ CleanEdges()

void INDI::AlignmentSubsystem::ConvexHull::CleanEdges ( )

CleanEdges runs through the edge list and cleans up the structure. If there is a newface then it will put that face in place of the visible face and NULL out newface. It also deletes so marked edges.

Definition at line 196 of file ConvexHull.cpp.

◆ CleanFaces()

void INDI::AlignmentSubsystem::ConvexHull::CleanFaces ( )

CleanFaces runs through the face list and deletes any face marked visible.

Definition at line 239 of file ConvexHull.cpp.

◆ CleanUp()

void INDI::AlignmentSubsystem::ConvexHull::CleanUp ( tVertex pvnext)

CleanUp goes through each data structure list and clears all flags and NULLs out some pointers. The order of processing (edges, faces, vertices) is important.

Definition at line 264 of file ConvexHull.cpp.

◆ CleanVertices()

void INDI::AlignmentSubsystem::ConvexHull::CleanVertices ( tVertex pvnext)

CleanVertices runs through the vertex list and deletes the vertices that are marked as processed but are not incident to any undeleted edges. The pointer to vnext, pvnext, is used to alter vnext in ConstructHull() if we are about to delete vnext.

Definition at line 271 of file ConvexHull.cpp.

◆ Collinear()

bool INDI::AlignmentSubsystem::ConvexHull::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 of the cross product is zero.

Definition at line 322 of file ConvexHull.cpp.

◆ Consistency()

void INDI::AlignmentSubsystem::ConvexHull::Consistency ( )

Consistency runs through the edge list and checks that all adjacent faces have their endpoints in opposite order. This verifies that the vertices are in counterclockwise order.

Definition at line 329 of file ConvexHull.cpp.

◆ ConstructHull()

void INDI::AlignmentSubsystem::ConvexHull::ConstructHull ( )

ConstructHull adds the vertices to the hull one at a time. The hull vertices are those in the list marked as onhull.

Definition at line 360 of file ConvexHull.cpp.

◆ Convexity()

void INDI::AlignmentSubsystem::ConvexHull::Convexity ( )

Convexity checks that the volume between every face and every point is negative. This shows that each point is inside every face and therefore the hull is convex.

Definition at line 387 of file ConvexHull.cpp.

◆ DoubleTriangle()

bool INDI::AlignmentSubsystem::ConvexHull::DoubleTriangle ( )

DoubleTriangle builds the initial double triangle. It first finds 3 noncollinear points and makes two faces out of them, in opposite order. It then finds a fourth point that is not coplanar with that face. The vertices are stored in the face structure in counterclockwise order so that the volume between the face and the point is negative. Lastly, the 3 newfaces to the fourth point are constructed and the data structures are cleaned up.

Definition at line 421 of file ConvexHull.cpp.

◆ EdgeOrderOnFaces()

void INDI::AlignmentSubsystem::ConvexHull::EdgeOrderOnFaces ( )

EdgeOrderOnFaces: puts e0 between v0 and v1, e1 between v1 and v2, e2 between v2 and v0 on each face. This should be unnecessary, alas. Not used in code, but useful for other purposes.

Definition at line 473 of file ConvexHull.cpp.

◆ GetScaleFactor()

int INDI::AlignmentSubsystem::ConvexHull::GetScaleFactor ( ) const
inline

Set the floating point to integer scaling factor.

Definition at line 263 of file ConvexHull.h.

◆ MakeCcw()

void INDI::AlignmentSubsystem::ConvexHull::MakeCcw ( tFace  f,
tEdge  e,
tVertex  p 
)

MakeCcw puts the vertices in the face structure in counterclock wise order. We want to store the vertices in the same order as in the visible face. The third vertex is always p. Although no specific ordering of the edges of a face are used by the code, the following condition is maintained for each face f: one of the two endpoints of f->edge[i] matches f->vertex[i]. But note that this does not imply that f->edge[i] is between f->vertex[i] and f->vertex[(i+1)%3]. (Thanks to Bob Williamson.)

Definition at line 511 of file ConvexHull.cpp.

◆ MakeConeFace()

ConvexHull::tFace INDI::AlignmentSubsystem::ConvexHull::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. It returns a pointer to the new face.

Definition at line 545 of file ConvexHull.cpp.

◆ MakeFace()

ConvexHull::tFace INDI::AlignmentSubsystem::ConvexHull::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 face.

Definition at line 583 of file ConvexHull.cpp.

◆ MakeNewVertex()

void INDI::AlignmentSubsystem::ConvexHull::MakeNewVertex ( double  x,
double  y,
double  z,
int  VertexId 
)

Makes a vertex from the supplied information and adds it to the vertices list.

Definition at line 623 of file ConvexHull.cpp.

◆ MakeNullEdge()

ConvexHull::tEdge INDI::AlignmentSubsystem::ConvexHull::MakeNullEdge ( )

MakeNullEdge creates a new cell and initializes all pointers to NULL and sets all flags to off. It returns a pointer to the empty cell.

Definition at line 639 of file ConvexHull.cpp.

◆ MakeNullFace()

ConvexHull::tFace INDI::AlignmentSubsystem::ConvexHull::MakeNullFace ( )

MakeNullFace creates a new face structure and initializes all of its flags to NULL and sets all the flags to off. It returns a pointer to the empty cell.

Definition at line 651 of file ConvexHull.cpp.

◆ MakeNullVertex()

ConvexHull::tVertex INDI::AlignmentSubsystem::ConvexHull::MakeNullVertex ( )

MakeNullVertex: Makes a vertex, nulls out fields.

Definition at line 666 of file ConvexHull.cpp.

◆ Print()

void INDI::AlignmentSubsystem::ConvexHull::Print ( )

Print: Prints out the vertices and the faces. Uses the vnum indices corresponding to the order in which the vertices were input. Output is in PostScript format. This code ignores the Z component of all vertices and does not scale the output to fit the page. It use on 3D hulls is not recommended.

Definition at line 679 of file ConvexHull.cpp.

◆ PrintEdges()

void INDI::AlignmentSubsystem::ConvexHull::PrintEdges ( std::ofstream &  Ofile)

Prints the edges Ofile.

Definition at line 801 of file ConvexHull.cpp.

◆ PrintFaces()

void INDI::AlignmentSubsystem::ConvexHull::PrintFaces ( std::ofstream &  Ofile)

Prints the faces to Ofile.

Definition at line 824 of file ConvexHull.cpp.

◆ PrintObj()

void INDI::AlignmentSubsystem::ConvexHull::PrintObj ( const char *  FileName = "chull.obj")

Outputs the faces in Lightwave obj format for 3d viewing. The files chull.obj and chull.mtl are written to the current working directory.

Definition at line 847 of file ConvexHull.cpp.

◆ PrintOut()

void INDI::AlignmentSubsystem::ConvexHull::PrintOut ( const char *  FileName,
tVertex  v 
)

Prints vertices, edges and faces to the standard error output.

Definition at line 924 of file ConvexHull.cpp.

◆ PrintPoint()

void INDI::AlignmentSubsystem::ConvexHull::PrintPoint ( tVertex  p)

Prints a single vertex to the standard output.

Definition at line 938 of file ConvexHull.cpp.

◆ PrintVertices()

void INDI::AlignmentSubsystem::ConvexHull::PrintVertices ( std::ofstream &  Ofile)

Prints vertices to Ofile.

Definition at line 946 of file ConvexHull.cpp.

◆ ReadVertices()

void INDI::AlignmentSubsystem::ConvexHull::ReadVertices ( )

ReadVertices: Reads in the vertices, and links them into a circular list with MakeNullVertex. There is no need for the # of vertices to be the first line: the function looks for EOF instead. Sets the global variable vertices via the add<> template function.

Definition at line 966 of file ConvexHull.cpp.

◆ remove()

template<class Type >
static void INDI::AlignmentSubsystem::ConvexHull::remove ( Type head,
Type  p 
)
inlinestatic

Definition at line 90 of file ConvexHull.h.

◆ Reset()

void INDI::AlignmentSubsystem::ConvexHull::Reset ( )

Frees the vertices edges and faces lists and resets the debug and check flags.

Definition at line 988 of file ConvexHull.cpp.

◆ SetScaleFactor()

void INDI::AlignmentSubsystem::ConvexHull::SetScaleFactor ( const int  NewScaleFactor)
inline

Set the floating point to integer scaling factor. If you want to tweak this a good value to start from may well be a little bit more than the resolution of the mounts encoders. Whatever is used must not exceed the default value which is set to the constant SAFE.

Definition at line 359 of file ConvexHull.h.

◆ SubVec()

void INDI::AlignmentSubsystem::ConvexHull::SubVec ( int  a[3],
int  b[3],
int  c[3] 
)

SubVec: Computes a - b and puts it into c.

Definition at line 1034 of file ConvexHull.cpp.

◆ swap()

template<class Type >
static void INDI::AlignmentSubsystem::ConvexHull::swap ( Type t,
Type x,
Type y 
)
inlinestatic

Definition at line 105 of file ConvexHull.h.

◆ Volumei()

int INDI::AlignmentSubsystem::ConvexHull::Volumei ( tFace  f,
tVertex  p 
)

Volumei returns the volume of the tetrahedron determined by f and p.

Definition at line 1043 of file ConvexHull.cpp.

◆ VolumeSign()

int INDI::AlignmentSubsystem::ConvexHull::VolumeSign ( tFace  f,
tVertex  p 
)

VolumeSign returns the sign of the volume of the tetrahedron determined by f and p. VolumeSign is +1 iff p is on the negative side of f, where the positive side is determined by the rh-rule. So the volume is positive if the ccw normal to f points outside the tetrahedron. The final fewer-multiplications form is due to Bob Williamson.

Definition at line 1063 of file ConvexHull.cpp.

Member Data Documentation

◆ edges

tEdge INDI::AlignmentSubsystem::ConvexHull::edges

Definition at line 171 of file ConvexHull.h.

◆ faces

tFace INDI::AlignmentSubsystem::ConvexHull::faces

Definition at line 172 of file ConvexHull.h.

◆ ONHULL

const bool INDI::AlignmentSubsystem::ConvexHull::ONHULL = true
static

Definition at line 164 of file ConvexHull.h.

◆ PROCESSED

const bool INDI::AlignmentSubsystem::ConvexHull::PROCESSED = true
static

Definition at line 167 of file ConvexHull.h.

◆ REMOVED

const bool INDI::AlignmentSubsystem::ConvexHull::REMOVED = true
static

Definition at line 165 of file ConvexHull.h.

◆ SAFE

const int INDI::AlignmentSubsystem::ConvexHull::SAFE = 1000000
static

Definition at line 168 of file ConvexHull.h.

◆ vertices

tVertex INDI::AlignmentSubsystem::ConvexHull::vertices

Definition at line 170 of file ConvexHull.h.

◆ VISIBLE

const bool INDI::AlignmentSubsystem::ConvexHull::VISIBLE = true
static

Definition at line 166 of file ConvexHull.h.


The documentation for this class was generated from the following files: