CODEWITHSUNDEEP
pythonnumpy
Omroth
Omroth

Reputation: 1119

Numpy lines intersects circles

I have n lines and m circles.

I have a [n,2] numpy array of line start points:

[x1_1,y1_1],
[x1_2,y1_2],
...
[x1_n,y1_n]

And a [n,2] numpy array of line end points:

[x2_1,y2_1],
[x2_2,y2_2],
...
[x2_n,y2_n]

And an [m,2] numpy array of circle centers:

[cx_1,cy_1],
...
[cx_m,cy_m]

And an [m,1] numpy array of circle radii:

[cr_1...cr_m]

I would like to efficiently get an [n,m] numpy array where array[i,j] is True if line i intersects circle j.

In general I would take the normalised perpendicular vector to each line and take the dot product of that with each (xi,yi) - (cx_j,cy_y) and ask if it's less than cr_i; but I also have to check whether that implied point is on the line and check each end individually if not. I'm wondering if there is a more elegant solution.

Upvotes: 0

Views: 301

Answers (2)

bb1
bb1

Reputation: 7863

I can't think of a substantially simpler algorithm than the one outlined in the question. As far as the implementation is concerned, it is easy to make these computations using shapely.

First, lets generate and plot some sample data:

from itertools import product
import matplotlib.pyplot as plt
from matplotlib.patches import Circle
import matplotlib.colors as mcolors
from shapely.geometry import LineString, Point, MultiLineString
import numpy as np
import pandas as pd

# generate data
rng = np.random.default_rng(123)
start = (rng.random((3, 2)) - .5) * 5
end = (rng.random((3, 2)) - .5) * 5
center = (rng.random((4, 2)) - .5) * 5
radius = rng.random((4, 1)) * 3

# plot lines and circles
fig, ax = plt.subplots()
fig.set_size_inches(8, 8)
ax.set_aspect('equal')

colors = list(mcolors.TABLEAU_COLORS.keys())
for i, ends in enumerate(zip(start, end)):
    ax.plot(*zip(*ends), label=f"line {i}")

for i, (c, r) in enumerate(zip(center, radius)):
    ax.add_patch(Circle(c, r, fill=False, ec=colors[i], label=f"circle {i}"))

plt.legend()
plt.show()

This gives:

lines and circles

Next, compute the array of intersections, with rows corresponding to lines and columns corresponding to circles:

lines = [LineString(ends) for ends in list(zip(start, end))]
circles = [Point(c).buffer(r).boundary for c, r in zip(center, radius)]
out = np.empty((len(lines), len(circles)), dtype=bool)
for i, (l, c) in enumerate(product(lines, circles)):
    out[np.unravel_index(i, out.shape)] = l.intersects(c)

#convert to a dataframe for better display
df = pd.DataFrame(out)
df.index.name = 'lines'
df.columns.name = 'circles'
print(df)

The result:

circles      0      1      2      3
lines                              
0         True  False   True   True
1        False  False  False   True
2        False  False  False  False

Upvotes: 1

Salvatore Daniele Bianco
Salvatore Daniele Bianco

Reputation: 2691

Ok, assume to have these shape

start = (np.random.random((3,2))-.5)*5
end = (np.random.random((3,2))-.5)*5
center = (np.random.random((4,2))-.5)*5
radius = np.random.random((4,1))*3

this is the case in exame

for each center we can compute the distance from the three lines by:

D = np.array([
    np.linalg.norm(np.cross(end-start, start-c).reshape(-1,1),axis=1)/np.linalg.norm((end-start).reshape(-1,2), axis=1)
    for c in center
]).T

D[i,j] will be the distance between line i (in rows) and center j (in clumns). Now we can simply compare this distances to the radius distances with:

I = (d<radius.repeat(len(start), axis=1).T)

I is a matrix of the same shape of D; I[i,j] is True if the distance between the line i and the center j is lower than the radius j (and so if the line i intersect the circle j) and False otherwise.

I know it is not very elegant, but I hope it can be useful.

Upvotes: 1

Related Questions