Classes for computational geometry

1244073422_geometry.zip

1244073422_geometry.zip

General Programming » Algorithms & Recipes » Computational Geometry Intermediate License: The Code Project Open License (CPOL) Classes for computational geometry By Chris Maunder Some classes and utility functions for general computational geometry

VC6, VC7Win2K, WinXP, Visual Studio, MFC, Dev Posted: 26 Dec 2001 Views: 135,231 Bookmarked: 71 times

34 votes for this article. Popularity: 7.11 Rating: 4.64 out of 5 1 2 3 4 5

• Download source files - 14 Kb

Introduction

This article presents two classes and a set of utility functions for computational geometry. C3Point is a 3D counterpart to CPoint and CPolygon encapsulates a set of C3Point's and provides general polygon handling functions. The classes have been mildly optimised for speed. The classes were originally written for use in discretising 2D surfaces into element networks and for calculating properties of the resultant elements. Care must be taken when using some of the functions such as the curvature and area functions to ensure that the results returned by the functions are consistent with your needs and definitions.

The classes make use of a typedef REAL that is either double or float depending on whether USING_DOUBLE or USING_FLOAT has been defined in geometry.h. Obviously using template classes would have been neater, but these classes were developed to get a job done, not to be the epitome of structured programming. A number of conversion functions have been provided:

D2Real(x) (x)             // double => REALF2Real(x) (x)             // float => REALReal2D(x) (x)             // REAL => doubleReal2F(x) ((float)(x))    // REAL => floatInt2Real(x) ((double)(x)) // int => REALReal2Int(x) ((int)(x))    // REAL => intReal2Int(double d0)       // REAL => int (faster than a (cast)).

All the classes and utility functions are provided 'as-is'. I've been meaning to write this class up for a long time and figured it was best to at least post something than nothing at all.

C3Point

C3Point is a 3D counterpart to CPoint. It contains 3 data members x,y and z and a set of functions for calculating properties, scaling, translating and for arithmetic operations.

