📄 ptloc.h
字号:
/////////////////////////////////////////////////////////////////////////////
// //
// ptloc.h Header file for implementation of efficient point location //
// routines. //
// //
// by Si hang March, 2001. //
// stsc_sh@sina.com //
// //
// This file with it's couple file ptloc.cpp were specially written for //
// the FEMM program(http://groups.yahoo.com/group/femm/) femmview to //
// provide a fast point location function to improve the Line Integral //
// calculation speed when the mesh size is big. //
// //
// The fast point location algorithm is due to Ernst P. Mucke, Isaac, //
// Saias, Binhai Zhu. "Fast Randomized Point Location Without //
// Preprocessing in Two- and Three-dimension Delaunay Triangulations", //
// In Proceedings of the 12th Annual Symposium on Computational //
// Geometry,1996. //
// //
// The data structure is due to Jonathan Richard Shewchuk, "Triangle: //
// Engineering a 2D Quality Mesh Generator and Delaunay Triangulator", //
// First Workshop on Applied Computational Geometry, ACM, May 1996. //
// And the data structure's manipulation primitives are described by //
// Leonidas J. Guibas and Jorge Stolfi, "Primitives for the Manipulation //
// of General Subdivisions and the Computation of Voronoi Diagrams," //
// ACM Transactions on Graphics 4(2):74-123, April 1985. //
// //
// This codes not used exact computation of the signs of determinants, //
// which is less robust. But it can change to robust version easily if //
// you need. Here I only used Orient2D() test. There are many share- //
// wares provide exact computation of the signs of determinants in the //
// web. Inculde the declarations in this file, then in ptloc.cpp replace //
// the Orient2D() functions with your function name. A very good share- //
// ware is due to Jonathan Richard Shewchuk, "Adaptive Precision //
// Floating-Point Arithmetic and Fast Robust Geometric Predicates," //
// Technical Report CMU-CS-96-140, School of Computer Science, Carnegie //
// Mellon University, Pittsburgh, Pennsylvania, May 1996. Which can //
// download freely at: //
// http://www.cs.cmu.edu/afs/cs/project/quake/public/code/predicates.c //
// //
// The origin algorithm of Mucke, Saias and Zhu is designed for convex //
// triangulations, and will not generally work if there exist the holes //
// and concavities. My implementation of this algorithm didn't have //
// this constraints. I assume all the boundaries in mesh model must //
// be closed. At least all models in FEMM must satisfy this condition. //
// Under this assumpation, my implementation can handle the holes //
// and concavities cases. For more detail, see the codes in ptloc.cpp. //
// There are two functions for this purpose: BuildOuterBoundaryLink() //
// and WalkThroughBoundary(). //
// //
// Anyway, I don't think my implementation is perfect and there maybe //
// still have bugs. Any suggestion and any bug please let me know. //
// stsc_sh@sina.com. Thank you. //
// //
/////////////////////////////////////////////////////////////////////////////
// Labels that signify the result of point location. The result of a
// search indicates that the point falls in the interior of a triangle,
// on an edge, on a vertex, or outside the mesh.
// enum LocateResult { eOnVertex, eOnEdge, eInTriangle, eOutSide };
/////////////////////////////////////////////////////////////////////////////
// //
// class TriEdge //
// //
// An object of TriEdge is n oriented triangle: includes a index to a //
// triangle and its orientation. The orientation denotes an edge of //
// the triangle. Hence, there are three possible orientations. By //
// convention, each edge is always directed to point counterclockwise //
// about the corresponding triangle. //
// //
// TriEdge include manipulation primitives. Each triangle contains three //
// index to other triangles, with orientations. To save memory, I keep //
// both pieces of information in single integer, which allows us to //
// handle all refernces to triangle and orientation pairs as integers: //
// <tri, ori> = 4 * tri + ori. Note how this conversion formula enables //
// the usage of fast shift operationa instead of multiplication. The //
// highest bit of the integer(sign bits) can be used to encode boundary //
// markers. //
// //
/////////////////////////////////////////////////////////////////////////////
class TriEdge {
public:
int ele;
int ori; // Ranges from 0 to 2.
public:
TriEdge();
TriEdge(int, int);
TriEdge(TriEdge&);
TriEdge& operator=(const TriEdge&);
BOOL operator==(TriEdge&);
BOOL operator!=(TriEdge&);
TriEdge sym();
TriEdge lnext();
TriEdge lprev();
TriEdge onext();
TriEdge oprev();
TriEdge dnext();
TriEdge dprev();
TriEdge rnext();
TriEdge rprev();
TriEdge& symself();
TriEdge& lnextself();
TriEdge& lprevself();
TriEdge& onextself();
TriEdge& oprevself();
TriEdge& dnextself();
TriEdge& dprevself();
TriEdge& rnextself();
TriEdge& rprevself();
CMeshNode* org();
CMeshNode* dest();
CMeshNode* apex();
BOOL symexist();
void bondboundary(TriEdge&);
TriEdge nextboundary();
TriEdge& nextboundaryself();
};
///////////////////////////////////////////////////////////////////////////////
// //
// BuildElemMap() Preprocess for Point Location Routines. //
// //
// This function must call first, and only need call once. It build a map //
// for current model's mesh data and several boundary edge links for current //
// modal's boundary. //
// //
///////////////////////////////////////////////////////////////////////////////
void BuildElemMap(CArray< CMeshNode, CMeshNode&> *pMeshNodes,
CArray< CElement, CElement&> *pMeshElems,
int *pNumList, int **ppConList, void *pd);
///////////////////////////////////////////////////////////////////////////////
// //
// Locate() Find a triangle or edge containing a given point. //
// //
// Searching begins from one of: the input `searchtri', a recently //
// encountered triangle `recenttri', or from a triangle chosen from a //
// random sample. The choice is made by determining which triangle's //
// origin is closest to the point we are searcing for. //
// //
// Details on the random sampling method can be found in the Mucke, Saias, //
// and Zhu paper cited in the header of this code. //
// //
// On completion, `searchtri' is a triangle that contains `searchpoint'. //
// //
// Returns eOnVertex if the point lies on an existing vertex. `searchtri' //
// is a handle whose origin is the existing vertex. //
// //
// Returns eOnEdge if the point lies on a mesh edge. `searchtri' is a //
// handle whose primary edge is the edge on which the point lies. //
// //
// Returns eInTriangleif the point lies strictly within a triangle. //
// `searchtri' is a handle on the triangle that contains the point. //
// //
// Returns eOutSide if the point lies outside the mesh. `searchtri' is a //
// handle whose primary edge the point is to the right of. This might //
// occur when the circumcenter of a triangle falls just slightly outside //
// the mesh due to floating-point roundoff error. It also occurs when //
// seeking a hole or region point that a foolish user has placed outside //
// the mesh. //
// //
///////////////////////////////////////////////////////////////////////////////
enum LocateResult Locate(CMeshNode& searchpoint, TriEdge* searchtri, void *pd);
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -