PolygonCut

75mm Returns a vector with the vertices of a polygon with everything to the left of the line going from s to e cut away. 15mm

13 lines tested but not extensively

Usage: vector<P> p = ...; p = polygonCut(p, P(0,0), P(1,0));

Needs: "Point.h"

content/geometry/PolygonCut.h — Ulf Lundstrom

typedef Point<double> P;
vector<P> polygonCut(const vector<P>& poly, P s, P e) {
	vector<P> res;
	rep(i,0,sz(poly)) {
		P cur = poly[i], prev = i ? poly[i-1] : poly.back();
		auto a = s.cross(e, cur), b = s.cross(e, prev);
		if ((a < 0) != (b < 0))
			res.push_back(cur + (prev - cur) * (a / (a - b)));
		if (a < 0)
			res.push_back(cur);
	}
	return res;
}