# Classes for computational geometry

, 26 Dec 2001 CPOL
 Rate this:
Some classes and utility functions for general computational geometry

## 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 => REAL
F2Real(x) (x)             // float => REAL
Real2D(x) (x)             // REAL => double
Real2F(x) ((float)(x))    // REAL => float
Int2Real(x) ((double)(x)) // int => REAL
Real2Int(x) ((int)(x))    // REAL => int
Real2Int(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 {
// Attributes
public:
REAL x,y,z;

//Operations
public:
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)         // 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 points

BOOL 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 polygon
void RemoveAll()                   // Empty polygon of all points
BOOL 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()-1
BOOL Close();                      // Make polygon closed
BOOL SetAt(int nPos, C3Point& p);  // set vertex nPos as point p
void Delete(int);                  // Delete a vertex
BOOL InsertAt(int nPosition, C3Point P); // insert point P at pos nPosition (0..N-1)

void FreeExtra();                  // Free extra memory left over after deletes

int PointSeparation(int Point1, int Point2); // Distance (in pts) between 2 points
void 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 polygon
C3Point GetClosestPoint(C3Point p, int *nIndex = NULL);
REAL Area();                       // returns polygon area
C3Point Centroid();                // Calculate centroid of polygon
BOOL 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 polygon
virtual void Translate(VECTOR v);        // Translate polygon
BOOL 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 triangulation
BOOL CPTriangulate(CPolygon*, C3Point); // Central point triangulation
BOOL DelauneyTri(CPolygon*);            // Triangulate: Delauney triangulation```
```// Load polygon from X-Y or X-Y-Z data file
BOOL LoadXY(LPCTSTR Filename, REAL Zdefault = D2Real(0.0));
BOOL LoadXY(FILE* fp, REAL Zdefault = D2Real(0.0));
BOOL LoadXYZ(LPCTSTR Filename, BOOL bWarn = TRUE);

// 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 spline
REAL Curvature(int i);                                  // Curvature at vertex i
REAL Curvature(int nIndex, int nSampleSize);            // Avg curvature at i over
// a number of points

C3Point& operator[](int index);
C3Point& Point(int index);
void operator=(CPolygon& P);```

## General Functions

These functions provide general routines for vectors (`C3Point`s) and polygons.

```inline REAL Dot(C3Point V1, C3Point V2)       // dot product
inline 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 vectors
BOOL   IntersectProp(C3Point a, C3Point b,  // Returns true iff ab properly intersects cd:
C3Point c, C3Point d)  //    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 segments ab and cd
C3Point c, C3Point d);            // 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 colinear
BOOL   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.

## Share

Founder CodeProject
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.

 First Prev Next
 VS2005 andrewtruckle 29-Feb-08 0:12
 CPolygon::Centroid problem andrewtruckle 9-Aug-07 23:07
 Re: CPolygon::Centroid problem Chris Maunder 10-Aug-07 3:58
 Re: CPolygon::Centroid problem andrewtruckle 13-Aug-07 0:39
 Re: CPolygon::Centroid problem Chris Maunder 13-Aug-07 5:34
 Re: CPolygon::Centroid problem andrewtruckle 13-Aug-07 9:28
 Re: CPolygon::Centroid problem Andrew Phillips 29-Sep-08 4:00
 Re: CPolygon::Centroid problem andrewtruckle 29-Sep-08 4:03
 Re: CPolygon::Centroid problem Chris Maunder 29-Sep-08 4:56
 Re: CPolygon::Centroid problem andrewtruckle 29-Sep-08 6:04
 Thanks so much! Frederic Sivignon 29-Jan-07 23:59
 Natural Spline Zodiacon 14-Jul-05 6:35
 Intersected only for 2D... Karl Runmo 10-Dec-04 4:38
 coordinate of intersection of line segments? Richard Males 30-Aug-04 12:30
 Subtract CPolygon from CPolygon d00_ape 20-Jul-04 0:40
 Where is the colinear method? hgjgj121z 20-Feb-04 13:46
 Great Job! Frank Berger 23-Jan-04 16:58
 Non-MFC? TCMaster 26-Aug-03 8:53
 Re: Non-MFC? John M. Drescher 26-Aug-03 9:59
 Re: Non-MFC? TCMaster 26-Aug-03 11:07
 Re: Non-MFC? Antony M Kancidrowski 28-Aug-03 3:01
 Re: Non-MFC? =[ Abin ]= 7-Sep-03 3:38
 Delaunay triangulation zhangxinbin 6-Aug-03 18:38
 Delaunay Triangulation kmoaveni 3-Jun-03 6:36
 Re: Delaunay Triangulation ysahn 19-Dec-03 14:10
 Re: Delaunay Triangulation Anonymous 8-Apr-04 23:33
 Re: ysahn Anonymous 12-Apr-04 0:07
 Re: ysahn saurgarg 15-Oct-04 16:58
 Sample or demo Thierry Lebrun 18-Nov-02 0:53
 Re: Sample or demo azhong12345 29-Jun-07 4:53
 please give me a sample to get norm and Curvature of each POINT! thanks a lot!
 Error in DelauneyTri hyung oh kim 30-May-02 18:55
 Post a demo bryce 21-Apr-02 19:42
 Sweet! Kastellanos Nikos 31-Jan-02 22:53
 Re: Sweet! kilowatt 21-Apr-02 19:24
 Can anyone show PointIn example? werewrrwewerqrweqrqwe 29-Jan-02 8:17
 Re: Can anyone show PointIn example? Graham Shanks 5-Jun-02 5:36
 It just goes to show... Andy Metcalfe 29-Dec-01 0:36
 Re: It just goes to show... Chris Maunder 31-Dec-01 15:57
 Re: It just goes to show... Andy Metcalfe 8-Jan-02 11:30
 Also take a look at vecmath CoolDev 27-Dec-01 8:33
 Last Visit: 31-Dec-99 19:00     Last Update: 21-Apr-15 2:03 Refresh 1