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.