-
Notifications
You must be signed in to change notification settings - Fork 25
/
index.js
124 lines (87 loc) · 3.28 KB
/
index.js
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
'use strict';
module.exports = lineclip;
module.exports.default = lineclip;
lineclip.polyline = lineclip;
lineclip.polygon = polygonclip;
// Cohen-Sutherland line clippign algorithm, adapted to efficiently
// handle polylines rather than just segments
function lineclip(points, bbox, result) {
var len = points.length,
codeA = bitCode(points[0], bbox),
part = [],
i, a, b, codeB, lastCode;
if (!result) result = [];
for (i = 1; i < len; i++) {
a = points[i - 1];
b = points[i];
codeB = lastCode = bitCode(b, bbox);
while (true) {
if (!(codeA | codeB)) { // accept
part.push(a);
if (codeB !== lastCode) { // segment went outside
part.push(b);
if (i < len - 1) { // start a new line
result.push(part);
part = [];
}
} else if (i === len - 1) {
part.push(b);
}
break;
} else if (codeA & codeB) { // trivial reject
break;
} else if (codeA) { // a outside, intersect with clip edge
a = intersect(a, b, codeA, bbox);
codeA = bitCode(a, bbox);
} else { // b outside
b = intersect(a, b, codeB, bbox);
codeB = bitCode(b, bbox);
}
}
codeA = lastCode;
}
if (part.length) result.push(part);
return result;
}
// Sutherland-Hodgeman polygon clipping algorithm
function polygonclip(points, bbox) {
var result, edge, prev, prevInside, i, p, inside;
// clip against each side of the clip rectangle
for (edge = 1; edge <= 8; edge *= 2) {
result = [];
prev = points[points.length - 1];
prevInside = !(bitCode(prev, bbox) & edge);
for (i = 0; i < points.length; i++) {
p = points[i];
inside = !(bitCode(p, bbox) & edge);
// if segment goes through the clip window, add an intersection
if (inside !== prevInside) result.push(intersect(prev, p, edge, bbox));
if (inside) result.push(p); // add a point if it's inside
prev = p;
prevInside = inside;
}
points = result;
if (!points.length) break;
}
return result;
}
// intersect a segment against one of the 4 lines that make up the bbox
function intersect(a, b, edge, bbox) {
return edge & 8 ? [a[0] + (b[0] - a[0]) * (bbox[3] - a[1]) / (b[1] - a[1]), bbox[3]] : // top
edge & 4 ? [a[0] + (b[0] - a[0]) * (bbox[1] - a[1]) / (b[1] - a[1]), bbox[1]] : // bottom
edge & 2 ? [bbox[2], a[1] + (b[1] - a[1]) * (bbox[2] - a[0]) / (b[0] - a[0])] : // right
edge & 1 ? [bbox[0], a[1] + (b[1] - a[1]) * (bbox[0] - a[0]) / (b[0] - a[0])] : null; // left
}
// bit code reflects the point position relative to the bbox:
// left mid right
// top 1001 1000 1010
// mid 0001 0000 0010
// bottom 0101 0100 0110
function bitCode(p, bbox) {
var code = 0;
if (p[0] < bbox[0]) code |= 1; // left
else if (p[0] > bbox[2]) code |= 2; // right
if (p[1] < bbox[1]) code |= 4; // bottom
else if (p[1] > bbox[3]) code |= 8; // top
return code;
}