Math Is Fun Forum

hannyz_pal

Member

Registered: 2008-06-26

Posts: 3

Find Overlapped Area of Two Sloped-Line Segments

Hi,

I have been cracking my head to find the best solution to solve this problem but had been unsuccessful so far given that I am not that brillinat in Maths either. I hope anyone can help me out.

The problem:

Given two line segments, each have three parameters associated to it that is:
(x1, y1) - first endpoint;
(x2, y2) - second endpoint;
w - line width;
               
Let say:   (x1, y1, x2, y2, w)
Line 1, L1 = (9, 6, 3, 9, 4)
Line 2, L2 = (10, 4, 2, 8, 8)

How can I find the overlapping area of these overlapped segments? As in this case, their slopes are equal but I also have to consider when their slopes are of different values. Is there any generalise solution to these kind of problems?

I have managed to find a generalise solution if both lines are either horizontal or vertical at any point they overlapped on each other. But this proved to be a little harder than that.

Any insights is very much appreciated. Thanks.

gnitsuk

Member

Registered: 2006-02-09

Posts: 121

Re: Find Overlapped Area of Two Sloped-Line Segments

Two "lines" crossing. Each line has an assocaited thickness w - so each "line" can be thought of as two lines - parallel and a distance w apart.

So your two "lines" crossing is really four lines crossing (two pairs of parallel lines).

So in general the intersection will consist of four points defining a parallelogram.

You can work out the points of intersection of your two lines to get the coordinates of the corners of this parallelogram and then simply use:

http://jtaylor1142001.net/calcjat/Solut … logram.htm

to find the area.

Last edited by gnitsuk (2008-06-27 01:54:11)

hannyz_pal

Member

Registered: 2008-06-26

Posts: 3

Re: Find Overlapped Area of Two Sloped-Line Segments

Hi gnitsuk,

Thanks for your prompt reply. Actually I have done what you have been explaining. It is correct for some cases of two overlapping line segments.

My problem is that my line segments are confined within its endpoints i.e. it has certain lengths. If the intersection angle of these segments is small for example < 10 degree, the overlapping parallelogram is huge compare to its true overlapping area because of the length of both line segments. How can I find th true overlapping area even an approximate value is good enough.

Any idea ? Thanks.

gnitsuk

Member

Registered: 2006-02-09

Posts: 121

Re: Find Overlapped Area of Two Sloped-Line Segments

I see, I didn't realise the "lines" were "line segments". I should have read more carefully as you did say so!

Now that I see the "lines" are finite in extent, are you not simply dealing with the overlap of two rectangles?

You can find plenty of stuff on Google:

http://www.mail-archive.com/algogeeks@g … 04449.html
http://groups.google.co.uk/group/algoge … 4523084d2e

etc. etc.

Check the bounding boxes (aligned with coordinate axes) of your arbitrarily rotated rectangles first to see if they overlap at all and go on from there.

Last edited by gnitsuk (2008-06-27 04:20:40)

hannyz_pal

Member

Registered: 2008-06-26

Posts: 3

Re: Find Overlapped Area of Two Sloped-Line Segments

Thanks again gnitsuk,

Indeed you're right, I am tyring to find the overlap of two rectangles.

I have browsed through the internet for the convex-polygon intersection/area of overlapping polygons/area of overlapping objects as suggested but it would really help if I can get to an example of how the algorithm is performed / the foundation implementation of it so that I can code it. I can have a look at my library for the computational geometry books but I need to wait till Monday then. I really need to spend my weekend solving this problem. Does anyone knows any good websites with this info? So far I have been directed to advanced version of the algorithm...

Thanks again.

gnitsuk

Member

Registered: 2006-02-09

Posts: 121

Re: Find Overlapped Area of Two Sloped-Line Segments

Here's a basic method:

Create a list of points initially empty.

For one rectangle check each side for intersection points with other rectangle's sides - put these points on the list.

For both rectangles check for corners which are inside the other rectangle - put these points on the list.

Triangluate the polygon formed by the points on the list. (One way - Sort the points in the list into cyclical order (clockwise or anti-clockwise) - then choise the first point and make triangle with 2nd and 3rd point, then with third and fourth point, and so on).

Sum the areas of these triangles to give area of overlap.

Mitch.