How to draw overlapping 2D circles and adjust shapes based on collision?

Question

I have an array of coordinates that I want to draw as circles on a single canvas. Something like this:

{'pos': {'x': '0.1303', 'y': '1.1152'}, 'size': 0.7}
{'pos': {'x': '1.0542', 'y': '0.7325'}, 'size': 0.1}
{'pos': {'x': '1.4368', 'y': '-0.1913'}, 'size': 0.1}
{'pos': {'x': '1.0542', 'y': '-1.1152'}, 'size': 0.7}
{'pos': {'x': '0.1303', 'y': '-1.4979'}, 'size': 0.7}
{'pos': {'x': '-0.7936', 'y': '-1.1152'}, 'size': 0.5}
{'pos': {'x': '-1.1763', 'y': '-0.1913'}, 'size': 0.1}
{'pos': {'x': '-0.7936', 'y': '0.7325'}, 'size': 0.3}
{'pos': {'x': '0.0827', 'y': '0.8454'}, 'size': 0.5}

But if any circle overlaps with another then I want to adjust both of their shapes, so that both circles will have a straight edge where it touches its neighbour.

For example, if I just use matplotlib to plot my circles then it might look something like this:

But what I want to happen is for these circles to have flat edges where they collide with their neighbour:

How can I dynamically change the shape of my circles in my script to make this happen, or is there a Python package that I don't know about which can help?

Answer 1

I don't know about something that will do this automatically, but you could look for intersections and manually make your circles.

Two circles intersect if the distance between their centers is less than the sum of their radii. The coordinates of the intersection points can be found using this answer from Math.SE or better yet this one from right here!

Let's implement this in a Circle class. I've broken it down into pieces and added type hints, docstrings and comments to make it easier to understand the class, because it's quite a large chunk of code:

Note: A previous version of this answer only supported two circles. To support intersecting multiple circles, I've used the intervaltree package to keep track of which intervals on the circle are cut off.

Imports:

from typing import Iterable, Tuple
import numpy as np
from matplotlib import pyplot as plt
import intervaltree

These methods create / initiate objects of the class

class Circle:

    @classmethod
    def from_dict(cls, cdict: dict) -> "Circle":
        """Create a Circle object from the dictionary structure specified in OP"""
        c = [float(f) for f in cdict["pos"].values()]
        r = cdict["size"]
        return cls(c, r)

    def __init__(self, center: Iterable, radius: float):
        self.center = np.asarray(center)
        self.radius = radius
        self._splits = intervaltree.IntervalTree()

The intersect_with method takes another Circle object and returns either

1. None, if no intersections are found or both circles are identical
2. A 1x2 numpy array containing the point of tangency if both circles are tangential
3. A 2x2 numpy array containing the points of intersection if both circles intersect

# 1. and 2. are easy to identify based on the distance between the two centers and the sum of the circles' radii.

For #3, the logic comes straight from Circle-circle intersection points

    def intersect_with(self, circ2: "Circle") -> np.ndarray:
        """Find the points of intersection between this circle and another

        Args:
            circ2 (Circle): The other circle

        Returns:
            np.ndarray: A Nx2 array containing the N points of intersection, or None if no intersection
        """
        # Gen center to center vector
        c1_to_c2 = circ2.center - self.center
        # Magnitude of that vector is distance between centers
        rdist = np.linalg.norm(c1_to_c2)
        # Sum of radii
        rsum = self.radius + circ2.radius

        # Check if condition 1: no solution
        if rdist == 0 or rdist > rsum: 
            return None
        # Check if condition 2: one solution
        elif rdist == rsum:
            return np.array([self.center + self.radius * c1_to_c2 / rdist])
        else:
            # Condition 3: two solutions
            d=rdist
            r0 = self.radius
            r1 = circ2.radius
            x0, y0 = self.center
            x1, y1 = circ2.center
            
            a=(r0**2-r1**2+d**2)/(2*d)
            h=np.sqrt(r0**2-a**2)
            
            x2=x0+a*(x1-x0)/d   
            y2=y0+a*(y1-y0)/d   
            
            x3=x2+h*(y1-y0)/d
            y3=y2-h*(x1-x0)/d
            
            x4=x2-h*(y1-y0)/d
            y4=y2+h*(x1-x0)/d
            
            return np.array([[x3, y3], [x4, y4]])

