| 1 | // Clipping of segments and polylines to travel bounds (ports of
|
| 2 | // plot_utils.clip_segment and nextdrawcore/boundsclip.clip_at_bounds).
|
| 3 | // Bounds are [[xMin, yMin], [xMax, yMax]].
|
| 4 |
|
| 5 | function clipCode(x, y, xMin, xMax, yMin, yMax) {
|
| 6 | let code = 0;
|
| 7 | if (x < xMin) code |= 1;
|
| 8 | else if (x > xMax) code |= 2;
|
| 9 | if (y < yMin) code |= 4;
|
| 10 | else if (y > yMax) code |= 8;
|
| 11 | return code;
|
| 12 | }
|
| 13 |
|
| 14 | /**
|
| 15 | * Cohen–Sutherland clip of [[x1, y1], [x2, y2]] to bounds.
|
| 16 | * Returns [accept, clippedSegment].
|
| 17 | */
|
| 18 | export function clipSegment(segment, bounds) {
|
| 19 | let [[x1, y1], [x2, y2]] = segment;
|
| 20 | const [[xMin, yMin], [xMax, yMax]] = bounds;
|
| 21 | for (let iterations = 0; ; iterations++) {
|
| 22 | const code1 = clipCode(x1, y1, xMin, xMax, yMin, yMax);
|
| 23 | const code2 = clipCode(x2, y2, xMin, xMax, yMin, yMax);
|
| 24 | if (code1 === 0 && code2 === 0) return [true, segment];
|
| 25 | if (code1 & code2) return [false, segment];
|
| 26 | if (iterations > 3) return [true, segment]; // Failsafe near precision limits
|
| 27 | const code = code1 !== 0 ? code1 : code2;
|
| 28 | let xNew, yNew;
|
| 29 | if (code & 1) {
|
| 30 | xNew = xMin;
|
| 31 | yNew = (y2 - y1) / (x2 - x1) * (xMin - x1) + y1;
|
| 32 | } else if (code & 2) {
|
| 33 | xNew = xMax;
|
| 34 | yNew = (y2 - y1) / (x2 - x1) * (xMax - x1) + y1;
|
| 35 | } else if (code & 4) {
|
| 36 | yNew = yMin;
|
| 37 | xNew = (x2 - x1) / (y2 - y1) * (yMin - y1) + x1;
|
| 38 | } else {
|
| 39 | yNew = yMax;
|
| 40 | xNew = (x2 - x1) / (y2 - y1) * (yMax - y1) + x1;
|
| 41 | }
|
| 42 | if (code === code1) {
|
| 43 | x1 = xNew;
|
| 44 | y1 = yNew;
|
| 45 | } else {
|
| 46 | x2 = xNew;
|
| 47 | y2 = yNew;
|
| 48 | }
|
| 49 | segment = [[x1, y1], [x2, y2]];
|
| 50 | }
|
| 51 | }
|
| 52 |
|
| 53 | export function pointInBounds([x, y], [[xMin, yMin], [xMax, yMax]], tol = 1e-9) {
|
| 54 | return !(x < xMin - tol || y < yMin - tol || x > xMax + tol || y > yMax + tol);
|
| 55 | }
|
| 56 |
|
| 57 | export function pointsNear(a, b, squaredTol) {
|
| 58 | const dx = a[0] - b[0];
|
| 59 | const dy = a[1] - b[1];
|
| 60 | return dx * dx + dy * dy < squaredTol;
|
| 61 | }
|
| 62 |
|
| 63 | /**
|
| 64 | * Split a polyline into the pieces that lie inside bounds. Returns
|
| 65 | * { paths, outOfBounds } where outOfBounds is true if any vertex exceeded
|
| 66 | * the positive travel limits by more than warnTol.
|
| 67 | */
|
| 68 | export function clipPolyline(vertices, bounds, warnTol = 0) {
|
| 69 | const [xMax, yMax] = bounds[1];
|
| 70 | let outOfBounds = false;
|
| 71 | const paths = [];
|
| 72 | let current = [];
|
| 73 | let prev = null;
|
| 74 | let prevIn = false;
|
| 75 | for (const vertex of vertices) {
|
| 76 | let inBounds = pointInBounds(vertex, bounds, 0);
|
| 77 | if (!inBounds && (vertex[0] > xMax + warnTol || vertex[1] > yMax + warnTol)) outOfBounds = true;
|
| 78 | if (prev == null) {
|
| 79 | if (inBounds) current.push(vertex);
|
| 80 | } else if (inBounds && prevIn) {
|
| 81 | current.push(vertex);
|
| 82 | } else {
|
| 83 | const [accept, seg] = clipSegment([prev, vertex], bounds);
|
| 84 | if (accept) {
|
| 85 | if (inBounds && !prevIn) {
|
| 86 | if (current.length) paths.push(current);
|
| 87 | current = [[seg[0][0], seg[0][1]], [seg[1][0], seg[1][1]]];
|
| 88 | }
|
| 89 | if (prevIn && !inBounds) {
|
| 90 | current.push([seg[1][0], seg[1][1]]);
|
| 91 | paths.push(current);
|
| 92 | current = [];
|
| 93 | }
|
| 94 | if (!prevIn && !inBounds) {
|
| 95 | if (current.length) paths.push(current);
|
| 96 | paths.push([[seg[0][0], seg[0][1]], [seg[1][0], seg[1][1]]]);
|
| 97 | current = [];
|
| 98 | }
|
| 99 | } else {
|
| 100 | inBounds = false;
|
| 101 | }
|
| 102 | }
|
| 103 | prev = vertex;
|
| 104 | prevIn = inBounds;
|
| 105 | }
|
| 106 | if (current.length) paths.push(current);
|
| 107 | return { paths, outOfBounds };
|
| 108 | }
|