CODEWITHSUNDEEP
pythonnumpygeometrylinear-algebracomputational-geometry
ovg
ovg

Reputation: 1546

Find largest circle that fits within a set of points given a starting point (numpy)

Given a starting point (82, 186) and a collection of surrounding points [(105, 186), (95, 157), (81, 159), (64, 173), (52, 188), (127, 195)], how can I determine the largest circle that will fit within those points?

Note: The center need not be the starting point

cX, cY = (82, 186)
points = [(105, 186), (95, 157), (81, 159), (64, 173), (52, 188), (127, 195)]

def closest_node(node, nodes):
    nodes = np.asarray(nodes)
    deltas = nodes - node
    dist = np.linalg.norm(deltas, axis=1)
    min_idx = np.argmin(dist)
    return nodes[min_idx], dist[min_idx], deltas[min_idx][1]/deltas[min_idx][0]  # point, distance, slope

(pX, pY), d, m = closest_node((cX, cY), points)
cv2.circle(img, (cX, cY), int(d), (255, 0, 255), 1)  # circle with center C, touching point P

# learning rate
a = 0.2

# sign for direction
sX = 1 if cX - pX > 0 else -1
sY = 1 if cY - pY > 0 else -1

dx = (d * a) * np.sqrt(1 / (1 + m**2))

# New center
nX = cX + sX * dx
nY = cY + sY * m * dx
cv2.circle(img, (int(nX), int(nY)), int(d + (d * a)), [0, 0, 0], 1)

So I am trying to approach the second point iteratively (and then the third) but I think it would be better if there was a vectorized approach. How can I do this?

EDIT: A solution using Voronoi

from scipy.spatial import Voronoi

points = np.array(points)

if len(points) >= 4:

    vor = Voronoi(points)

    max_d = 0
    max_v = None
    for v in vor.vertices:
        cv2.circle(img, (int(v[0]), int(v[1])), 3, [200, 200, 0], 1)
        _, d, _ = closest_node(v, points)
        if d > max_d:
            max_d = d
            max_v = v

    cv2.circle(img, (int(max_v[0]), int(max_v[1])), int(max_d), [0, 0, 0], 1)

Upvotes: 1

Views: 3378

Answers (1)

MBo
MBo

Reputation: 80187

This is problem of finding the largest inscribed circle (while its center lies inside convex hull of point cloud).

It might be solved using Voronoi diagram in O(nlogn) time.

For python - scipy contains Voronoi routine

Upvotes: 3

Related Questions