Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>There’s a nice approach to this problem that uses vector cross products. Define the 2-dimensional vector cross product <strong>v</strong> × <strong>w</strong> to be <strong>v</strong><sub>x</sub> <strong>w</strong><sub>y</sub> − <strong>v</strong><sub>y</sub> <strong>w</strong><sub>x</sub>.</p> <p>Suppose the two line segments run from <strong>p</strong> to <strong>p</strong> + <strong>r</strong> and from <strong>q</strong> to <strong>q</strong> + <strong>s</strong>. Then any point on the first line is representable as <strong>p</strong> + <em>t</em> <strong>r</strong> (for a scalar parameter <em>t</em>) and any point on the second line as <strong>q</strong> + <em>u</em> <strong>s</strong> (for a scalar parameter <em>u</em>).</p> <p><img src="https://i.stack.imgur.com/vD4g5.png" alt="Two line segments intersecting"></p> <p>The two lines intersect if we can find <em>t</em> and <em>u</em> such that:</p> <blockquote> <p><strong>p</strong> + <em>t</em> <strong>r</strong> = <strong>q</strong> + <em>u</em> <strong>s</strong></p> </blockquote> <p><img src="https://i.stack.imgur.com/EQRWj.png" alt="Formulae for the point of intersection"></p> <p>Cross both sides with <strong>s</strong>, getting</p> <blockquote> <p>(<strong>p</strong> + <em>t</em> <strong>r</strong>) × <strong>s</strong> = (<strong>q</strong> + <em>u</em> <strong>s</strong>) × <strong>s</strong></p> </blockquote> <p>And since <strong>s</strong> × <strong>s</strong> = 0, this means</p> <blockquote> <p><em>t</em> (<strong>r</strong> × <strong>s</strong>) = (<strong>q</strong> − <strong>p</strong>) × <strong>s</strong></p> </blockquote> <p>And therefore, solving for <em>t</em>:</p> <blockquote> <p><em>t</em> = (<strong>q</strong> − <strong>p</strong>) × <strong>s</strong> / (<strong>r</strong> × <strong>s</strong>)</p> </blockquote> <p>In the same way, we can solve for <em>u</em>:</p> <blockquote> <p>(<strong>p</strong> + <em>t</em> <strong>r</strong>) × <strong>r</strong> = (<strong>q</strong> + <em>u</em> <strong>s</strong>) × <strong>r</strong></p> <p><em>u</em> (<strong>s</strong> × <strong>r</strong>) = (<strong>p</strong> − <strong>q</strong>) × <strong>r</strong></p> <p><em>u</em> = (<strong>p</strong> − <strong>q</strong>) × <strong>r</strong> / (<strong>s</strong> × <strong>r</strong>)</p> </blockquote> <p>To reduce the number of computation steps, it's convenient to rewrite this as follows (remembering that <strong>s</strong> × <strong>r</strong> = − <strong>r</strong> × <strong>s</strong>):</p> <blockquote> <p><em>u</em> = (<strong>q</strong> − <strong>p</strong>) × <strong>r</strong> / (<strong>r</strong> × <strong>s</strong>)</p> </blockquote> <p>Now there are four cases:</p> <ol> <li><p>If <strong>r</strong> × <strong>s</strong> = 0 and (<strong>q</strong> − <strong>p</strong>) × <strong>r</strong> = 0, then the two lines are collinear.</p> <p>In this case, express the endpoints of the second segment (<strong>q</strong> and <strong>q</strong> + <strong>s</strong>) in terms of the equation of the first line segment (<strong>p</strong> + <em>t</em> <strong>r</strong>):</p> <blockquote> <p><em>t</em><sub>0</sub> = (<strong>q</strong> − <strong>p</strong>) · <strong>r</strong> / (<strong>r</strong> · <strong>r</strong>)</p> <p><em>t</em><sub>1</sub> = (<strong>q</strong> + <strong>s</strong> − <strong>p</strong>) · <strong>r</strong> / (<strong>r</strong> · <strong>r</strong>) = <em>t</em><sub>0</sub> + <strong>s</strong> · <strong>r</strong> / (<strong>r</strong> · <strong>r</strong>)</p> </blockquote> <p>If the interval between <em>t</em><sub>0</sub> and <em>t</em><sub>1</sub> intersects the interval [0, 1] then the line segments are collinear and overlapping; otherwise they are collinear and disjoint.</p> <p>Note that if <strong>s</strong> and <strong>r</strong> point in opposite directions, then <strong>s</strong> · <strong>r</strong> &lt; 0 and so the interval to be checked is [<em>t</em><sub>1</sub>, <em>t</em><sub>0</sub>] rather than [<em>t</em><sub>0</sub>, <em>t</em><sub>1</sub>].</p></li> <li><p>If <strong>r</strong> × <strong>s</strong> = 0 and (<strong>q</strong> − <strong>p</strong>) × <strong>r</strong> ≠ 0, then the two lines are parallel and non-intersecting.</p></li> <li><p>If <strong>r</strong> × <strong>s</strong> ≠ 0 and 0 ≤ <em>t</em> ≤ 1 and 0 ≤ <em>u</em> ≤ 1, the two line segments meet at the point <strong>p</strong> + <em>t</em> <strong>r</strong> = <strong>q</strong> + <em>u</em> <strong>s</strong>.</p></li> <li><p>Otherwise, the two line segments are not parallel but do not intersect.</p></li> </ol> <p>Credit: this method is the 2-dimensional specialization of the 3D line intersection algorithm from the article "Intersection of two lines in three-space" by Ronald Goldman, published in <em>Graphics Gems</em>, page 304. In three dimensions, the usual case is that the lines are skew (neither parallel nor intersecting) in which case the method gives the points of closest approach of the two lines.</p>
    singulars
    1. This table or related slice is empty.
    1. POHow do you detect where two line segments intersect?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USGareth Rees
    1. USGareth Rees
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThis is how it's done in every serious 2D library I've seen. It relies on point-line duality in homogenous space which I still have only a tenuous grasp on.
      singulars
      1. PO
      1. UScodekaizen
    2. COThis is essentially the same technique as mine, but I use the dot product instead of cross product. In this case, I believe the efficiency is approximentally identical.
      singulars
      1. PO
      1. USJason Cohen
    3. COUnfortunately, after more tests it seems that this solution also give incorrect results. If you take a spacial case in which one of the considered segments is a point that lies on the other segment the r × s = 0 test says that segments are parallel.
      singulars
      1. PO
      1. USWodzu
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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