计算一个简单的不规则多边形的面积是微不足道的。但是，考虑如下左图所示的自相交多边形 ABCDEF：
如果我们使用上面的链接到公式以多边形顺序遍历点，我们得到的面积为 0。（“顺时针”区域抵消了“逆时针”区域。）
但是，如果我们围绕中心对点进行径向排序并计算面积，我们会在正上方得到多边形 ABEDCF 的错误面积。
如何最好地找到自相交多边形的可见区域？（如果答案需要为每个交叉点创建幻象点，请提供有关如何最好地找到交叉点以及如何以正确顺序遍历它们的详细信息。）
在调查我对这个问题的解决方案的边缘案例时出现了这个问题。
我将“区域”定义为使用“非零”或“偶数”规则填充多边形时可见的像素数量。我会接受其中任何一个的答案，尽管两者都会更好。请注意，我没有明确定义自重叠区域以计算重叠区域两次。
您可以使用此页面中的以下伪代码尝试Bentley–Ottmann
Bentley-Ottmann 算法
Bentley-Ottmann 算法的输入是线段 Li 的集合 OMEGA={Li}，其输出将是交点的集合 LAMBDA={Ij}。该算法被称为“扫描线算法”，因为它的操作可以被可视化为具有另一条线，即“扫描线”SL，扫描集合 OMEGA 并在它通过各个片段 Li 时收集信息。为 SL 的每个位置收集的信息基本上是 OMEGA 中当前与 SL 相交的所有段的有序列表。维护此信息的数据结构通常也称为“扫描线”。此类结构还可以在发现交叉点时检测并输出它们。它发现交叉点的过程是算法及其效率的核心。
要实现扫描逻辑，我们必须首先对 OMEGA 的段进行线性排序，以确定 SL 遇到它们的顺序。也就是说，我们需要对所有段 Li 的端点 {Ei0,Ei1}i=1,n 进行排序，以便我们可以检测 SL 何时开始和停止与 OMEGA 的每个段相交。传统上，端点是通过先增加 x 然后增加 y 坐标值来排序的，但是任何线性顺序都可以（一些作者更喜欢先减少 y 然后增加 x）。在传统的排序中，扫描线是垂直的，在遇到每个线段时从左到右移动，如图所示：
图片扫描线
在算法中的任何一点，扫描线 SL 只与一个端点位于其左侧（或上方）而另一端点位于其右侧的线段相交。SL 数据结构通过以下方式保持这些段的动态列表：（1）在遇到最左边的端点时添加一个段，以及（2）在遇到最右边的端点时删除一个段。此外，SL 以“上下”关系对段列表进行排序。因此，要添加或删除一个段，必须确定其在列表中的位置，这可以通过对列表中的当前段进行最坏情况的 O(log-n) 二进制搜索来完成。此外，除了添加或删除段之外，还有一个事件改变了列表结构；即，每当两个线段相交时，它们在有序列表中的位置必须交换。鉴于这两个部分，
为了组织这一切，该算法维护了一个有序的“事件队列”EQ，其元素导致 SL 段列表发生变化。最初，EQ 设置为所有段端点的扫描排序列表。但是，当段之间的交叉点被发现时，它们也会以与端点使用相同的扫描顺序添加到 EQ 中，但必须测试以避免将重复的交叉点插入事件队列中。上图中的示例显示了这是如何发生的。在事件 2 中，段 S1 和 S2 导致交叉点 I12 被计算并放入队列中。然后，在事件 3 处，段 S3 介于 S1 和 S2 之间并将其分开。接下来，在事件 4 中，S1 和 S3 在扫描线上交换位置，并且 S1 再次靠近 S2，导致再次计算 I12。但是，每个路口只能有一个事件，并且 I12 不能两次入队。因此，当一个交叉点被放入队列时，我们必须在队列中找到它的潜在 x 排序位置，并检查它是否已经存在。由于任何两个线段最多有一个交点，因此用线段的标识符标记一个交点就足以唯一地标识它。由于这一切，事件队列的最大大小 = 2n+k.le.2n+n2，任何插入或删除都可以通过 O(log(2n+n2)) = O(log-n ) 二分查找。
但是，这一切与有效地找到完整的路段交叉点有什么关系呢？好吧，随着段被顺序添加到 SL 段列表中，它们与其他符合条件的段的可能交叉点被确定。当找到一个有效的交集时，它就会被插入到事件队列中。此外，当在扫描期间处理 EQ 上的交集事件时，它会导致 SL 列表的重新排序，并且交集也被添加到输出列表 LAMBDA。最后，当所有事件都处理完毕后，LAMBDA 将包含所有交点的完整有序集。
但是，我们仍然需要描述一个关键细节，即算法的核心；即，如何计算一个有效的交集？显然，只有当它们在某个时间同时出现在扫描线上时，它们才能相交。但这本身不足以使算法高效。重要的观察是两个相交的线段必须是扫描线上的直接上下邻居。因此，只有少数受限情况需要计算可能的交叉点：
当一个段被添加到 SL 列表中时，确定它是否与其上方和下方的邻居相交。
当从 SL 列表中删除一个段时，它之前的上下邻居将作为新邻居聚集在一起。因此，需要确定它们可能的交叉点。
在相交事件中，两个路段在 SL 列表中交换位置，并且必须确定它们与新邻居（每个一个）的相交。这意味着对于 EQ 的任何一个事件（端点或交集）的处理，最多需要进行两个交集确定。
一个细节仍然存在，即从 SL 结构中添加、查找、交换和删除段所需的时间。为此，SL 可以实现为平衡二叉树（例如 AVL、2-3 或红黑树），以保证这些操作最多花费 O(log-n) 时间，因为 n是 SL 列表的最大大小。因此，(2n+k) 个事件中的每一个事件至少有 O(log-n) 个处理要做。将初始排序和事件处理相加，算法的效率为：O(nlog-n)+O((2n+k)log-n)=O((n+k)log-n)。
伪代码：Bentley-Ottmann 算法
将所有这些放在一起，实现 Bentley-Ottmann 算法的顶级逻辑由以下伪代码给出：
Initialize event queue EQ = all segment endpoints;
Sort EQ by increasing x and y;
Initialize sweep line SL to be empty;
Initialize output intersection list IL to be empty;
While (EQ is nonempty) {
Let E = the next event from EQ;
If (E is a left endpoint) {
Let segE = E's segment;
Add segE to SL;
Let segA = the segment Above segE in SL;
Let segB = the segment Below segE in SL;
If (I = Intersect( segE with segA) exists)
Insert I into EQ;
If (I = Intersect( segE with segB) exists)
Insert I into EQ;
}
Else If (E is a right endpoint) {
Let segE = E's segment;
Let segA = the segment Above segE in SL;
Let segB = the segment Below segE in SL;
Delete segE from SL;
If (I = Intersect( segA with segB) exists)
If (I is not in EQ already)
Insert I into EQ;
}
Else { // E is an intersection event
Add E’s intersect point to the output list IL;
Let segE1 above segE2 be E's intersecting segments in SL;
Swap their positions so that segE2 is now above segE1;
Let segA = the segment above segE2 in SL;
Let segB = the segment below segE1 in SL;
If (I = Intersect(segE2 with segA) exists)
If (I is not in EQ already)
Insert I into EQ;
If (I = Intersect(segE1 with segB) exists)
If (I is not in EQ already)
Insert I into EQ;
}
remove E from EQ;
}
return IL;
}
此例程输出所有交点的完整有序列表。
这是我的想法，我假设你的多边形中没有孔，有孔会更复杂，你应该首先从你的多边形中删除孔：
首先找到多边形的凸包，为此您需要找到多边形顶点的凸包。并计算凸包面积。
之后，找到多边形的所有交点。
您应该从凸包中减去不属于原始多边形的额外多边形以找到您的多边形区域，将它们命名为badpoly。badpolys在凸包上总是至少有一个边框，因此该边框不属于您的原始多边形，将它们命名为badborder，通过遍历凸包，您可以找到所有badborders，但是要找到badpoly的其他边框，下一个连接的边框到鉴于相对于badborder具有最小角度的badborder是badpoly的边界之一，您可以继续此操作以查找badpoly的所有边界然后计算它的面积，同样通过重复这种方式你可以计算所有badpolys的面积。
在这种情况下，Bentley-Ottmann 算法并不好。
因为它仅在您想要段之间的交点时才有效。
哈哈，我已经解决了通过将自相交多边形转换为多个多边形来计算自相交多边形的问题。
这是我的代码。
https://github.com/zslzz/intersection_polygon
class SdPolygon(object):
def __init__(self, points=None):
points = self.parafloat(points)
self.points = points
self.current_points = []
self.sd_polygons = []
self.gene_polygon()
from shapely.ops import cascaded_union
self.sd_polygon = cascaded_union(self.sd_polygons)
def parafloat(self, points):
"""
为保证准确，将所有的浮点数转化为整数
:return:
"""
para_point = [(int(x), int(y)) for x, y in points]
return para_point
def gene_polygon(self):
for point in self.points:
self.add_point_to_current(point) # 依次将点加入数组
p0 = Polygon(self.current_points)
self.sd_polygons.append(p0)
def add_point_to_current(self, point):
"""
将该点加入到current_points 中，倒序遍历current_points中的点，如果能围成多边形，则将所围成的点弹出
:param point:
:return:
"""
if len(self.current_points) < 2:
self.current_points.append(point)
return
cross_point_dict = {} # 记录线段与其他点的相交点，{0:P1,6:P2}
l0 = Line(Point(point[0], point[1]), Point(self.current_points[-1][0], self.current_points[-1][1]))
for i in range(0, len(self.current_points) - 1):
line = Line(Point(self.current_points[i][0], self.current_points[i][1]),
Point(self.current_points[i + 1][0], self.current_points[i + 1][1]))
cross_point = self.get_cross_point(l0, line) # 获取相交点
if self.is_in_two_segment(cross_point, l0, line): # 如果相交点在两个线段上
cross_point_dict.update({i: cross_point})
flag_dict = {} # 保存剪下点的信息
cross_points_list = sorted(cross_point_dict.items(), key=lambda item: item[0], reverse=True) # [(3,P),(1,P)]
for cross_point_info in cross_points_list:
cross_i, cross_point = cross_point_info[0], cross_point_info[1]
if flag_dict: # 对应需要剪下多个多边形的情形，
points = self.current_points[cross_i + 1:flag_dict['index'] + 1]
points.append((flag_dict['point'].x, flag_dict['point'].y))
points.append((cross_point.x, cross_point.y))
p = Polygon(points)
self.sd_polygons.append(p)
else:
points = self.current_points[cross_i + 1:]
points.append((cross_point.x, cross_point.y))
p = Polygon(points)
self.sd_polygons.append(p) # 将生成的polygon保存
flag_dict.update(index=cross_i, point=cross_point)
if flag_dict:
point_list = self.current_points[:flag_dict['index'] + 1] # 还未围成多边形的数组
point_list.append((flag_dict['point'].x, flag_dict['point'].y)) # 加上交点
self.current_points = point_list
self.current_points.append(point)
def is_in_segment(self, point, point1, point2):
"""
交点是否在线段上
:param point:(x,y)
:param point1:[(x1,y1),(x2,y2)]
:param point2:
:return:
"""
if point1.x > point2.x:
minx = point2.x
maxx = point1.x
else:
minx = point1.x
maxx = point2.x
if point1.y > point2.y:
miny = point2.y
maxy = point1.y
else:
miny = point1.y
maxy = point2.y
if minx <= point.x <= maxx and miny <= point.y <= maxy:
return True
return False
def is_in_two_segment(self, point, l1, l2):
"""
点 是否在两段 线段中间
:param point:
:param l1:
:param l2:
:return:
"""
def is_same_point(p1, p2):
"""
判断点是否相同
:param p1:
:param p2:
:return:
"""
if abs(p1.x - p2.x) < 0.1 and abs(p1.y - p2.y) < 0.1:
return True
return False
if self.is_in_segment(point, l1.p1, l1.p2) and self.is_in_segment(point, l2.p1, l2.p2):
if (is_same_point(point, l1.p1) or is_same_point(point, l1.p2)) and (
is_same_point(point, l2.p1) or is_same_point(point, l2.p2)):
# 判断是否在两条线段的端点上
return False
return True
return False
def get_line_para(self, line):
"""
规整line
:param line:
:return:
"""
line.a = line.p1.y - line.p2.y
line.b = line.p2.x - line.p1.x
line.c = line.p1.x * line.p2.y - line.p2.x * line.p1.y
def get_cross_point(self, l1, l2):
"""
得到交点
:param l1: 直线Line
:param l2:
:return: 交点坐标Point
"""
self.get_line_para(l1)
self.get_line_para(l2)
d = l1.a * l2.b - l2.a * l1.b
p = Point()
if d == 0:
return p
p.x = ((l1.b * l2.c - l2.b * l1.c) // d)
p.y = ((l1.c * l2.a - l2.c * l1.a) // d)
return p