假设2d空间中的一系列点不是自相交的,那么确定结果多边形面积的有效方法是什么？

作为旁注,这不是作业,我不是在寻找代码.我正在寻找一个可以用来实现我自己的方法的描述.我有关于从点列表中拉出一系列三角形的想法,但我知道有一些关于凸多边形和凹多边形的边缘情况我可能无法捕捉到.

给定一组在平面上的点的,α-形状的概念,对于给定的正数α,通过找到Delaunay三角剖分并删除对于其中至少一个边缘的长度超过了阿尔法任何三角形定义.这是使用d3的示例:

http://bl.ocks.org/gka/1552725

问题是,当有数千个点时,简单地绘制所有内部三角形对于交互式可视化来说太慢了,所以我想找到边界多边形.这不是那么简单,因为从这个例子可以看出,有时可能会有两个这样的多边形.

作为简化,假设已经执行了一些聚类,因此保证每个三角测量的唯一边界多边形.找到这个边界多边形的最佳方法是什么？特别是,边缘必须一致地排序,它必须支持"洞"的可能性(想想圆环或圆环形状 - 这在GeoJSON中是可表达的).

建立

给定凸包内的一些节点集,假设该域包含一个或多个凹面区域:

其中蓝点是点,黑线表示域.假设点被保持为points长度的2D数组n,其中n是点对的数量.

然后让我们使用类似scipy.spatial的Delaunay方法对点进行三角测量:

如您所见,人们可能会遇到穿过域的三角形的创建.

题

删除任何跨越域外的三角形的好算法方法是什么？理想但不一定,单面边缘仍然保留域形状(即,没有去除三角形的主要间隙).

由于我的问题似乎继续得到大量的活动,我想跟进我目前正在使用的应用程序.

假设您已定义边界,则可以使用光线投射算法来确定多边形是否在域内.

去做这个:

1. 取每个多边形的质心为C_i = (x_i,y_i).
2. 然后,想象一条线L = [C_i,(+inf,y_i)]:也就是说,一条横跨东部超过域末端的线.
3. 对于边界s_i中的每个边界段S,检查交叉点L.如果是,请向内部计数器添加+1 intersection_count; 否则,什么都不添加.

4. 后之间的所有交叉点的数量L和s_i for i=1..N计算:

   if intersection_count % 2 == 0:
       return True # triangle outside convex hull
   else:
       return False # triangle inside convex hull
   

   Run Code Online (Sandbox Code Playgroud)

如果没有明确定义边界,我发现将形状"映射"到布尔数组并使用邻居跟踪算法来定义它是有帮助的.请注意,此方法假设一个实体域,您需要对其中包含"漏洞"的域使用更复杂的算法.

您可能已经注意到,在较新版本的matlab中,边界函数(计算一组2d或3d点的边界)已得到改进.

现在可以给函数一个名为'shrink factor'的参数.如果收缩因子为0,则跟踪的边界是传统的凸包.当收缩参数更大时,边界更加收缩.如果未指定任何值,则缩小系数的默认值为0.5.

所以,我理解它的用途和它的作用(实际上我已经在项目中使用过该函数),但我不知道它是如何工作的.这种收缩系数的几何原理是什么？

谢谢!