计算一个简单的不规则多边形的面积很容易。但是，考虑左侧所示的自交叉多边形ABCDEF：
如果我们按照多边形顺序使用上面链接的公式遍历点，我们得到0的面积。（“顺时针”面积抵消了“逆时针”面积。）
然而，如果我们根据中心径向排序点并计算面积，则在上图右侧得到多边形ABEDCF的错误面积。
如何最好地找到自交叉多边形的可见面积？（如果答案需要为每个交点创建幻影点，请提供有关如何最佳找到交点以及如何按正确顺序遍历它们的详细信息。）
当调查解决此问题的边缘情况时，出现了这个问题。
我将“面积”定义为使用“非零”或“奇偶”规则填充多边形时可见的像素数量。我将接受任何一种答案，但两种都更好。请注意，我明确不为自重叠定义面积，以将重叠区域计算两次。
然而，还有一个关键细节，算法的核心，我们仍然需要描述;即如何计算有效的交点？显然，只有在两个线段同时出现在扫描线上时，它们才能相交。但这本身并不足以使算法高效。重要的观察是，两个相交的线段必须是扫描线上的相邻线段。因此，只有几种受限情况需要计算可能的交点：
当线段添加到SL列表中时，请确定它是否与其上下邻居相交。
当从SL列表中删除线段时，它的上下邻居被合并为新邻居。因此，需要确定它们的可能交点。
在交叉事件中，SL列表中的两个线段会交换位置，并且必须确定它们与新邻居（每个线段有一个新邻居）的交点。这意味着对于任何一个EQ事件（端点或交叉点）的处理，最多需要进行两次交点确定。
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
0是正确答案 :) - ypercubeᵀᴹ