计算几何类
5.00/5 (23投票s)
用于通用计算几何的一些类和实用函数。
引言
本文档介绍了用于计算几何的两个类和一个实用函数集。C3Point 是 CPoint 的三维对应物，而 CPolygon 封装了一组 C3Point 并提供了通用的多边形处理函数。这些类经过轻微优化以提高速度。这些类最初是为将二维表面离散化为元素网络以及计算结果元素属性而编写的。在使用某些函数（如曲率和面积函数）时，必须小心，以确保函数返回的结果与您的需求和定义一致。
这些类使用一个 typedef REAL，具体是 double 或 float，具体取决于 geometry.h 中是否定义了 USING_DOUBLE 或 USING_FLOAT。 显而易见，使用模板类会更简洁，但这些类是为完成一项工作而开发的，而不是为了成为结构化编程的典范。 提供了一些转换函数。
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)).
所有类和实用函数均按“原样”提供。我一直想编写这个类，并认为至少发布一些内容总比什么都不发好。
C3Point
C3Point 是 CPoint 的三维对应物。它包含 3 个数据成员 x、y 和 z，以及用于计算属性、缩放、平移和进行算术运算的一组函数。
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) // 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 封装了一组 C3Point 并提供了通用的多边形处理函数。
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 Add(C3Point); // Add point to polygon
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);
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 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);
通用函数
这些函数为向量（C3Point）和多边形提供通用例程。
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.
致谢
所使用的算法部分基于 Joseph O'Rourke 的著作 C 语言的计算几何。