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
|
import {
vectorCross,
vectorFromPoint,
type GlobalPoint,
type LocalPoint,
} from "@excalidraw/math";
import type { Bounds } from "@excalidraw/excalidraw/element/bounds";
export type LineSegment<P extends LocalPoint | GlobalPoint> = [P, P];
export function getBBox<P extends LocalPoint | GlobalPoint>(
line: LineSegment<P>,
): Bounds {
return [
Math.min(line[0][0], line[1][0]),
Math.min(line[0][1], line[1][1]),
Math.max(line[0][0], line[1][0]),
Math.max(line[0][1], line[1][1]),
];
}
export function doBBoxesIntersect(a: Bounds, b: Bounds) {
return a[0] <= b[2] && a[2] >= b[0] && a[1] <= b[3] && a[3] >= b[1];
}
const EPSILON = 0.000001;
export function isPointOnLine<P extends GlobalPoint | LocalPoint>(
l: LineSegment<P>,
p: P,
) {
const p1 = vectorFromPoint(l[1], l[0]);
const p2 = vectorFromPoint(p, l[0]);
const r = vectorCross(p1, p2);
return Math.abs(r) < EPSILON;
}
export function isPointRightOfLine<P extends GlobalPoint | LocalPoint>(
l: LineSegment<P>,
p: P,
) {
const p1 = vectorFromPoint(l[1], l[0]);
const p2 = vectorFromPoint(p, l[0]);
return vectorCross(p1, p2) < 0;
}
export function isLineSegmentTouchingOrCrossingLine<
P extends GlobalPoint | LocalPoint,
>(a: LineSegment<P>, b: LineSegment<P>) {
return (
isPointOnLine(a, b[0]) ||
isPointOnLine(a, b[1]) ||
(isPointRightOfLine(a, b[0])
? !isPointRightOfLine(a, b[1])
: isPointRightOfLine(a, b[1]))
);
}
// https://martin-thoma.com/how-to-check-if-two-line-segments-intersect/
export function doLineSegmentsIntersect<P extends GlobalPoint | LocalPoint>(
a: LineSegment<P>,
b: LineSegment<P>,
) {
return (
doBBoxesIntersect(getBBox(a), getBBox(b)) &&
isLineSegmentTouchingOrCrossingLine(a, b) &&
isLineSegmentTouchingOrCrossingLine(b, a)
);
}
|
