## 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)
F2Real(x) (x)
Real2D(x) (x)
Real2F(x) ((float)(x))
Int2Real(x) ((double)(x))
Real2Int(x) ((int)(x))
Real2Int(double d0)

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 {
public:
REAL x,y,z;
public:
C3Point() {}
C3Point(double x, double y, double z)
REAL Length2()
REAL Length()
void Scale(REAL factor)
void Normalise();
void operator=(C3Point& P)
C3Point operator-(C3Point P)
C3Point operator-()
C3Point operator+(C3Point P)
C3Point operator+=(C3Point P)
C3Point operator-=(C3Point P)
REAL operator*(C3Point P)
C3Point operator*(REAL f)
C3Point operator/(REAL f)
C3Point operator*=(REAL f)
C3Point operator/=(REAL f)
C3Point operator^(C3Point P)
BOOL operator==(C3Point& P);
BOOL operator!=(C3Point& P)
};
#define VECTOR C3Point

## CPolygon

`CPolygon`

encapsulates a set of `C3Point`

's and provides general polygon handling functions.

CPolygon();
CPolygon(int);
BOOL Closed();
int GetSize()
BOOL InSpan(int start, int end, int index);
BOOL InSpanProper(int start, int end, int index);
BOOL PointIn(C3Point P);
BOOL SetSize(int);
void RemoveAll()
BOOL Trim(int, int);
BOOL Close();
BOOL Add(C3Point);
BOOL SetAt(int nPos, C3Point& p);
void Delete(int);
BOOL InsertAt(int nPosition, C3Point P);
void FreeExtra();
int PointSeparation(int Point1, int Point2);
void Rationalise(int nAngle);
REAL SegmentLength(int,int);
C3Point GetClosestPoint(C3Point p, int *nIndex = NULL);
REAL Area();
C3Point Centroid();
BOOL GetAttributes(REAL *pArea,
C3Point *pCentroid,
C3Point *pNorm,
REAL *pSlope,
REAL *pAspect);
BOOL Diagonal(int i, int j);
virtual void Translate(VECTOR v);
BOOL Intersected(C3Point& p1, C3Point& p2);
BOOL IntersectedProp(C3Point& p1, C3Point& p2);
BOOL Triangulate(CPolygon*);
BOOL CPTriangulate(CPolygon*, C3Point);
BOOL DelauneyTri(CPolygon*);

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);
BOOL LoadXYZ(FILE* fp);
BOOL Save(LPCTSTR Filename, BOOL bAsPoints = FALSE, BOOL bWarn = TRUE);
void NaturalSpline(double*& b, double*& c, double*& d);
REAL Curvature(int i);
REAL Curvature(int nIndex, int nSampleSize);
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);
REAL Angle(VECTOR v, VECTOR u);
REAL TriArea2(C3Point, C3Point, C3Point);
REAL TriArea2(VECTOR u, VECTOR v);
BOOL IntersectProp(C3Point a, C3Point b,
C3Point c, C3Point d)
BOOL Intersect(C3Point a, C3Point b,
C3Point c, C3Point d);
BOOL Left(C3Point a, C3Point b, C3Point c);
BOOL LeftOn(C3Point a, C3Point b, C3Point c);
BOOL Colinear(C3Point a, C3Point b, C3Point c);
BOOL Between(C3Point a, C3Point b, C3Point c);
VECTOR Normal(C3Point p1, C3Point p2, C3Point p3);
VECTOR Scale(REAL factor, VECTOR v);

## Credits

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

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.