Table of Contents
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.
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 :
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.
Each time I implement a new feature, I like to create some minimum viable image that would not have been possible before.