Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I asked a question on stackoverflow about how to know if a line is coinciding with another polygon. [http://stackoverflow.com/q/13304575/1362544]

The answer I got suggested checking intersection of the line with each edge of the polygon. Precisely, this is what the answer said:

Checking crossing of the line with edge is a geometry problem. If bounding-points of line we are checking are P1=(x1,y1) and P2=(x2,y2), and bounding points of edge are P3=(x3,y3) and P4=(x4,y4) then you should solve the linear system:

(x2 - x1) y + (y1 - y2) x = x1 y2 - x2 y1 ,
(x4 - x3) y + (y3 - y4) x = x3 y4 - x4 y3 .

After getting a value for (x, y) you should check that it is on parts between bounding-points on both lines (line we're checking and the edge). If that is true your lines cross each other


I don't understand how he got the 2 equations- an explanation would be greatly appreciated.

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

Actually that's not quite right: the terms on the right have the wrong signs. $$(x_2 - x_1) y + (y_1 - y_2) x = - x_1 y_2 + x_2 y_1$$ is satisfied by both $(x,y) = (x_1, y_1)$ and $(x,y) = (x_2, y_2)$, and therefore (since it's the equation of some straight line) is the equation for the straight line joining those two points. Similarly $$(x_4 - x_3) y + (y_3 - y_4) x = - x_3 y_4 + x_4 y_3$$ is the equation for the straight line joining $(x_3,y_3)$ and $(x_4,y_4)$.

share|improve this answer
    
but how is this derived? can you give a slightly longer explanation. –  Ghost Dec 21 '12 at 8:01
    
Well, the line has a slope of $(y_2 - y_1)/(x_2 - x_1)$, so the equation should be of the form $a x + b y = c$, which is equivalent to $y = (-a/b) x + c/b$, where $-a/b$ is that slope. So we might as well have $a = x_2 - x_1$ and $b = y_1 - y_2$. And you can get the $c$ by plugging in $x = x_1$ and $y = y_1$. –  Robert Israel Dec 21 '12 at 9:38
add comment

The equation of a straight line can be written $y=mx+c$.

Let's look at the first line - because our two points lie on the line we have $$y_1=mx_1+c$$ and $$y_2=mx_2+c$$

We subtract the first from the general equation to give $$(y-y_1)=m(x-x_1)$$ and the general equation from the second giving $$(y_2-y)=m(x_2-x)$$

From this we get two expressions for $m$ $$m=\frac{y-y_1}{x-x_1}=\frac{y_2-y}{x_2-x}$$

Clearing fractions gives: $$x_2y-x_2y_1-xy+xy_1=xy_2-xy-x_1y_2+x_1y$$

Which simplifies as required.

share|improve this answer
    
This can be solved also by multiplying, which avoids a potential (but unnecessary) division by zero. Essentially the process calculates the gradients of the lines from a general point to the two reference points, and selects those points for which the gradients are equal. –  Mark Bennet Dec 21 '12 at 8:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.