class C3Point {// Attributespublic:    REAL x,y,z;//Operationspublic:    C3Point() {}                          // constructor    C3Point(double x, double y, double z) // constructor    REAL Length2()                        // length squared    REAL Length()                         // length    void Scale(REAL factor)               // scale by a factor    void Normalise();                     // convert to a unit length    void operator=(C3Point& P)            // assign    C3Point operator-(C3Point P)          // subtract    C3Point operator-()                   // unary -    C3Point operator+(C3Point P)          // add    C3Point operator+=(C3Point P)         // add +=    C3Point operator-=(C3Point P)         // subtract -=    REAL operator*(C3Point P)             // vector dot product    C3Point operator*(REAL f)             // scalar product    C3Point operator/(REAL f)             // scalar div    C3Point operator*=(REAL f)            // scalar mult *=    C3Point operator/=(REAL f)            // scalar div /=    C3Point operator^(C3Point P)          // cross product    BOOL operator==(C3Point& P);          // is equal to?    BOOL operator!=(C3Point& P)           // is not equal to?};#define VECTOR C3Point

CPolygon

CPolygon encapsulates a set of C3Point's and provides general polygon handling functions.

CPolygon();CPolygon(int);                     // Construct with a preallocated number of 
                                   // pointsBOOL Closed();                     // Is the polygon closed?int GetSize()                      // Number of points// is vertex 'index' between start,end inclusive?BOOL InSpan(int start, int end, int index);       // is vertex 'index' between start,end exclusive?BOOL InSpanProper(int start, int end, int index); BOOL PointIn(C3Point P);           // Is point inside polygon?BOOL SetSize(int);                 // Change size of polygonvoid RemoveAll()                   // Empty polygon of all pointsBOOL Trim(int, int);               // Trims polygon down so that points before                                   //   "Start" and after "End" are removed.                                       //   Start and End must be in the range 
                                   //   0..GetSize()-1BOOL Close();                      // Make polygon closedBOOL Add(C3Point);                 // Add point to polygonBOOL SetAt(int nPos, C3Point& p);  // set vertex nPos as point pvoid Delete(int);                  // Delete a vertexBOOL InsertAt(int nPosition, C3Point P); // insert point P at pos nPosition 
                                         //   (0..N-1)void FreeExtra();                  // Free extra memory left over after 
                                   // deletesint PointSeparation(int Point1, int Point2); // Distance (in pts) between 2 
                                             // pointsvoid Rationalise(int nAngle);      // Combines adjacent line segments if the 
                                   // angle between them is less than nAngle
                                   // (degrees).REAL SegmentLength(int,int);       // Length of a segment of the polygonC3Point GetClosestPoint(C3Point p, int *nIndex = NULL);REAL Area();                       // returns polygon areaC3Point Centroid();                // Calculate centroid of polygonBOOL GetAttributes(REAL *pArea,                    C3Point *pCentroid,                    C3Point *pNorm,                   REAL *pSlope,                    REAL *pAspect);BOOL Diagonal(int i, int j);             // Returns TRUE iff (v_i, v_j) is a 
                                         // proper internal or external 
                                         // diagonal of this polygonvirtual void Translate(VECTOR v);        // Translate polygonBOOL Intersected(C3Point& p1, C3Point& p2);     // Does p1-p2 intersect 
                                                // polygon?BOOL IntersectedProp(C3Point& p1, C3Point& p2); // Does p1-p2 intersect 
                                                // polygon properly?BOOL Triangulate(CPolygon*);            // Triangulate: Ear clip triangulationBOOL CPTriangulate(CPolygon*, C3Point); // Central point triangulationBOOL DelauneyTri(CPolygon*);            // Triangulate: Delauney triangulation

// Load polygon from X-Y or X-Y-Z data fileBOOL LoadXY(LPCTSTR Filename, REAL Zdefault = D2Real(0.0));BOOL LoadXY(FILE* fp, REAL Zdefault = D2Real(0.0));BOOL LoadXYZ(LPCTSTR Filename, BOOL bWarn = TRUE);BOOL LoadXYZ(FILE* fp);// Save file either as://    Num Points, elevation, x-y pairs...,// or//    x-y-z triplets...BOOL Save(LPCTSTR Filename, BOOL bAsPoints = FALSE, BOOL bWarn = TRUE);void NaturalSpline(double*& b, double*& c, double*& d); // Natural cubic 
                                                        // splineREAL Curvature(int i);                                  // Curvature at vertex
                                                        //  iREAL Curvature(int nIndex, int nSampleSize);            // Avg curvature at i 
                                                        // over a number of 
                                                        // pointsC3Point& operator[](int index);C3Point& Point(int index);void operator=(CPolygon& P);

General Functions

These functions provide general routines for vectors (C3Points) and polygons.

inline REAL Dot(C3Point V1, C3Point V2)       // dot productinline C3Point Cross(C3Point p1, C3Point p2)  // cross product

C3Point GetClosestPoint2D(C3Point& start, C3Point& end, C3Point& P);REAL   Angle(C3Point, C3Point, C3Point);    // Angle between 2 vectors formed 
                                            // from 3 points (deg)REAL   Angle(VECTOR v, VECTOR u);           // Angle between 2 vectors 
                                            // (degrees)REAL   TriArea2(C3Point, C3Point, C3Point); // Area^2 between 2 vectors formed
                                            // from 3 points REAL   TriArea2(VECTOR u, VECTOR v);        // Area^2 between 2 vectorsBOOL   IntersectProp(C3Point a, C3Point b,  // Returns true iff ab properly                       C3Point c, C3Point d)  //    intersects cd: they share 
                                            //    a point interior to both 
                                            //    segments. The properness 
                                            //    of the intersection is 
                                            //    ensured by using strict 
                                            // leftness.BOOL   Intersect(C3Point a, C3Point b,             // Returns true iff 
                 C3Point c, C3Point d);            // segments ab and cd                                                   // intersect, properly or 
                                                   // improperly.BOOL   Left(C3Point a, C3Point b, C3Point c);      // Returns true iff c is 
                                                   //   strictly to the left                                                    //   of the directed line 
                                                   //   through a to b.BOOL   LeftOn(C3Point a, C3Point b, C3Point c);    // Same as Left, but c may 
                                                   //   be on the line ab.BOOL   Colinear(C3Point a, C3Point b, C3Point c);  // Returns TRUE if a,b,c 
                                                   //   are colinearBOOL   Between(C3Point a, C3Point b, C3Point c);   // Returns TRUE iff (a,b,c)
                                                   //   are collinear and                                                    //   point c lies on the 
                                                   //   closed segement ab.VECTOR Normal(C3Point p1, C3Point p2, C3Point p3); // Computes the normal 
                                                   //   (NOT unit normal) of                                                    //   a triangle, with 
                                                   //   points in Counter                                                    //   Clockwise direction.VECTOR Scale(REAL factor, VECTOR v);               // Scales a vector by a 
                                                   //   factor.

Credits

The algorithms used are based in part from the book Computational Geometry in C by Joseph O'Rourke.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Chris Maunder Member

Chris is the Co-founder, Administrator, Architect, Chief Editor and Shameless Hack who wrote and runs The Code Project. He's been programming since 1988 while pretending to be, in various guises, an astrophysicist, mathematician, physicist, hydrologist, geomorphologist, defence intelligence researcher and then, when all that got a bit rough on the nerves, a web developer. He is a Microsoft Visual C++ MVP both globally and for Canada locally. His programming experience includes C/C++, C#, SQL, MFC, ASP, ASP.NET, and far, far too much FORTRAN. He has worked on PocketPCs, AIX mainframes, Sun workstations, and a CRAY YMP C90 behemoth but finds notebooks take up less desk space. He dodges, he weaves, and he never gets enough sleep. He is kind to small animals. Chris was born and bred in Australia but splits his time between Toronto and Melbourne, depending on the weather. For relaxation he is into road cycling, snowboarding, rock climbing, and storm chasing. Occupation: Founder Company: The Code Project Location: Canada

Discussions and Feedback

41 messages have been posted for this article. Visit http://www.codeproject.com/KB/recipes/geometry.aspx to post and view comments on this article, or click here to get a print view with messages.

PermaLink | Privacy | Terms of Use Last Updated: 26 Dec 2001 Editor: Chris Maunder

Copyright 2001 by Chris Maunder Everything else Copyright © CodeProject, 1999-2009 Web16 | Advertise on the Code Project