多边形区域内储层建模结点三角剖分算法研究

结合储层建模结点数据的特点 ,提出了一种对多边形区域内建模结点数据进行快速三角剖分的算法 .如果区域边界边与剖分三角形可能相交 ,根据边界边顶点与剖分三角形确定的矩形区域的关系 ,对于不同情况 ,通过计算矢量叉积 ,或最坏情况下通过计算交点 ,来确定边界边与剖分三角形是否真正相交 .同时 ,讨论了在剖分过程中 ,对边界边链表进行实时更新 ,逐步减少边界边的思路 .虽然整个算法的时间复杂度最坏情况为 O( 3× m×n) ( m为多边形区域内结点形成的三角形个数 ,n为边界边个数 ) ,但在实际应用中 ,对大批量的储层建模结点数据进行三角剖分时 ,文中提出的算法具有比较高的处理效率

Study on Triangulation Algorithm of Stochastic Reservoir Modeling Data in Polygonal Domain

A fast algorithm is put forward that is used to triangulate stochastic reservoir modeling data in a polygonal domain. This algorithm is based on the characteristic of modeling data. If a triangle has the possibility to intersect domain edges, there are two methods to determine whether they intersect really. One is to take the vector cross product,and the other is to compute the intersection point under the worst condition. This paper also presents a method refreshing the edge linker by deleting the edges in triangulating process in real time. Although the theoretical time complexity of the method is O(3×m×n) in the worst situation ( m is the number of triangles that are decided by the nodes in the polygonal domain, and n is the number of the edges of the polygonal domain), this algorithm has still a good efficiency for a large number of modeling data in practice.