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

#include <ConvexHull.h>

Collaboration diagram for INDI::AlignmentSubsystem::ConvexHull:

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. 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. 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. 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. 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. 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. More...

void	ConstructHull ()
	ConstructHull adds the vertices to the hull one at a time. More...

void	Convexity ()
	Convexity checks that the volume between every face and every point is negative. More...

void	DoubleTriangle ()
	DoubleTriangle builds the initial double triangle. More...

void	EdgeOrderOnFaces ()
	EdgeOrderOnFaces: puts e0 between v0 and v1, e1 between v1 and v2, e2 between v2 and v0 on each face. 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. 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. More...

tFace	MakeFace (tVertex v0, tVertex v1, tVertex v2, tFace f)
	MakeFace creates a new face structure from three vertices (in ccw order). 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. More...

tFace	MakeNullFace ()
	MakeNullFace creates a new face structure and initializes all of its flags to NULL and sets all the flags to off. More...

tVertex	MakeNullVertex ()
	MakeNullVertex: Makes a vertex, nulls out fields. More...

void	Print ()
	Print: Prints out the vertices and the faces. 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. 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. 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. 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. 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

Private Attributes
bool	debug

bool	check

int	ScaleFactor

Detailed Description

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

Member Typedef Documentation

◆ tEdge

typedef tsEdge* INDI::AlignmentSubsystem::ConvexHull::tEdge

◆ tFace

typedef tsFace* INDI::AlignmentSubsystem::ConvexHull::tFace

◆ tsEdge

typedef struct tEdgeStructure INDI::AlignmentSubsystem::ConvexHull::tsEdge

◆ tsFace

typedef struct tFaceStructure INDI::AlignmentSubsystem::ConvexHull::tsFace

◆ tsVertex

typedef struct tVertexStructure INDI::AlignmentSubsystem::ConvexHull::tsVertex

◆ tVertex

typedef tsVertex* INDI::AlignmentSubsystem::ConvexHull::tVertex

Member Enumeration Documentation

◆ anonymous enum

anonymous enum

Enumerator
X
Y
Z

Constructor & Destructor Documentation

◆ ConvexHull()

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

◆ ~ConvexHull()

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

inlinevirtual

Member Function Documentation

◆ add()

template<class Type >

static void INDI::AlignmentSubsystem::ConvexHull::add	(	Type &	head,
		Type	p
	)

inlinestatic

◆ 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.

◆ 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.

◆ 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.

◆ Checks()

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

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

◆ 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.

◆ CleanFaces()

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

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

◆ 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.

◆ 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.

◆ 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.

◆ 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.

◆ 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.

◆ 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.

◆ DoubleTriangle()

void 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.

◆ 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.

◆ GetScaleFactor()

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

inline

Set the floating point to integer scaling factor.

◆ 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.)

◆ 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.

◆ 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.

◆ 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.

◆ 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.

◆ 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.

◆ MakeNullVertex()

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

MakeNullVertex: Makes a vertex, nulls out fields.

◆ 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.

◆ PrintEdges()

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

Prints the edges Ofile.

◆ PrintFaces()

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

Prints the faces to Ofile.

◆ 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.

◆ PrintOut()

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

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

◆ PrintPoint()

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

Prints a single vertex to the standard output.

◆ PrintVertices()

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

Prints vertices to Ofile.

◆ 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.

◆ remove()

template<class Type >

static void INDI::AlignmentSubsystem::ConvexHull::remove	(	Type &	head,
		Type	p
	)

inlinestatic

◆ Reset()

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

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

◆ 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.

◆ SubVec()

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

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

◆ swap()

template<class Type >

static void INDI::AlignmentSubsystem::ConvexHull::swap	(	Type &	t,
		Type &	x,
		Type &	y
	)

inlinestatic

◆ Volumei()

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

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

◆ 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.

Member Data Documentation

◆ check

bool INDI::AlignmentSubsystem::ConvexHull::check

private

◆ debug

bool INDI::AlignmentSubsystem::ConvexHull::debug

private

◆ edges

tEdge INDI::AlignmentSubsystem::ConvexHull::edges

◆ faces

tFace INDI::AlignmentSubsystem::ConvexHull::faces

◆ ONHULL

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

static

◆ PROCESSED

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

static

◆ REMOVED

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

static

◆ SAFE

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

static

◆ ScaleFactor

int INDI::AlignmentSubsystem::ConvexHull::ScaleFactor

private

◆ vertices

tVertex INDI::AlignmentSubsystem::ConvexHull::vertices

◆ VISIBLE

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

static

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

ln/3rdparty/src/indilib/indi-1.7.4/libindi/libs/indibase/alignment/ConvexHull.h
ln/3rdparty/src/indilib/indi-1.7.4/libindi/libs/indibase/alignment/ConvexHull.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Private Attributes

Detailed Description

Member Typedef Documentation

◆ tEdge

◆ tFace

◆ tsEdge

◆ tsFace

◆ tsVertex

◆ tVertex

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ ConvexHull()

◆ ~ConvexHull()

Member Function Documentation

◆ add()

◆ AddOne()

◆ CheckEndpts()

◆ CheckEuler()

◆ Checks()

◆ CleanEdges()

◆ CleanFaces()

◆ CleanUp()

◆ CleanVertices()

◆ Collinear()

◆ Consistency()

◆ ConstructHull()

◆ Convexity()

◆ DoubleTriangle()

◆ EdgeOrderOnFaces()

◆ GetScaleFactor()

◆ MakeCcw()

◆ MakeConeFace()

◆ MakeFace()

◆ MakeNewVertex()

◆ MakeNullEdge()

◆ MakeNullFace()

◆ MakeNullVertex()

◆ Print()

◆ PrintEdges()

◆ PrintFaces()

◆ PrintObj()

◆ PrintOut()

◆ PrintPoint()

◆ PrintVertices()

◆ ReadVertices()

◆ remove()

◆ Reset()

◆ SetScaleFactor()

◆ SubVec()

◆ swap()

◆ Volumei()

◆ VolumeSign()

Member Data Documentation

◆ check

◆ debug

◆ edges

◆ faces

◆ ONHULL

◆ PROCESSED

◆ REMOVED

◆ SAFE

◆ ScaleFactor

◆ vertices

◆ VISIBLE