After calculating the intersection points, we need to be able to decide which part of the curve to discard, i.e. what are the start and end points of the counterclockwise arc. This function does that job. The idea is that we want to discard the portion of the arc which intersects with the vector joining the two centers. That is, we want the start point of our circle to be counterclockwise of the center-center vector, and the end point to be clockwise of it. So we check the cross product of those vectors. If it's negative, then we invert the start and end points:

    def arrange_intersection_pts(self, circ2: "Circle", ipts: np.ndarray) -> Tuple[float]:
        vec_from_center = ipts - self.center
        center_to_center = circ2.center - self.center
        ang_to_center = np.arctan2(vec_from_center[:, 1], vec_from_center[:, 0])
        if np.cross(center_to_center, vec_from_center[0, :]) > 0:
            return ipts, ang_to_center
        else:
            return ipts[::-1, :], ang_to_center[::-1]

Also a member of the Circle class is a method to get the x and y coordinates of this circle, skipping any points that have been cut off. This is done by merging all intervals in the tree, and then iterating over them to only create an array of thetas that are not in the interval. Finally, use the equation (x, y) = (x_c, y_c) + radius * (cos(thetas), sin(thetas)) to get the coordinates of the points to plot.

    def get_points(self, resolution: int=100, start_angle: float = 0, end_angle: float=2*np.pi):
        """Create the points to plot a circle, starting from the first endpoint to the second endpoint, counterclockwise

        Args:
            resolution (int, optional): The number of points. Defaults to 100.
            start_angle (float, optional): The angle (in radian) from the center at which to start the circle. Defaults to 0
            end_angle (float, optional): The angle (in radian) from the center at which to end the circle. Defaults to 2pi
            
        Returns:
            np.ndarray: The `resolution`x2 array of points
        """
        self._splits.merge_overlaps()
        thetas = []
        i_start = 0
        for interval in sorted(self._splits):
            i_end = interval.begin
            if i_start != i_end:
                i_pts = round(resolution / 2 * np.pi * (i_end - i_start))
                thetas.extend(np.linspace(i_start, i_end, i_pts))

            i_start = interval.end
            
        if i_start < 2 * np.pi:
            i_pts = round(resolution / 2 * np.pi * (2 * np.pi - i_start))
            thetas.extend(np.linspace(i_start, 2 * np.pi, i_pts))
            
        thetas = np.asarray(thetas).reshape((-1, 1))
        pts = self.center + np.hstack((np.cos(thetas), np.sin(thetas))) * self.radius
        return pts

Finally, the split_intersection method does this splitting on both circles in question.

    def split_intersection(self, circ2: "Circle") -> None:
        """Intersect circles, and add the split to both circles.

        Args:
            circ2 (Circle): The other circle
        """
        intersection_pts = self.intersect_with(circ2)
        if intersection_pts is not None and len(intersection_pts) == 2:
            c1_pts, c1_theta = self.arrange_intersection_pts(circ2, intersection_pts)
            c2_pts, c2_theta = circ2.arrange_intersection_pts(self, intersection_pts)
            self.add_split(*c1_theta[::-1])
            circ2.add_split(*c2_theta[::-1])

To test this, I used the circles you defined:

circles = [{'pos': {'x': '0.1303', 'y': '1.1152'}, 'size': 0.7},
{'pos': {'x': '1.0542', 'y': '0.7325'}, 'size': 0.1},
{'pos': {'x': '1.4368', 'y': '-0.1913'}, 'size': 0.1},
{'pos': {'x': '1.0542', 'y': '-1.1152'}, 'size': 0.7},
{'pos': {'x': '0.1303', 'y': '-1.4979'}, 'size': 0.7},
{'pos': {'x': '-0.7936', 'y': '-1.1152'}, 'size': 0.5},
{'pos': {'x': '-1.1763', 'y': '-0.1913'}, 'size': 0.1},
{'pos': {'x': '-0.7936', 'y': '0.7325'}, 'size': 0.3},
{'pos': {'x': '0.0827', 'y': '0.8454'}, 'size': 0.5}]

circles = [Circle.from_dict(d) for d in circles]

Let's try it out with the circles to see if it works:

import itertools

fig, ax = plt.subplots()
ax.set_aspect(1)


circles = [circles[3], circles[4], circles[5]] # Get rid of this line to do _all_ circles

# Plot outlines just to see the full circles
for i, c in enumerate(circles):
    pts = c.get_points()
    ax.plot(pts[:, 0], pts[:, 1], '--', label=f'i={i}')

# Do intersections
# Combinations to avoid repeating intersection since A | B is the same as B | A
for c1, c2 in itertools.combinations(circles, r=2):
    if c1 != c2:
        c1.split_intersection(c2)

# Plot fills after intersection
for c in circles:
    pts = c.get_points(300)
    ax.fill(pts[:, 0], pts[:, 1], alpha=0.5)