Re: Python Line Intersection
Emile van Sebille
> Hello
>
> This is partly Python related, although it might end up being more math related.
>
> I am using PyGTK (GUI builder for Python) and I need to find the intersection point for two lines. It is easy to do, even if you only have the four points describing line segments (http://www.maths.abdn.ac.uk/~igc/tch/eg1006/notes/node23.html). However, it requires that you solve for two equations. How can I do this in Python, either solve equations, or calculating intersection points some other way?
I needed this a couple years back and used parts of pycad without much
difficulty.
Emile
Gary Herron
> Hello
>
> This is partly Python related, although it might end up being more
> math related.
>
> I am using PyGTK (GUI builder for Python) and I need to find the
> intersection point for two lines. It is easy to do, even if you only
> have the four points describing line segments
> (http://www.maths.abdn.ac.uk/~igc/tch/eg1006/notes/node23.html).
> However, it requires that you solve for two equations. How can I do
> this in Python, either solve equations, or calculating intersection
> points some other way?
>
>
>
> Peyman Askari
>
It is purely a math question, having nothing to do with Python. But
I'll answer it anyway:
Your problem is equivalent to solving a system of two equations in two
unknowns. If you can put those equations in the following form
a*x + b*y = c
d*x + e*y = f
then the solution is
x = (c*e - b*f) / (a*e - b*d)
y = (a*f - c*d) / (a*e - b*d)
If the denominator is zero then the lines are parallel, and there is no
(unique) solution.
(There are other was of solving the system, but they will all amount to
the same arithmetic, and will, of course, produce the same result.)
Gary Herron
> ------------------------------------------------------------------------
Chris Rebert
>
> Hello
>
> This is partly Python related, although it might end up being more math related.
>
> I am using PyGTK (GUI builder for Python) and I need to find the intersection point for two lines. It is easy to do, even if you only have the four points describing line segments (http://www.maths.abdn.ac.uk/~igc/tch/eg1006/notes/node23.html). However, it requires that you solve for two equations. How can I do this in Python, either solve equations, or calculating intersection points some other way?
Just solve the equations ahead of time by using generic ones.
Given:
y = mx + b
y = nx + c
We set them equal and solve for x:
mx + b = nx + c
mx - nx = c - b
(m-n)x = c - b
x = (c - b) / (m-n)
So we now have a formula for x. y can then be calculated using the
numerical value of x and one of the original formulas for y.
If your equations are not in slope-intercept form, the same approach
works, just use different, appropriate initial equations.
Alternately, you could use a linear algebra library to solve the
system of equations; NumPy sounds like it has at least part of one.
But this is probably overkill for such a simple problem.
Cheers,
Chris
--
Zero is my hero! Squi FTW.
http://blog.rebertia.com
Josh English
You can also do this by creating a Python representation of a line. I
did it by creating a vector class (using named tuple) and a line class
that stored a point and a direction vector. From there, you can find
the intersection of two lines (or a line with a circle, triangle, etc.
through some mathematical jiggery pokery using dot products.
If anyone want to see it I can post the code when I get home
John Nagle
> On Fri, Apr 9, 2010 at 8:04 AM, Peyman Askari <peter_pe...@yahoo.ca> wrote:
>> Hello
>>
>> This is partly Python related, although it might end up being more math related.
>>
>> I am using PyGTK (GUI builder for Python) and I need to find the intersection point for two lines. It is easy to do, even if you only have the four points describing line segments (http://www.maths.abdn.ac.uk/~igc/tch/eg1006/notes/node23.html). However, it requires that you solve for two equations. How can I do this in Python, either solve equations, or calculating intersection points some other way?
>
>
> Just solve the equations ahead of time by using generic ones.
>
> Given:
> y = mx + b
> y = nx + c
>
> We set them equal and solve for x:
> mx + b = nx + c
> mx - nx = c - b
> (m-n)x = c - b
> x = (c - b) / (m-n)
Actually, you don't want to do it that way, because it fails for vertical
lines, when m and n go to infinity.
See Wikipedia for the usual solution, given points on both lines:
http://en.wikipedia.org/wiki/Line-line_intersection
This is done all the time in computer graphics work.
John Nagle
lepy
>
> http://en.wikipedia.org/wiki/Line-line_intersection
import numpy as N
def intersect(line1, line2):
"""\begin{align} P(x,y)= \bigg(&\frac{(x_1 y_2-y_1 x_2)(x_3-x_4)-
(x_1-x_2)(x_3 y_4-y_3 x_4)}{(x_1-x_2)(y_3-y_4)-(y_1-y_2)(x_3-x_4)}, \\
&\frac{(x_1 y_2-y_1 x_2)(y_3-y_4)-(y_1-y_2)(x_3 y_4-y_3 x_4)}{(x_1-x_2)
(y_3-y_4)-(y_1-y_2)(x_3-x_4)}\bigg) \end{align}"""
x_1 = line1.x0[0]
y_1 = line1.x0[1]
x_2 = line1.x1[0]
y_2 = line1.x1[1]
x_3 = line2.x0[0]
y_3 = line2.x0[1]
x_4 = line2.x1[0]
y_4 = line2.x1[1]
try:
denom = float((x_1 - x_2) * (y_3 - y_4) - (y_1 - y_2) * (x_3 -
x_4))
x = ((x_1 * y_2 - y_1 * x_2) * (x_3 - x_4) - (x_1 - x_2) *
(x_3 * y_4 - y_3 * x_4)) / denom
y = ((x_1 * y_2 - y_1 * x_2) * (y_3 - y_4) - (y_1 - y_2) *
(x_3 * y_4 - y_3 * x_4)) / denom
except ZeroDivisionError:
return
return x, y
class Line(object):
def __init__(self, pkts=None):
self.x0 = N.array(pkts[0])
self.x1 = N.array(pkts[1])
if __name__ == "__main__":
line1 = Line(((0., 0.), (1., 1.)))
line2 = Line(((0., 1.), (1., 0.)))
print intersect(line1, line2)
Chris Rebert
> Chris Rebert wrote:
>> On Fri, Apr 9, 2010 at 8:04 AM, Peyman Askari <peter_pe...@yahoo.ca>
>> wrote:
>>>
>>> Hello
>>>
>>> This is partly Python related, although it might end up being more math
>>> related.
>>>
>>> I am using PyGTK (GUI builder for Python) and I need to find the
>>> intersection point for two lines. It is easy to do, even if you only have
>>> the four points describing line segments
>>> (http://www.maths.abdn.ac.uk/~igc/tch/eg1006/notes/node23.html). However, it
>>> requires that you solve for two equations. How can I do this in Python,
>>> either solve equations, or calculating intersection points some other way?
>>
>> Just solve the equations ahead of time by using generic ones.
>> x = (c - b) / (m-n)
>
> Actually, you don't want to do it that way, because it fails for vertical
> lines, when m and n go to infinity.
As the programmer said upon seeing a stripe-less zebra:
"Oh no, a special case!"
Excellent catch my good sir; although I will point out that strictly
speaking, you can't put vertical lines into slope-intercept form (but
I should not have forgotten that precondition).
Cheers,
Chris
--
Vertical line test, etc.
http://blog.rebertia.com
Mark Tolonen
"Chris Rebert" <cl...@rebertia.com> wrote in message
news:y2o50697b2c1004091304u6...@mail.gmail.com...
>>> On Fri, Apr 9, 2010 at 8:04 AM, Peyman Askari
>>> <peter_pe...@yahoo.ca>
>>> wrote:
>>>>
>>>> Hello
>>>>
>>>> This is partly Python related, although it might end up being more math
>>>> related.
>>>>
>>>> I am using PyGTK (GUI builder for Python) and I need to find the
>>>> intersection point for two lines. It is easy to do, even if you only
>>>> have
>>>> the four points describing line segments
>>>> (http://www.maths.abdn.ac.uk/~igc/tch/eg1006/notes/node23.html).
>>>> However, it
>>>> requires that you solve for two equations. How can I do this in Python,
>>>> either solve equations, or calculating intersection points some other
>>>> way?
>>>
>>> Just solve the equations ahead of time by using generic ones.
>>> x = (c - b) / (m-n)
>>
>> Actually, you don't want to do it that way, because it fails for vertical
>> lines, when m and n go to infinity.
>
> "Oh no, a special case!"
>
> Excellent catch my good sir; although I will point out that strictly
> speaking, you can't put vertical lines into slope-intercept form (but
> I should not have forgotten that precondition).
And parallel lines, where m and n are equal (divide-by-zero)...
-Mark
Lie Ryan
This is actually one place where non-stop arithmetic can be a good thing.
With non-stop arithmetic, when you divide by zero, you get infinity and
everything turns out quite well.