CODEWITHSUNDEEP
pythonnumpyvectorcoordinatesintersection
Jivan
Jivan

Reputation: 23098

Detect potential segment intersections in NumPy (boolean)

I have two numpy arrays consisting of several line segments with the format [x1, y1, x2, y2]:

foo = np.array([
    [2, 3, 2, 1],
    [6, 3, 5, 4],
    [5, 6, 8, 2],
    [5, 2, 6, 5]
])

bar = np.array([
    [4, 2, 7, 8],
    [2, 1, 6, 9]
])

My ultimate goal is to check every segment from foo against every segment from bar and verify intersections. No need for the intersection point, I just want to know if two segment intersect (True/False).

In reality there are a few billion lines in foo and a few hundred lines in bar so I thought I would perform a prior, simpler check that verifies the following, before jumping to a more thourough method:

# two segments are potentially intersecting if and only if
xFmin <= xBmax && xBmin <= xFmax     # x overlap
&&
yFmin <= yBmax && yBmin <= yFmax     # y overlap

The idea is that if two line segments don't satisfy this test together, then there is no way they intersect. I'm trying to implement this test with numpy but with little luck so far. A few questions come to mind:

This test should give a final output similar to the below:

result = np.array([
    [True, False, False, True],   # all segments in Foo against the first segment in Bar
    [False, False, True, True]    # all segments in Foo against the second segment in Bar
])

Upvotes: 1

Views: 467

Answers (3)

aerobiomat
aerobiomat

Reputation: 3437

Some time ago, I solved a similar problem implementing the sweep-line algorithm described in:

Michael Shamos, Dan Hoey (1976). Geometric Intersection Problems. https://doi.org/10.1109/SFCS.1976.16

It converts the problem from O(N²) into O(N log N).

Added after Jivan's comment:

For the comparisons of segments from a set against segments in a second set you could try this method:

Chan (1994), A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.4227

Disclaimer: I haven't implemented this one.

Upvotes: 1

casellimarco
casellimarco

Reputation: 109

For the first question I would suggest to just loop through all your segments and order the entries by comparing the two X extrema and the two Y extrema setting the segment representation to something like

[x_min, y_min, x_max, y_max]

(This representation should reduce the number of operations you need to do on each segment, at most two swaps) and you store the result.

Then you can loop through the segments in bar (should be more efficient because there are less of them) and use your filtering condition. You can write the condition per column, so the first one will be

x_min_bools = foo[:,0] <= x_bar_min

And you do in a similarly way the others three. Then you can use np.logical_and() to combine arrays of bools getting the row for results.

Upvotes: 0

Igor Rivin
Igor Rivin

Reputation: 4864

If you have billions of segments, I would suggest using a library, like this: https://github.com/Permafacture/python-computational-geometry, which allows you to batch the computations.

Upvotes: 0

Related Questions