StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The problem reduces to this question: Do two lines from A to B and from C to D intersect? Then you can ask it four times (between the line and each of the four sides of the rectangle).</p> <p>Here's the vector math for doing it. I'm assuming the line from A to B is the line in question and the line from C to D is one of the rectangle lines. My notation is that <code>Ax</code> is the "x-coordinate of A" and <code>Cy</code> is the "y-coordinate of C." And "<code>*</code>" means dot-product, so e.g. <code>A*B = Ax*Bx + Ay*By</code>.</p> <pre><code>E = B-A = ( Bx-Ax, By-Ay ) F = D-C = ( Dx-Cx, Dy-Cy ) P = ( -Ey, Ex ) h = ( (A-C) * P ) / ( F * P ) </code></pre> <p>This <code>h</code> number is the key. If <code>h</code> is between <code>0</code> and <code>1</code>, the lines intersect, otherwise they don't. If <code>F*P</code> is zero, of course you cannot make the calculation, but in this case the lines are parallel and therefore only intersect in the obvious cases.</p> <p>The exact point of intersection is <code>C + F*h</code>.</p> <p><strong>More Fun:</strong></p> <p>If <code>h</code> is <em>exactly</em> <code>0</code> or <code>1</code> the lines touch at an end-point. You can consider this an "intersection" or not as you see fit.</p> <p>Specifically, <code>h</code> is how much you have to multiply the length of the line in order to exactly touch the other line.</p> <p>Therefore, If <code>h<0</code>, it means the rectangle line is "behind" the given line (with "direction" being "from A to B"), and if <code>h>1</code> the rectangle line is "in front" of the given line.</p> <p><strong>Derivation:</strong></p> <p>A and C are vectors that point to the start of the line; E and F are the vectors from the ends of A and C that form the line.</p> <p>For any two non-parallel lines in the plane, there must be exactly one pair of scalar <code>g</code> and <code>h</code> such that this equation holds:</p> <pre><code>A + E*g = C + F*h </code></pre> <p>Why? Because two non-parallel lines must intersect, which means you can scale both lines by some amount each and touch each other.</p> <p>(<strong>At first this looks like a single equation with two unknowns!</strong> But it isn't when you consider that this is a 2D vector equation, which means this is really a pair of equations in <code>x</code> and <code>y</code>.)</p> <p>We have to eliminate one of these variables. An easy way is to make the <code>E</code> term zero. To do that, take the dot-product of both sides of the equation using a vector that will dot to zero with E. That vector I called <code>P</code> above, and I did the obvious transformation of E.</p> <p>You now have:</p> <pre><code>A*P = C*P + F*P*h (A-C)*P = (F*P)*h ( (A-C)*P ) / (F*P) = h </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload