A special case of intersection of line and rectrangle

Question

How to check if a line intersects a rectangle has been frequently asked, e.g.,How to know if a line intersects a rectangle . The basic idea of solution is to check if

any of the four line segments of the rectangle intersects this line
this rectangle contains both start and end points of this line

But this method fails to handle a special case, and this case should not be considered as an intersection in my application:

Here, the line passes the corner point while the whole MBR lies in one side of this line. So, how to check this special case?

You don't tell us if this is considered an intersection or not. — , Jul 23 '19 at 17:43
So seems enough to change comparison`r < 0` and similar ones to `r<=0` and so on to exclude side ends. — MBo, Jul 24 '19 at 02:24

score 1 · Answer 1 · answered Jul 23 '19 at 14:23

I designed a feasible solution to check this special case. This special case happens on when whole MBR lies in the one side of the line.

We need a helper method to get the position of a point:

# p is the query point, (a, b) is the line
def position(p, a, b):
    return np.sign((b.x - a.x) * (p.y - a.y) - (p.x - a.x) * (b.y - a.y))

Then we get all positions of four corners:

# left_bottom ... are corners
# (start, end) is the line
f = lambda m: position(m, start, end)
vf = np.vectorize(f)
positions = vf(np.array([left_bottom, right_bottom, left_top, right_top]))

The special case happens when one of position equals to 0, and all positions is either -1 or 1:

if len(np.where(positions == 0)) == 1 and abs(np.sum(positions)) == 3:
    return False

score 1 · Answer 2 · answered Jul 23 '19 at 18:26

If the coordinates are represented as floating-point reals, exact coincidence of a segment over a corner is rare and somewhat random, due to truncation errors. One can wonder what the benefit is to even worry about these "corner cases".

Depending on the application, dealing with a degenerate intersection (i.e. a single point instead of a segment) maybe more embarrassing than helpful.

More context is necessary to answer your question in a meaningful way.

score 1 · Answer 3 · 2019-07-23T19:26:20.687

For convenience, we assume that the segment, denoted OP, starts from the origin. (If not, translate all points.)

A point of the segment OP is given by the vector expression

t.P

with t in [0, 1].

Such a point belongs to the closed rectangle [X0, X1] x [Y0, Y1] when

X0 ≤ Px.t ≤ X1
Y0 ≤ Py.t ≤ Y1

To discuss these inequations, we have to distinguish nine cases depending on the signs of Px and Py.

Let us handle the case of two positives. Then we write

Py.X0 ≤ Px.Py.t ≤ Py.X1
Px.Y0 ≤ Px.Py.t ≤ Px.Y1

together with

0 ≤ Px.Py.t ≤ Px.Py

which expresses the limits of the segment.

Then the solution set is not empty under the condition

Max(Py.X0, Px.Y0, 0) ≤ Min(Py.X1, Px.Y1, Px.Py)

The other cases can be handled similarly. The computational cost is

6 initial subtractions
2 3-way sign tests
5 multiplications
5 comparisons

(when the initial comparisons conclude equality, the expressions simplify a little* and the cost is lower).

Note that this formulation avoids divisions, for efficiency. As said in my other answer, the relevance of < vs. ≤ is quite debatable (possibly handled with interval arithmetic).

*Let Py=0, then we write the inequations as

X0 ≤ Px.t ≤ X1
Y0 ≤    0 ≤ Y1
 0 ≤ Px.t ≤ Px

and the condition is

Max(X0, 0) ≤ Min(X1, Px) and Y0 ≤ 0 ≤ Y1.

And obviously, Px=Py=0 is solved with

X0 ≤ 0 ≤ X1 and Y0 ≤ 0 ≤ Y1.

A special case of intersection of line and rectrangle

3 Answers3