Janady13/thatdeveloperguy-website / tools/svg/geometry.ts

1import fitCurve from 'fit-curve'; 2import polygonClipping from 'polygon-clipping'; 3import type { Point, Ring } from './model.ts'; 4 5export type Cubic = { c1: Point; c2: Point; to: Point }; 6export interface Contour { start: Point; segments: Cubic[] } 7 8export function ringArea(ring: Ring): number { 9 let area = 0; 10 for (let i = 0; i < ring.length; i++) { 11 const [x1, y1] = ring[i]!; const [x2, y2] = ring[(i + 1) % ring.length]!; 12 area += x1 * y2 - x2 * y1; 13 } 14 return area / 2; 15} 16 17/** Union of rings that share one paint. polygon-clipping returns exteriors and holes with opposite winding, which the nonzero fill rule renders correctly. */ 18export function unionRings(rings: Ring[]): Ring[] { 19 if (rings.length <= 1) return rings; 20 const polygons = rings.map(ring => [ring.map(p => [p[0], p[1]] as [number, number])]); 21 const result = polygonClipping.union(polygons[0]!, ...polygons.slice(1)); 22 const out: Ring[] = []; 23 for (const polygon of result) for (const ring of polygon) { 24 const pts = ring.map(p => [p[0], p[1]] as Point); 25 if (pts.length > 1 && pts[0]![0] === pts[pts.length - 1]![0] && pts[0]![1] === pts[pts.length - 1]![1]) pts.pop(); 26 if (pts.length >= 3) out.push(pts); 27 } 28 return out; 29} 30 31function turn(a: Point, b: Point, c: Point): number { 32 const v1x = b[0] - a[0], v1y = b[1] - a[1], v2x = c[0] - b[0], v2y = c[1] - b[1]; 33 const l1 = Math.hypot(v1x, v1y), l2 = Math.hypot(v2x, v2y); 34 if (l1 === 0 || l2 === 0) return 0; 35 const cos = Math.min(1, Math.max(-1, (v1x * v2x + v1y * v2y) / (l1 * l2))); 36 return Math.acos(cos) * 180 / Math.PI; 37} 38 39function pointLineDistance(p: Point, a: Point, b: Point): number { 40 const dx = b[0] - a[0], dy = b[1] - a[1]; 41 const len2 = dx * dx + dy * dy; 42 if (len2 === 0) return Math.hypot(p[0] - a[0], p[1] - a[1]); 43 const t = Math.max(0, Math.min(1, ((p[0] - a[0]) * dx + (p[1] - a[1]) * dy) / len2)); 44 return Math.hypot(p[0] - (a[0] + t * dx), p[1] - (a[1] + t * dy)); 45} 46 47function douglasPeucker(points: Point[], epsilon: number): Point[] { 48 if (points.length <= 2) return points; 49 let index = 0, max = 0; 50 const a = points[0]!, b = points[points.length - 1]!; 51 for (let i = 1; i < points.length - 1; i++) { const d = pointLineDistance(points[i]!, a, b); if (d > max) { max = d; index = i; } } 52 if (max <= epsilon) return [a, b]; 53 const left = douglasPeucker(points.slice(0, index + 1), epsilon), right = douglasPeucker(points.slice(index), epsilon); 54 return left.slice(0, -1).concat(right); 55} 56 57/** Douglas-Peucker on a closed ring: split at the two points farthest apart so the pixel staircase collapses to its straight and curved runs. */ 58export function simplifyRing(ring: Ring, epsilon: number): Ring { 59 if (ring.length <= 4) return ring; 60 let i0 = 0, i1 = 0, far = -1; 61 for (let i = 0; i < ring.length; i++) { const p = ring[i]!, d = Math.hypot(p[0] - ring[0]![0], p[1] - ring[0]![1]); if (d > far) { far = d; i1 = i; } } 62 far = -1; 63 for (let i = 0; i < ring.length; i++) { const p = ring[i]!, d = Math.hypot(p[0] - ring[i1]![0], p[1] - ring[i1]![1]); if (d > far) { far = d; i0 = i; } } 64 if (i0 > i1) [i0, i1] = [i1, i0]; 65 const first = douglasPeucker(ring.slice(i0, i1 + 1), epsilon); 66 const second = douglasPeucker(ring.slice(i1).concat(ring.slice(0, i0 + 1)), epsilon); 67 const out = first.slice(0, -1).concat(second.slice(0, -1)); 68 return out.length >= 3 ? out : ring; 69} 70 71/** Indices where the polyline turns more than `minTurnDeg`; those stay sharp through fitting. */ 72export function cornerIndices(ring: Ring, minTurnDeg: number): number[] { 73 const out: number[] = []; 74 const n = ring.length; 75 for (let i = 0; i < n; i++) { 76 const a = ring[(i - 1 + n) % n]!, b = ring[i]!, c = ring[(i + 1) % n]!; 77 if (turn(a, b, c) >= minTurnDeg) out.push(i); 78 } 79 return out; 80} 81 82/** fit-curve measures error only at sample points, so a sparse polyline lets a cubic bulge between them. Resample every `step` px first. */ 83export function densify(points: Point[], step: number): Point[] { 84 const out: Point[] = []; 85 for (let i = 0; i < points.length - 1; i++) { 86 const a = points[i]!, b = points[i + 1]!; 87 const len = Math.hypot(b[0] - a[0], b[1] - a[1]); 88 const n = Math.max(1, Math.ceil(len / step)); 89 for (let k = 0; k < n; k++) out.push([a[0] + (b[0] - a[0]) * k / n, a[1] + (b[1] - a[1]) * k / n]); 90 } 91 out.push(points[points.length - 1]!); 92 return out; 93} 94 95function fitOpen(sparse: Point[], tolerance: number): Cubic[] { 96 if (sparse.length < 2) return []; 97 if (sparse.length === 2) { const [a, b] = sparse as [Point, Point]; return [{ c1: a, c2: b, to: b }]; } 98 const points = densify(sparse, 2); 99 const curves = fitCurve(points.map(p => [p[0], p[1]]), tolerance); 100 return curves.map(c => ({ c1: [c[1]![0]!, c[1]![1]!], c2: [c[2]![0]!, c[2]![1]!], to: [c[3]![0]!, c[3]![1]!] })); 101} 102 103/** Schneider fitting per corner-to-corner run. A ring with no corners is fitted as one closed run starting at index 0. */ 104export function fitRing(source: Ring, tolerance: number, minTurnDeg: number): Contour { 105 const ring = simplifyRing(source, tolerance); 106 const n = ring.length; 107 const corners = cornerIndices(ring, minTurnDeg); 108 const anchors = corners.length ? corners : [0]; 109 const start = ring[anchors[0]!]!; 110 const segments: Cubic[] = []; 111 for (let k = 0; k < anchors.length; k++) { 112 const from = anchors[k]!, to = anchors[(k + 1) % anchors.length]!; 113 const run: Point[] = []; 114 let i = from; 115 do { run.push(ring[i]!); i = (i + 1) % n; } while (i !== to); 116 run.push(ring[to]!); 117 if (anchors.length === 1) run[run.length - 1] = ring[from]!; // closed run back to its own start 118 segments.push(...fitOpen(run, tolerance)); 119 } 120 return { start, segments }; 121} 122 123export function contourVertexCount(contour: Contour): number { return 1 + contour.segments.length; } 124