Instrument Neutral Distributed Interface INDI
2.0.2
|
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 tsVertex * | tVertex |
typedef struct tEdgeStructure | tsEdge |
typedef tsEdge * | tEdge |
typedef struct tFaceStructure | tsFace |
typedef tsFace * | tFace |
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 |
This class computes the convex hull of a set of 3d points.
Definition at line 59 of file ConvexHull.h.
Definition at line 122 of file ConvexHull.h.
Definition at line 125 of file ConvexHull.h.
typedef struct tEdgeStructure INDI::AlignmentSubsystem::ConvexHull::tsEdge |
Definition at line 119 of file ConvexHull.h.
typedef struct tFaceStructure INDI::AlignmentSubsystem::ConvexHull::tsFace |
Definition at line 122 of file ConvexHull.h.
typedef struct tVertexStructure INDI::AlignmentSubsystem::ConvexHull::tsVertex |
Definition at line 105 of file ConvexHull.h.
Definition at line 119 of file ConvexHull.h.
anonymous enum |
Enumerator | |
---|---|
X | |
Y | |
Z |
Definition at line 65 of file ConvexHull.h.
INDI::AlignmentSubsystem::ConvexHull::ConvexHull | ( | ) |
Definition at line 44 of file ConvexHull.cpp.
|
inlinevirtual |
Definition at line 63 of file ConvexHull.h.
|
inlinestatic |
Definition at line 73 of file ConvexHull.h.
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.
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.
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.
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.
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.
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.
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.
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 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.
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.
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.
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.
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.
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.
|
inline |
Set the floating point to integer scaling factor.
Definition at line 263 of file ConvexHull.h.
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.
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.
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.
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.
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.
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.
ConvexHull::tVertex INDI::AlignmentSubsystem::ConvexHull::MakeNullVertex | ( | ) |
MakeNullVertex: Makes a vertex, nulls out fields.
Definition at line 666 of file ConvexHull.cpp.
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.
void INDI::AlignmentSubsystem::ConvexHull::PrintEdges | ( | std::ofstream & | Ofile | ) |
Prints the edges Ofile.
Definition at line 801 of file ConvexHull.cpp.
void INDI::AlignmentSubsystem::ConvexHull::PrintFaces | ( | std::ofstream & | Ofile | ) |
Prints the faces to Ofile.
Definition at line 824 of file ConvexHull.cpp.
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.
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.
void INDI::AlignmentSubsystem::ConvexHull::PrintPoint | ( | tVertex | p | ) |
Prints a single vertex to the standard output.
Definition at line 938 of file ConvexHull.cpp.
void INDI::AlignmentSubsystem::ConvexHull::PrintVertices | ( | std::ofstream & | Ofile | ) |
Prints vertices to Ofile.
Definition at line 946 of file ConvexHull.cpp.
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.
|
inlinestatic |
Definition at line 90 of file ConvexHull.h.
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.
|
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.
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.
|
inlinestatic |
Definition at line 105 of file ConvexHull.h.
Volumei returns the volume of the tetrahedron determined by f and p.
Definition at line 1043 of file ConvexHull.cpp.
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.
tEdge INDI::AlignmentSubsystem::ConvexHull::edges |
Definition at line 171 of file ConvexHull.h.
tFace INDI::AlignmentSubsystem::ConvexHull::faces |
Definition at line 172 of file ConvexHull.h.
|
static |
Definition at line 164 of file ConvexHull.h.
|
static |
Definition at line 167 of file ConvexHull.h.
|
static |
Definition at line 165 of file ConvexHull.h.
|
static |
Definition at line 168 of file ConvexHull.h.
tVertex INDI::AlignmentSubsystem::ConvexHull::vertices |
Definition at line 170 of file ConvexHull.h.
|
static |
Definition at line 166 of file ConvexHull.h.