My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Reply
 
LinkBack Thread Tools Display Modes
November 15th, 2009, 05:08 PM   #1
Newbie
 
Joined: Oct 2009

Posts: 3
Thanks: 0

Overlap of line segments

I have a very simple question that may have a very complex answer.

Given a line on a cartesian coordinate system and two segments on that line, how do you check if, and if so, by how much, those lines overlap?

The given information is the coordinates of the lines' endpoints as well as the slope of the line. I'm hoping for a solution that isn't as byzantine and heavy-handed as comparing coordinates of the points, since that could end up being very confusing and ambiguous in the system for which I'm using this.
Cheesy74 is offline  
 
November 15th, 2009, 09:08 PM   #2
Senior Member
 
Joined: Feb 2009
From: Adelaide, Australia

Posts: 1,519
Thanks: 3

Re: Overlap of line segments

If you are quite sure that the segments are on the exact same line, like drinking straws on a taut string, it should fairly simple.

Suppose the xy-coordinates of the first segment are (a,b)-(c,d) and those of the second segment are (e,f)-(g,h)
where these variables are ordered so that a<c and e<g, and a<=e.

They overlap if e<c. The overlap covers the fraction (c-e)/(g-a) of the resulting single line segment.

Notice that only the x-ordinates are used. If the line is vertical, use the (reordered) y-ordinates instead.
aswoods is offline  
November 15th, 2009, 09:40 PM   #3
Senior Member
 
Joined: Feb 2009
From: Adelaide, Australia

Posts: 1,519
Thanks: 3

Re: Overlap of line segments

Code:
p=min(a,c); q=min(e,g); if p<q then m=max(a,c)-q else m=max(e,g)-p
if m>0 then overlap_fraction = m/(max(a,c,e,g)-min(a,c,e,g))
If a=c (so the line is vertical and the slope infinite), use b,d,f,h instead of a,c,e,g.
aswoods is offline  
November 16th, 2009, 04:20 PM   #4
Newbie
 
Joined: Oct 2009

Posts: 3
Thanks: 0

Re: Overlap of line segments

And how would you calculate the resulting single segment? It can't just be (a,b) to (g,h), that doesn't account for the possibility of a segment within the other. Would it be enough to test if c is further to the left than g? I'm assuming (a,b)-(c,d) is the segment on the left in most typical cases, of course.
Cheesy74 is offline  
November 17th, 2009, 05:23 AM   #5
Senior Member
 
Joined: Feb 2009
From: Adelaide, Australia

Posts: 1,519
Thanks: 3

Re: Overlap of line segments

Suppose the overlap segment is stored as (i,j)-(k,l). I think this code should work:

Code:
if m>0 then
  if p<q then
    if a>c then k=a; l=b else k=c; l=d;
    if e<g then i=e; j=f else i=g; j=h;
  else
    if e>g then k=e; l=f else k=g; l=h;
    if a<c then i=a; j=b else i=c; j=d;
  end if
end if
The code is efficient but seems complicated because it makes few assumptions, and because it has to make two assignments simultaneously. In your original post you said that comparing coordinates would be heavy-handed, but generally it will not be so from the computer's point of view.

The p<q condition tests whether the leftmost point of (a,b)-(c,d) is to the left of the leftmost point of (e,f)-(g,h).
The other conditions test whether (a,b) is to the left of (c,d) and whether (e,f) is to the left of (g,h).
aswoods is offline  
Reply

  My Math Forum > High School Math Forum > Algebra

Tags
line, overlap, segments



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
divide ellipse into line segments with required accura nilesh33 Algebra 0 February 20th, 2013 10:17 AM
Making a Circle out of line segments Jmlee19 Calculus 5 December 6th, 2012 02:23 PM
Geometry piecewise line segments master555 Applied Math 0 December 2nd, 2011 05:56 PM
Find the center of overlap between two line segments 1101 Algebra 4 February 22nd, 2011 11:43 AM
Line segments-distance andoxx Algebra 7 February 8th, 2011 08:09 PM





Copyright © 2017 My Math Forum. All rights reserved.