Polygon clipping

The first test of a (very naive) algorithm used to calculate the visible parts of the line segments of a polygon that is (partly) occluded by other polygons.
The algorithm doesn't work well with edge cases (overlapping lines or polygons that share one or more vertices). I tried to come up with a function that would give me a set of non-overlapping lines, so I can draw the result directly with my plotter.

#polygons

```// Polygon clipping. Created by Reinder Nijhoff 2018
// @reindernijhoff
//
// https://turtletoy.net/turtle/348e597fd8
//

Canvas.setpenopacity(.5);

const turtle = new Turtle();
const num_polygons = 600;
const num_lines = 400;
const polygons = [];

function walk(i) {
const c = new Polygon();

if (i<num_polygons) {
c.createPoly(
Math.random()*200-100, Math.random()*200-100,
3+Math.floor(Math.random()*5), 3+4*Math.random(), 2*Math.random()*Math.PI);
} else {
c.createPoly(0, -500, 4, 400 + (i-num_polygons)/num_lines*500, Math.PI * .4);
}
let vis = true;
for (let i=0, l=polygons.length; i<l; i++) {
if(!c.diff(polygons[i])) {
vis = false;
break;
}
}
if (vis) {
c.draw(turtle);
polygons.push(c);
}
return i < num_polygons + num_lines -1;
}

function LineSegment(p1, p2) {
this.p1 = p1;
this.p2 = p2;
}

function Polygon() {
this.cp = []; // clip path: array of [x,y] pairs
this.dp = []; // 2d line to draw: array of linesegments
}

Polygon.prototype.genDrawPath = function() {
this.dp = [];
for (let i=0, l=this.cp.length; i<l; i++) {
this.dp.push(new LineSegment(this.cp[i], this.cp[(i+1)%l]));
}
}

Polygon.prototype.createPoly = function(x,y,c,r,a) {
this.cp = [];
for (let i=0; i<c; i++) {
this.cp.push( [x + Math.sin(i*Math.PI*2/c+a) * r, y + Math.cos(i*Math.PI*2/c+a) * r] );
}
this.genDrawPath();
}

Polygon.prototype.draw = function(t) {
if (this.dp.length ==0) {
return;
}
for (let i=0, l=this.dp.length; i<l; i++) {
const d = this.dp[i];
if (!vec2_equal(d.p1, t.pos())) {
t.penup();
t.goto(d.p1);
t.pendown();
}
t.goto(d.p2);
}
}

Polygon.prototype.inside = function(p) {
// find number of intersections from p to far away - if even you're outside
const p1 = [1000.1, 1000];
let int = 0;
for (let i=0, l=this.cp.length; i<l; i++) {
if (vec2_find_segment_intersect(p, p1, this.cp[i], this.cp[(i+1)%l])) {
int ++;
}
}
return int & 1;
}

// very naive polygon diff algorithm - made this up myself
Polygon.prototype.diff = function(p) {
const ndp = [];
for (let i=0, l=this.dp.length; i<l; i++) {
const ls = this.dp[i];

// find all intersections with clip path
const int = [];
for (let j=0, cl=p.cp.length; j<cl; j++) {
const pint = vec2_find_segment_intersect(ls.p1,ls.p2,p.cp[j],p.cp[(j+1)%cl]);
if (pint) {
int.push(pint);
}
}
if (int.length == 0) { // 0 intersections, inside or outside?
if (!p.inside(ls.p1)) {
ndp.push(ls);
}
} else {
int.push(ls.p1);
int.push(ls.p2);
// order intersection points on line ls.p1 to ls.p2
const cmp = [ls.p2[0]-ls.p1[0], ls.p2[1]-ls.p1[1]];
int.sort( (a,b) => {
const db = vec2_dot([b[0]-ls.p1[0], b[1]-ls.p1[1]], cmp);
const da = vec2_dot([a[0]-ls.p1[0], a[1]-ls.p1[1]], cmp);
return da - db;
});
for (let j=0; j<int.length-1; j++) {
if (!p.inside([(int[j][0]+int[j+1][0])/2,(int[j][1]+int[j+1][1])/2])) {
if (!vec2_equal(int[j], int[j+1])) {
ndp.push(new LineSegment(int[j], int[j+1]));
}
}
}
}
}
this.dp = ndp;
return this.dp.length > 0;
}

// vec2 functions
function vec2_equal(a,b) {
return vec2_dist_sqr(a,b) < 0.001;
}

function vec2_dot(a, b) {
return a[0]*b[0]+a[1]*b[1];
}

function vec2_dist_sqr(a, b) {
return (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]);
}

//port of http://paulbourke.net/geometry/pointlineplane/Helpers.cs
function vec2_find_segment_intersect(l1p1, l1p2, l2p1, l2p2){
// Denominator for ua and ub are the same, so store this calculation
const d = (l2p2[1] - l2p1[1]) * (l1p2[0] - l1p1[0]) - (l2p2[0] - l2p1[0]) * (l1p2[1] - l1p1[1]);

//n_a and n_b are calculated as seperate values for readability
const n_a = (l2p2[0] - l2p1[0]) * (l1p1[1] - l2p1[1]) - (l2p2[1] - l2p1[1]) * (l1p1[0] - l2p1[0]);

const n_b = (l1p2[0] - l1p1[0]) * (l1p1[1] - l2p1[1]) - (l1p2[1] - l1p1[1]) * (l1p1[0] - l2p1[0]);

// Make sure there is not a division by zero - this also indicates that
// the lines are parallel.
// If n_a and n_b were both equal to zero the lines would be on top of each
// other (coincidental).  This check is not done because it is not
// necessary for this implementation (the parallel check accounts for this).
if (d == 0) {
return false;
}

// Calculate the intermediate fractional point that the lines potentially intersect.
const ua = n_a / d;
const ub = n_b / d;

// The fractional point will be between 0 and 1 inclusive if the lines
// intersect.  If the fractional calculation is larger than 1 or smaller
// than 0 the lines would need to be longer to intersect.
if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) {
return [l1p1[0] + (ua * (l1p2[0] - l1p1[0])), l1p1[1] + (ua * (l1p2[1] - l1p1[1])) ];
}
return false;
}```