Line-Line Intersection

math

Table of Contents

Motivation

At the time of writing this, [2022-11-24 Thu] , I had set myself the task of implementing line-polygon clipping for my new plotter art framework but found that my Internet connection didn't work.

As a challenge, I set out to come up with a solution myself. In any case, it will be useful to have this information written down for the next time I need it.

Line-Line Intersection

A basic fact of Euclidean Geometry is that two lines (extended infinitely) are either parallel or will intersect in some point.

Consider two lines line-line_intersection_a7219853942ce88ed25fe3c6e4058fb5ba53d047.svg and line-line_intersection_d79b4af7542c228bbc7933642acb361f00580541.svg defined by their start and end points.

This gives rise to parametric equations which for line-line_intersection_e0eccef32f0fd6ab1f277579993e66a71a5b7d89.svg define the points on each line.

  • line-line_intersection_28e0a5ee5f56ec7eca550f22cafb0538ad2fc6df.svg
  • line-line_intersection_7396aee8ec6fb02a16e5bcedbd31a02c56824968.svg

We're looking for line-line_intersection_f8f891679f1e5906103e87e0fe2d61344e5321a5.svg such that line-line_intersection_f6154fff20df4cd92a90ee93d680b77733c100db.svg .

line-line_intersection_8eac5e1cab8818eb8e5ee74dbdc422d3d314c15b.svg

Solving once for line-line_intersection_5727d123e10da8480221384e94fb64bf87cd3591.svg and once for line-line_intersection_08dda2173ea3f7521d5c596dbd1890e6cda71e8b.svg :

line-line_intersection_a395f181d8176c528c9dd93b9e5584c270467bf8.svg
line-line_intersection_75235f19c9a6ef572c46af7c53394cead160bc6b.svg

Combining

line-line_intersection_4fb1313a45ec2d457c9a7fb8ea0da9ba40fa6e20.svg

For cosmetic reasons, we can reorder this so line-line_intersection_8b9a519c9b49c75c81ef93a0446189f241f48d6b.svg comes before line-line_intersection_23fcefdd894d4a955916950d5ea1bbaf9396b29a.svg and smaller indices before larger ones.

line-line_intersection_c716a72fae642544cbf4d88708d75b53fb6e2104.svg

If the lines are parallel, the denominator will be zero and there are either no or infinitely many intersection points.

To make sure the intersection point lies inside both lines, we'll need to calculate line-line_intersection_08dda2173ea3f7521d5c596dbd1890e6cda71e8b.svg too.

line-line_intersection_d2042f6f4a49736478f3874b531cee2c4c78489b.svg

If both line-line_intersection_c8bc73ef2a0bb41b249e529a7b969e38e001ee05.svg , we know the intersection point is part of both lines.

Test Image

Each time I implement a new feature, I like to create some minimum viable image that would not have been possible before.

line_intersection.svg

If you have an idea how this page could be improved or a comment send me a mail.