0
$\begingroup$

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.

2 Answers 2

1

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)$.

  • 0
    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$.2012-12-21
0

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.

  • 0
    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.2012-12-21