检查点周围是否有封闭区域

Question

我有一个由圆心坐标和半径给出的圆列表，还有一些由坐标给出的点。需要检查圆是否在给定点周围形成闭合区域该点不在任何圆内<例如，这里我们看到点周围的闭合区域

这里是未封闭区域：

我过滤圆（不是最好的方法-如何做得更好？），但我不知道如何建立成对相交

def check_inside(c1, r1, c2, r2):
    if r1 < r2:
        c1, c2 = c2, c1
        r1, r2 = r2, r1
    if r1 > (((c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2) ** 0.5 + r2): 
        return c2, r2
    else:
        return -1

    
def check_intersection(c1, r1, c2, r2):
    if (r1 + r2 >= ((c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2) ** 0.5) and check_inside(c1, r1, c2, r2) == -1:
        return True
    return False
    

if __name__ == "__main__":
    
    circles = []
    circles_s = input()
    circles_s = re.findall(r'\([\d.,-? ]*\d+\)', circles_s)
    for circle in circles_s:
        x, y, r = circle[1:-1].split(', ')
        circles.append(((float(x), float(y)), float(r)))
    point = tuple([float(x) for x in input().split(', ')])
    
    circles_intersected = set()
    for i in range(len(circles)):
        for j in range(len(circles)):
            if circles[i] != circles[j] and check_intersection(*circles[i], *circles[j]):
                circles_intersected.add(circles[i])
                circles_intersected.add(circles[j])
                
    circles_intersected = list(circles_intersected)
    circle_final = circles_intersected.copy()
    for i in range(len(circles_intersected)):
        for j in range(len(circles_intersected)):
            if circles_intersected[i] != circles_intersected[j]:
                res = check_inside(*circles_intersected[i], *circles_intersected[j])
                if res != -1:
                    if circles_intersected[i][0] == res[0] and circles_intersected[i][1] == res[1] and\
                    circles_intersected[i] in circle_final:
                        circle_final.remove(circles_intersected[i])
                    elif circles_intersected[j][0] == res[0] and circles_intersected[j][1] == res[1] and\
                    circles_intersected[j] in circle_final:
                        circle_final.remove(circles_intersected[j])

Answer 1

使用以下方法：

1. 通过O(n)检查点是否在任何圆内，如果存在圆，则该点被捕获
2. 引理：如果点被外圆捕获，那么如果连接该圆的中心，则点被新创建的多边形捕获

所以只需清除所有圆，然后连接两个圆心，如果它们对应的圆是连接的或ra + rb >= |a-b|

现在你们的问题是找出一个给定的点是否被页面上的一些行所捕获。 为此，请执行以下操作：

1. 找到由直线创建的所有多边形，您可以创建一个图形并使用O(n^2)查找循环
2. 对于所有找到的多边形，使用ray casting算法