ConvexHull.h

Go to the documentation of this file.

 
#pragma once
 
// This C++ code is based on the c code described below
// it was ported to c++ by Roger James in December 2013
// !!!!!!!!!!!!!!!!!!!!!!! IMPORTANT !!!!!!!!!!!!!!!!!!
// This must code must use integer coordinates. A naive conversion
// to floating point WILL NOT work. For the reasons behind this
// have a look at at section 4.3.5 of the O'Rourke book. For more
// information try http://www.mpi-inf.mpg.de/departments/d1/ClassroomExamples/
// For INDI alignment purposes we need to scale floating point coordinates
// into the integer space before using this algorithm.
 
/*
This code is described in "Computational Geometry in C" (Second Edition),
Chapter 4.  It is not written to be comprehensible without the
explanation in that book.
 
Input: 3n integer coordinates for the points.
Output: the 3D convex hull, in postscript with embedded comments
        showing the vertices and faces.
 
Compile: gcc -o chull chull.c (or simply: make)
 
Written by Joseph O'Rourke, with contributions by
  Kristy Anderson, John Kutcher, Catherine Schevon, Susan Weller.
Last modified: May 2000
Questions to orourke@cs.smith.edu.
 
--------------------------------------------------------------------
This code is Copyright 2000 by Joseph O'Rourke.  It may be freely
redistributed in its entirety provided that this copyright notice is
not removed.
--------------------------------------------------------------------
*/
 
#include <gsl/gsl_matrix.h>
 
#include <cmath>
#include <cstring>
#include <fstream>
#include <limits>
 
namespace INDI
{
namespace AlignmentSubsystem
{
class ConvexHull
{
    public:
        ConvexHull();
        virtual ~ConvexHull() {}
 
        enum
        {
            X = 0,
            Y = 1,
            Z = 2
        };
 
        template <class Type>
        static void add(Type &head, Type p)
        {
            if (NULL != head)
            {
                p->next       = head;
                p->prev       = head->prev;
                head->prev    = p;
                p->prev->next = p;
            }
            else
            {
                head       = p;
                head->next = head->prev = p;
            }
        };
 
        template <class Type>
        static void remove(Type &head, Type p)
        {
            if (NULL != head)
            {
                if (head == head->next)
                    head = NULL;
                else if (p == head)
                    head = head->next;
                p->next->prev = p->prev;
                p->prev->next = p->next;
                delete p;
            }
        };
 
        template <class Type>
        static void swap(Type &t, Type &x, Type &y)
        {
            t = x;
            x = y;
            y = t;
        };
 
        // Explicit forward declarations
        struct tVertexStructure;
        struct tFaceStructure;
        struct tEdgeStructure;
 
        /* Define structures for vertices, edges and faces */
        typedef struct tVertexStructure tsVertex;
        typedef tsVertex *tVertex;
 
        typedef struct tEdgeStructure tsEdge;
        typedef tsEdge *tEdge;
 
        typedef struct tFaceStructure tsFace;
        typedef tsFace *tFace;
 
        struct tVertexStructure
        {
            int v[3];
            int vnum;
            tEdge duplicate; // pointer to incident cone edge (or NULL)
            bool onhull;     // True iff point on hull.
            bool mark;       // True iff point already processed.
            tVertex next, prev;
        };
 
        struct tEdgeStructure
        {
            tFace adjface[2];
            tVertex endpts[2];
            tFace newface;  // pointer to incident cone face.
            bool delete_it; //  True iff edge should be delete.
            tEdge next, prev;
        };
 
        struct tFaceStructure
        {
            tFaceStructure()
            {
                pMatrix = gsl_matrix_alloc(3, 3);
            }
            ~tFaceStructure()
            {
                gsl_matrix_free(pMatrix);
            }
            tEdge edge[3];
            tVertex vertex[3];
            bool visible; // True iff face visible from new point.
            tFace next, prev;
            gsl_matrix *pMatrix;
        };
 
        /* Define flags */
        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; /* Range of safe coord values. */
 
        tVertex vertices;
        tEdge edges;
        tFace faces;
 
        bool AddOne(tVertex p);
 
        void CheckEndpts();
 
        void CheckEuler(int V, int E, int F);
 
        void Checks();
 
        void CleanEdges();
 
        void CleanFaces();
 
        void CleanUp(tVertex *pvnext);
 
        void CleanVertices(tVertex *pvnext);
 
        bool Collinear(tVertex a, tVertex b, tVertex c);
 
        void Consistency();
 
        void ConstructHull();
 
        void Convexity();
 
        bool DoubleTriangle();
 
        void EdgeOrderOnFaces();
 
        int GetScaleFactor() const
        {
            return ScaleFactor;
        }
 
        void MakeCcw(tFace f, tEdge e, tVertex p);
 
        tFace MakeConeFace(tEdge e, tVertex p);
 
        tFace MakeFace(tVertex v0, tVertex v1, tVertex v2, tFace f);
 
        void MakeNewVertex(double x, double y, double z, int VertexId);
 
        tEdge MakeNullEdge();
 
        tFace MakeNullFace();
 
        tVertex MakeNullVertex();
 
        void Print();
 
        void PrintEdges(std::ofstream &Ofile);
 
        void PrintFaces(std::ofstream &Ofile);
 
        void PrintObj(const char *FileName = "chull.obj");
 
        void PrintOut(const char *FileName, tVertex v);
 
        void PrintPoint(tVertex p);
 
        void PrintVertices(std::ofstream &Ofile);
 
        void ReadVertices();
 
        void Reset();
 
        void SetScaleFactor(const int NewScaleFactor)
        {
            ScaleFactor = NewScaleFactor;
        }
 
        void SubVec(int a[3], int b[3], int c[3]);
 
        int Volumei(tFace f, tVertex p);
 
        int VolumeSign(tFace f, tVertex p);
 
    private:
        bool debug;
        bool check;
 
        int ScaleFactor; // Scale factor to be used when converting from floating point to integers and vice versa
};
 
} // namespace AlignmentSubsystem
} // namespace INDI