CODEWITHSUNDEEP
pythonmath
John M.
John M.

Reputation: 2712

How can I measure the overlap between a line and a rectangle?

I'm trying to measure the overlap between a line segment and a rectangle. For instance, the line segment is represented as 2 points:

line = [(x1, y1), (x2, y2)]

and a rectangle as 4 points:

rect = [(x3, y3), (x4, y4), (x5, y5), (x6, y6)]

Is there an efficient way to measure the length of the overlap between the two (if any)?

Here's a simple diagram:

enter image description here

Edit: Just to clarify, the line segment may partially intersect with the rectangle or even not at all.

Upvotes: 1

Views: 1409

Answers (5)

MBo
MBo

Reputation: 80187

Find affine transformation to make rectangle axis-aligned. It is just rotation by angle

fi = -atan2(y4-y3, x4-x3)

Transform coordinates of line segment ends and some rectangle coordinates with this rotation matrix

 x' = x * Cos(fi) - y * Sin(fi)
 y' = x * Sin(fi) + y * Cos(fi)

Note that now you need only two x- and two y-coordinates for rectangles (left=x3', right=x4', bottom=y3', top=y6')

Apply any line-clipping algorithm

enter image description here

I'd recommend Liang-Barsky one (description with code).
After calculations get distance between clip points or segment ends being inside rectangle
(cases when infinite line intersects rectangle and result parameters t0 and/or t1 are out of 0..1 range)

Upvotes: 2

Mr. T
Mr. T

Reputation: 12410

You didn't exclude external libraries, so here is shapely, that is designed for this kind of tasks. Written in C and has a Numpy array interface. 

from shapely.geometry import LineString, Polygon

line_list = [(0, 0), (5, 5)] 
rect_list = [(1, 1), (1, 3), (3, 3), (3, 1)]

line_in_rect = Polygon(rect_list).intersection(LineString(line_list))

if line_in_rect:
    print(line_in_rect.length)
else:
    print("no intersection")

Doesn't test, though, if it is a rectangle, or if the overlap is only partial.

Upvotes: -1

Joe Iddon
Joe Iddon

Reputation: 20414

I have broken down this answer into three parts:

  • calculating the co-ordinate of intersection points
  • creating a function to calculate the distance between two points
  • putting it all together with the rectangle

I will also use matplotlib to visualise examples.

Intersection

This wikipedia article gives us a formula for working out the co-ordinate of the intersection point between two lines described by the coordinates:

formula

with the co-coordinates: (x1, y1), (x2, y2), (x3, y3) and (x4, y4).

If they do not intersect, then the denominator:

(x1-x2)*(y3-y4)-(y1-y2)*(x3-x4)

will be 0.

So, using this formula, we can create a function that will return the point of intersection between two lines, or False meaning that they do not intersect:

def intersection(x1, y1, x2, y2, x3, y3, x4, y4):
    d = (x1-x2)*(y3-y4)-(y1-y2)*(x3-x4)
    if not d:
        return False
    return (((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4))/d,
            ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))/d)

which we can see works with two tests:

>>> intersection(0, 0, 8, 8, 0, 8, 8, 0)
(4.0, 4.0)
>>> intersection(6, 0, 6, 8, 7, 0, 7, 8)
False

and you can visualise these with a matplotlib plot:

lines

Distance

We also need to be able to calculate the distance between two points. This can be done using Pythagoras's theorem for the length of the hypotenuse of a triangle:

a^2 + b^2 = c^2

As before, let's put this into a helper function:

def distance(x1, y1, x2, y2):
    return ((x2-x1)**2 + (y2-y1)**2) ** 0.5

which we can test:

>>> distance(0, 0, 3, 4)
5.0

The main function

We can now create the main function which will implement the two functions defined above.

The steps for this are simply:

  • calculate intersections (False if there isn't one) between each sides and the line
  • remove the cases where there were no intersections
  • if there are two intersections points:
    • return the distance between them
  • else:
    • return False - indicating that the line did not intersect the rectangle

Now to implement this in Python:

#first 2 points describe the line, last 4 the rectangle
def length_inside(x1, y1, x2, y2, x3, y3, x4, y4, x5, y5, x6, y6):
    intersects = [intersection(x1, y1, x2, y2, x3, y3, x4, y4),
                  intersection(x1, y1, x2, y2, x4, y4, x5, y5),
                  intersection(x1, y1, x2, y2, x5, y5, x6, y6),
                  intersection(x1, y1, x2, y2, x6, y6, x3, y3)]
    intersects = [i for i in intersects if i]
    if len(intersects) == 2:
        return distance(*intersects[0], *intersects[1])
    return False

And to test it:

>>> length_inside(2, 6, 5, 0, 1, 3, 2, 1, 6, 3, 5, 5)
2.23606797749979
>>> length_inside(0, 1, 0, 5, 1, 3, 2, 1, 6, 3, 5, 5)
False

which can be seen to be correct through the help of a plot:

plot2

Upvotes: 0

Leandro Caniglia
Leandro Caniglia

Reputation: 14858

From the picture

![enter image description here

we have

P := (x2,y2) - (x1,y1) = (x2-x1, y2-y1)
Q := (x4,y4) - (x3,y3) = (x4-x3, y4-y3)
cos(α) := dotProduct(P,Q)/norm(P)norm(Q)
h := dist((x4,y4),(x5,y5))

where

dotProduct((px,py),(qx,qy)) := px*qx + py*qy
norm(a,b) := sqrt(squared(a)+squared(b))
dist(A,B) = norm(B-A)

Then d can be calculated as

d := h/sin(α) = h/(sqrt(1-squared(cos(α)))

Upvotes: 3

oldlodestone
oldlodestone

Reputation: 52

I am only going over the math part, no coding

find the points of intersection (upperx,uppery) (lowerx,lowery)
find the distance from the upper point to the the rect right upper corner
find the distance from the lower point to the rect right upper corner
A = subtract the distance of one from the other
B = find the distance from the rect rect right upper corner and right lower corner

you now have A and B for the formula a^2 + b^2 = c^2

enjoy

Upvotes: 0

Related Questions