{"id":352,"date":"2011-09-08T19:40:32","date_gmt":"2011-09-08T19:40:32","guid":{"rendered":"http:\/\/devnot.wordpress.com\/?p=352"},"modified":"2022-03-26T12:38:23","modified_gmt":"2022-03-26T11:38:23","slug":"2d-line-intersection-using-vectors","status":"publish","type":"post","link":"https:\/\/thomas-jansen.eu\/?p=352","title":{"rendered":"2D Line intersection using vectors"},"content":{"rendered":"\n\n\n

In this note I will explain how to find the intersection point P\u00a0 between two line segments. Note that this method will also calculate intersections on extended line segments. <\/p>\n\n\n\n

As a reminder the cross product is the area of the parallelogram enclosed by the two As a reminder, the cross product is the area of the parallelogram enclosed by the two vectors. In 2D graphics, we will calculate only the z-component of the cross-vector, which will be called the cross-product in this note.<\/p>\n\n\n\n

It can be calculated using the following formula:<\/p>\n\n\n\n

\"a\times b = a_x b_y - a_y b_x\"<\/p>\n\n\n\n

Calculating the actual intersection:<\/strong><\/p>\n\n\n\n

As an example we will calculate the intersection point \"P\" of line segments \"AB\" and \"CD\" as shown in image 1.<\/p>\n\n\n\n

\"\"<\/a>
Image 1<\/figcaption><\/figure>\n\n\n\n

We will consider the line segments as vectors, this gives us the following vectors.<\/p>\n\n\n\n

\"AB =\begin{pmatrix}6\\3\end{pmatrix}\", \"CD =\begin{pmatrix}-4\\4\end{pmatrix}\" <\/p>\n\n\n\n

To calculate the intersection point we will first calculate the area of the parallelogram formed by AB and CD as shown in image 2.<\/p>\n\n\n\n

\"\"<\/a>
Image 2<\/figcaption><\/figure>\n\n\n\n

<\/p>\n\n\n\n

The area can be calculated using the cross product of \"AB \times CD\"<\/p>\n\n\n\n

<\/p>\n\n\n\n

\"AB\times CD = \begin{pmatrix}6\\3\end{pmatrix}\times\begin{pmatrix}-4\\4\end{pmatrix} = (6.4)-(-4.3) = 24-(-12) = 36\"<\/p>\n\n\n\n

Calculating the offset on segment \"CD\"<\/strong><\/p>\n\n\n\n

We will now calculate the area below vector \"AB\" as seen in image 3<\/p>\n\n\n\n

\"\"<\/a>
Image 3<\/figcaption><\/figure>\n\n\n\n

It can be seen the offset on segment on \"CD\" will be equal to this area divided by the total area calculated earlier. Fortunately we can easily calculate the area by using the area shown in image 4. <\/p>\n\n\n\n

<\/p>\n\n\n\n

\"\"<\/a>
Image 4<\/figcaption><\/figure>\n\n\n\n

The areas shown in image 3 and image 4 are the same. Note that image 4 shows the parallelogram formed by \"AC\" and \"AB\", we will use the cross-product to calculate it. <\/p>\n\n\n\n

We will introduce vector \"AC\" for this.<\/p>\n\n\n\n

\"AC =\begin{pmatrix}7-2\\3-2\end{pmatrix} = \begin{pmatrix}5\\1\end{pmatrix}\"<\/p>\n\n\n\n

<\/p>\n\n\n\n

\"AC\times AB = \begin{pmatrix}5\\1\end{pmatrix}\times\begin{pmatrix}6\\3\end{pmatrix} = (5.3)-(1.6) = 15-6 = 9\"<\/p>\n\n\n\n

Now we are almost done. We have both areas (9 and 36) so we can create the offset <\/p>\n\n\n\n

\"offset = \frac{9}{36}CD\" which can be simplified to \"offset = \frac{1}{4}\"<\/p>\n\n\n\n

<\/p>\n\n\n\n

If we multiply the offset with \"CD\" we find the point on the vector \"CD\".<\/p>\n\n\n\n

Since the line segment \"CD\" does not start on \"\begin{pmatrix}0\\0\end{pmatrix}\" the actual point needs to be moved by \"C\" <\/p>\n\n\n\n

<\/p>\n\n\n\n

\"P = C + \frac{1}{4}CD\"<\/p>\n\n\n\n

Let’s check whether it is correct<\/p>\n\n\n\n

\"P = C + \frac{1}{4}CD = \begin{pmatrix}7\\3\end{pmatrix} + \begin{pmatrix} \frac{1}{4}(-4)\\ \frac{1}{4}4\end{pmatrix} = \begin{pmatrix}6\\4\end{pmatrix}\"<\/p>\n\n\n\n

<\/p>\n\n\n\n

As a general formula:<\/p>\n\n\n\n

\"\boxed{P = C + \frac{AC\times AB}{AB \times CD}CD}\"<\/p>\n\n\n\n

The offset on \"CD\" can be negative or larger then one. In that case the intersection is on the extension of line segment \"CD\". This is an advantage of this method.<\/p>\n\n\n\n

Calculating the offset on segment \"AB\"<\/strong><\/p>\n\n\n\n

For the offset of \"P\" on \"AB\" we repeat the steps above.<\/p>\n\n\n\n

<\/p>\n\n\n\n

We know calculate the area as shown at image 5<\/p>\n\n\n\n

<\/p>\n\n\n\n

\"\"<\/a>
Image 5<\/figcaption><\/figure>\n\n\n\n

Which equals the area shown in image 6.<\/p>\n\n\n\n

\"\"<\/a>
Image 6<\/figcaption><\/figure>\n\n\n\n

\"AC\times CD = \begin{pmatrix}5\\1\end{pmatrix}\times\begin{pmatrix}-4\\4\end{pmatrix} = (5.4)-(1.-4) = 20-(-4) =24\"<\/p>\n\n\n\n

<\/p>\n\n\n\n

\"P = A + \frac{24}{36}AB \to P = A + \frac{2}{3}AB\"<\/p>\n\n\n\n

Let’s check whether it is correct<\/p>\n\n\n\n

\"P = A + \frac{2}{3}AB = \begin{pmatrix}2\\2\end{pmatrix} + \begin{pmatrix} \frac{2}{3}(6)\\ \frac{2}{3}3\end{pmatrix} = \begin{pmatrix}6\\4\end{pmatrix}\"<\/p>\n\n\n\n

As a general formula:<\/p>\n\n\n\n

\"\boxed{P = A + \frac{AC\times CD}{AB \times CD}AB}\" <\/p>\n\n\n\n

<\/p>\n\n\n\n

<\/p>\n\n\n\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

In this note I will explain how to find the intersection point P\u00a0 between two line segments. Note that this method will also calculate intersections on extended line segments. As a reminder the cross product is the area of the parallelogram enclosed by the two As a reminder, the cross product is the area of […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[102,103,82],"class_list":["post-352","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-geometry","tag-intersect","tag-vector"],"_links":{"self":[{"href":"https:\/\/thomas-jansen.eu\/index.php?rest_route=\/wp\/v2\/posts\/352","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/thomas-jansen.eu\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/thomas-jansen.eu\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/thomas-jansen.eu\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/thomas-jansen.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=352"}],"version-history":[{"count":36,"href":"https:\/\/thomas-jansen.eu\/index.php?rest_route=\/wp\/v2\/posts\/352\/revisions"}],"predecessor-version":[{"id":734,"href":"https:\/\/thomas-jansen.eu\/index.php?rest_route=\/wp\/v2\/posts\/352\/revisions\/734"}],"wp:attachment":[{"href":"https:\/\/thomas-jansen.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=352"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/thomas-jansen.eu\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=352"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/thomas-jansen.eu\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=352"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}