Table of Contents
Motivation
At the time of writing this, , 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
and
defined by their start and end points.
This gives rise to parametric equations
which for
define the points on each line.
We're looking for
such that
.
Solving once for
and once for
:
Combining
For cosmetic reasons, we can reorder this so
comes before
and
smaller indices before larger ones.
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
too.
If both
, 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.
