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

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

使用以下方法：

通过O(n)检查点是否在任何圆圈内，如果有圆圈则点被捕获。
引理：如果点被外圆包围，那么如果你连接那个圆的中心，那么这个点就会被新创建的多边形包围

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

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

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

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

Check if there is a closed area around the point

python

algorithm

math

geometry