Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 | import type { Types } from '@cornerstonejs/core';
import { vec2 } from 'gl-matrix';
import getSignedArea from './getSignedArea';
import {
EPSILON,
IntersectionDirection,
pointsAreEqual,
PolylineNodeType,
robustSegmentIntersection,
type AugmentedPolyNode,
type IntersectionInfo,
} from './robustSegmentIntersection';
import containsPoint from './containsPoint';
import arePolylinesIdentical from './arePolylinesIdentical';
export default function subtractPolylines(
targetPolylineCoords: Types.Point2[],
sourcePolylineCoordsInput: Types.Point2[]
): Types.Point2[][] {
if (targetPolylineCoords.length < 3) {
return [];
}
if (sourcePolylineCoordsInput.length < 3) {
return [targetPolylineCoords.slice()];
}
const sourcePolylineCoords = sourcePolylineCoordsInput.slice();
// Early detection for identical polylines
if (arePolylinesIdentical(targetPolylineCoords, sourcePolylineCoordsInput)) {
return []; // Subtracting identical polylines results in empty set
}
// 1. Ensure consistent winding for subtraction (e.g., target CCW, source CW)
const targetArea = getSignedArea(targetPolylineCoords);
const sourceArea = getSignedArea(sourcePolylineCoords);
// Assuming target is primary, source is subtractor.
// If target is CCW (positive area) and source is also CCW, reverse source.
// If target is CW (negative area) and source is also CW, reverse source.
// Essentially, they need opposite winding signs for subtraction.
if (
Math.sign(targetArea) === Math.sign(sourceArea) &&
Math.abs(sourceArea) > EPSILON
) {
sourcePolylineCoords.reverse();
}
// Early exit: Target contained in source (and no intersections)
// This check requires more robust `containsPoints` and `intersectPolyline`
// For now, we rely on the main algorithm to resolve this.
// 2. Find all intersections
const intersections: IntersectionInfo[] = [];
for (let i = 0; i < targetPolylineCoords.length; i++) {
const p1 = targetPolylineCoords[i];
const p2 = targetPolylineCoords[(i + 1) % targetPolylineCoords.length];
for (let j = 0; j < sourcePolylineCoords.length; j++) {
const q1 = sourcePolylineCoords[j];
const q2 = sourcePolylineCoords[(j + 1) % sourcePolylineCoords.length];
const intersectPt = robustSegmentIntersection(p1, p2, q1, q2);
if (intersectPt) {
const lenP = Math.sqrt(vec2.squaredDistance(p1, p2));
const lenQ = Math.sqrt(vec2.squaredDistance(q1, q2));
intersections.push({
coord: intersectPt,
seg1Idx: i,
seg2Idx: j,
alpha1:
lenP < EPSILON
? 0
: Math.sqrt(vec2.squaredDistance(p1, intersectPt)) / lenP,
alpha2:
lenQ < EPSILON
? 0
: Math.sqrt(vec2.squaredDistance(q1, intersectPt)) / lenQ,
});
}
}
}
// 3. Build augmented polylines (linked lists of AugmentedPolyNode)
const buildAugmentedList = (
polyCoords: Types.Point2[],
polyIndex: 0 | 1,
allIntersections: IntersectionInfo[]
): AugmentedPolyNode[] => {
const augmentedList: AugmentedPolyNode[] = [];
let nodeIdCounter = 0;
for (let i = 0; i < polyCoords.length; i++) {
const p1 = polyCoords[i];
// Add original vertex
augmentedList.push({
id: `${polyIndex}_v${nodeIdCounter++}`,
coordinates: p1,
type: PolylineNodeType.Vertex,
originalPolyIndex: polyIndex,
originalVertexIndex: i,
next: null,
prev: null, // To be filled
isIntersection: false,
visited: false,
});
// Find intersections on segment (p1, p_next)
const segmentIntersections = allIntersections
.filter(
(isect) => (polyIndex === 0 ? isect.seg1Idx : isect.seg2Idx) === i
)
.sort(
(a, b) =>
(polyIndex === 0 ? a.alpha1 : a.alpha2) -
(polyIndex === 0 ? b.alpha1 : b.alpha2)
);
for (const isect of segmentIntersections) {
// Avoid duplicate intersection points if alpha is very close
if (
augmentedList.length > 0 &&
pointsAreEqual(
augmentedList[augmentedList.length - 1].coordinates,
isect.coord
)
) {
if (!augmentedList[augmentedList.length - 1].isIntersection) {
// Promote vertex to intersection if coords match
augmentedList[augmentedList.length - 1].isIntersection = true;
augmentedList[augmentedList.length - 1].intersectionInfo = isect; // Store for pairing
augmentedList[augmentedList.length - 1].alpha =
polyIndex === 0 ? isect.alpha1 : isect.alpha2;
}
continue;
}
augmentedList.push({
id: `${polyIndex}_i${nodeIdCounter++}`,
coordinates: isect.coord,
type: PolylineNodeType.Intersection,
originalPolyIndex: polyIndex,
next: null,
prev: null, // To be filled
isIntersection: true,
visited: false,
alpha: polyIndex === 0 ? isect.alpha1 : isect.alpha2,
intersectionInfo: isect, // Temporary, for pairing
});
}
}
// Filter out duplicate consecutive points that might have arisen
const finalList: AugmentedPolyNode[] = [];
if (augmentedList.length > 0) {
finalList.push(augmentedList[0]);
for (let i = 1; i < augmentedList.length; i++) {
if (
!pointsAreEqual(
augmentedList[i].coordinates,
finalList[finalList.length - 1].coordinates
)
) {
finalList.push(augmentedList[i]);
} else {
// If points are same, merge intersection property
if (augmentedList[i].isIntersection) {
finalList[finalList.length - 1].isIntersection = true;
finalList[finalList.length - 1].intersectionInfo =
augmentedList[i].intersectionInfo;
finalList[finalList.length - 1].alpha = augmentedList[i].alpha;
}
}
}
}
// Link nodes
if (finalList.length > 0) {
for (let i = 0; i < finalList.length; i++) {
finalList[i].next = finalList[(i + 1) % finalList.length];
finalList[i].prev =
finalList[(i - 1 + finalList.length) % finalList.length];
}
}
return finalList;
};
const targetAugmented = buildAugmentedList(
targetPolylineCoords,
0,
intersections
);
const sourceAugmented = buildAugmentedList(
sourcePolylineCoords,
1,
intersections
);
// 4. Pair intersection nodes and classify direction
targetAugmented.forEach((tnode) => {
if (tnode.isIntersection) {
const tData = tnode.intersectionInfo as IntersectionInfo;
const partner = sourceAugmented.find(
(snode) =>
snode.isIntersection &&
pointsAreEqual(snode.coordinates, tnode.coordinates) &&
(snode.intersectionInfo as IntersectionInfo).seg1Idx ===
tData.seg1Idx && // Ensure it's the same geometric event
(snode.intersectionInfo as IntersectionInfo).seg2Idx === tData.seg2Idx
);
if (partner) {
tnode.partnerNode = partner;
partner.partnerNode = tnode;
// Classify direction: Target entering or exiting Source
const p_prev = tnode.prev.coordinates;
const p_curr = tnode.coordinates; // = partner.coordinates
const p_next_source = partner.next.coordinates; // Next point on (reversed) source
const v_target_arrival = vec2.subtract(
vec2.create(),
p_curr,
p_prev
) as Types.Point2;
const v_source_departure = vec2.subtract(
vec2.create(),
p_next_source,
p_curr
) as Types.Point2;
// This sign depends on:
// Target winding (assume CCW after normalization if any)
// Source winding (assume CW after normalization for subtraction)
// If target CCW, source CW:
// Positive cross product means target is turning "left" relative to source's path.
// If source is CW, its "inside" is to its right.
// If target turns left across source, it's entering.
// This needs careful geometric validation. A simpler check:
// Midpoint of tnode.prev -> tnode segment vs sourcePoly.
// Midpoint of tnode -> tnode.next segment vs sourcePoly.
const midPrevTargetSeg = [
(tnode.prev.coordinates[0] + tnode.coordinates[0]) / 2,
(tnode.prev.coordinates[1] + tnode.coordinates[1]) / 2,
];
// Use original source coordinates for point-in-polygon test, as sourceAugmented is already reversed.
const prevSegMidpointInsideSource = containsPoint(
sourcePolylineCoordsInput,
midPrevTargetSeg as Types.Point2
);
if (prevSegMidpointInsideSource) {
tnode.intersectionDir = IntersectionDirection.Exiting; // Was inside, now hitting boundary -> exiting
} else {
tnode.intersectionDir = IntersectionDirection.Entering; // Was outside, now hitting boundary -> entering
}
} else {
// console.warn("Unpaired intersection on target:", tnode.coordinates, tData);
// This can happen if robustSegmentIntersection is not perfect or due to precision
tnode.isIntersection = false; // Treat as vertex if no partner
}
}
});
// Clean up temporary data
targetAugmented.forEach((n) => delete n.intersectionInfo);
sourceAugmented.forEach((n) => delete n.intersectionInfo);
// 5. Trace result polygons
const resultPolylines: Types.Point2[][] = [];
for (let i = 0; i < targetAugmented.length; i++) {
const startNode = targetAugmented[i];
if (startNode.visited || startNode.isIntersection) {
continue;
}
// Start only from unvisited TARGET vertices.
// Check if this startNode of target is outside the original source polygon.
if (containsPoint(sourcePolylineCoordsInput, startNode.coordinates)) {
continue; // Skip if starting point is inside the subtraction area
}
const currentPathCoords: Types.Point2[] = [];
let currentNode: AugmentedPolyNode = startNode;
let onTargetList = true;
let safetyBreak = 0;
const maxIter = (targetAugmented.length + sourceAugmented.length) * 2;
do {
if (safetyBreak++ > maxIter) {
console.warn(
'Subtraction: Max iterations reached, possible infinite loop.'
);
break;
}
currentNode.visited = true;
// Add coordinate if different from last, to avoid duplicate points
if (
currentPathCoords.length === 0 ||
!pointsAreEqual(
currentPathCoords[currentPathCoords.length - 1],
currentNode.coordinates
)
) {
currentPathCoords.push(currentNode.coordinates);
}
if (currentNode.isIntersection) {
if (onTargetList) {
// Currently on target polyline's list
if (
currentNode.intersectionDir === IntersectionDirection.Entering &&
currentNode.partnerNode
) {
currentNode = currentNode.partnerNode; // Jump to source poly
onTargetList = false;
// Path continues from partnerNode, then its next.
}
// If Exiting or no partner, stay on target. Path continues from currentNode.next.
} else {
// Currently on source polyline's list
// Intersection on source means we must be switching back to target
if (currentNode.partnerNode) {
currentNode = currentNode.partnerNode; // Jump back to target poly
onTargetList = true;
// Path continues from partnerNode, then its next.
} else {
// Should not happen if graph is consistent. Stay on source.
console.warn(
'Subtraction: Intersection on source without partner.'
);
}
}
}
currentNode = currentNode.next; // Advance to next node on current list
} while (currentNode !== startNode || !onTargetList); // Loop until back to startNode on the target list
if (currentPathCoords.length >= 3) {
// Final check for self-intersection or degenerate path could be added here
// Remove last point if it's identical to the first (closing the loop)
if (
pointsAreEqual(
currentPathCoords[0],
currentPathCoords[currentPathCoords.length - 1]
)
) {
currentPathCoords.pop();
}
if (currentPathCoords.length >= 3) {
resultPolylines.push(currentPathCoords);
}
}
}
return resultPolylines;
}
|