Check if there is a closed area around the point

Question

I have a list of circles given by center coordinates and radius, and some point given by coordinates. It is required to check whether the circles form a closed area around a given point. The point does not lie inside any of the circles. For example, here we see the closed area around point

and here - unclosed area:

I filtered circles (not the best way - how to do better?), but I don't know, how to establish pairwise intersection.

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])

Seems like a fairly hard problem in that an unclosed area might correspond to a very serpentine path through a maze of circles — John Coleman, Jan 10 '21 at 14:01
@mkrieger1 Algorithmic questions *can* be appropriate questions on Stack Overflow. — John Coleman, Jan 10 '21 at 14:02
Maybe there are python libraries that can help solve this problem? it is necessary to distinguish case 1 from case 2, knowing only the coordinates and radii of the circles, the coordinates of the point. — Любовь Пономарева, Jan 10 '21 at 14:07
Can you do a [flood fill](https://en.wikipedia.org/wiki/Flood_fill) and see if you reach the edge of the image? — ChrisGPT was on strike, Jan 10 '21 at 14:12
@ЛюбовьПономарева, note that requests for libraries are explicitly off-topic as defined in the [help/on-topic]. — ChrisGPT was on strike, Jan 10 '21 at 14:12

score 8 · Accepted Answer · edited Jan 11 '21 at 04:07

8

Use the following approach:

Check if point is inside any of circles by O(n), if there was a circle then the point is trapped.
Lemma: if point is trapped by outer circles, then if you connect the center of that circles, then the point is trapped by the new created polygon

So just clear all circles, and then connect two circle centers if their corresponding circles are connected or ra + rb >= |a-b|

Now your question is to find out, if a given point is trapped by some lines on page or not. To achieve this do the following:

find all polygons created by the lines, you can create a graph and find the loops with O(n^2)
for all the found polygons use the ray casting algorithm

edited Jan 11 '21 at 04:07

fdermishin

3,519
3
24
45

answered Jan 10 '21 at 14:28

Ehsan Gerayli

495
2
9

Nice (+1). The key point is your lemma. In some ways, lines and polygons are the only things deeply understood in computational geometry, so if your problem doesn't involve such things -- find a way to introduce them. – John Coleman Jan 10 '21 at 14:41
You could use collitions algorithm to know if there is a gap or not between circles. – Avatazjoe Jan 10 '21 at 14:43
@JohnColeman I need to check if the circles intersect in pairs around a point, what algorithm can be used to establish a pairwise intersection? – Любовь Пономарева Jan 11 '21 at 11:54
@EhsanGerayli, How to check if lines form closed polygon? – Любовь Пономарева Jan 12 '21 at 16:23

Check if there is a closed area around the point

1 Answers1