Skip to content

Commit 28fb58b

Browse files
jasondaviesjasondavies
committed
Fix polygon clipping.
1 parent bc96647 commit 28fb58b

5 files changed

Lines changed: 208 additions & 97 deletions

File tree

‎d3.js‎

Lines changed: 79 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -5580,18 +5580,19 @@
55805580
}
55815581
function d3_geo_circleInterpolate(radians, precision) {
55825582
var cr = Math.cos(radians), sr = Math.sin(radians);
5583-
return function(from, to, context) {
5583+
return function(from, to, direction, context) {
5584+
var step = direction * precision;
55845585
from = from.angle;
55855586
to = to.angle;
55865587
if (from < to) from += 2 * Math.PI;
5587-
for (var step = precision, t = from; t > to; t -= step) {
5588+
for (var step = precision, t = from; direction > 0 ? t > to : t < to; t -= step) {
55885589
var c = Math.cos(t), s = Math.sin(t), point = d3_geo_circleSpherical([ cr, -sr * c, -sr * s ]);
55895590
context.lineTo(point[0], point[1]);
55905591
}
55915592
};
55925593
}
55935594
function d3_geo_circleClipPolygon(coordinates, context, clipLine, interpolate, angle) {
5594-
var unvisited = 0, intersections = [], segments = [], buffer = d3_geo_circleBufferSegments(clipLine), winding = 0;
5595+
var subject = [], clip = [], segments = [], buffer = d3_geo_circleBufferSegments(clipLine), winding = 0;
55955596
coordinates.forEach(function(ring) {
55965597
var x = buffer(ring, context), ringSegments = x[1];
55975598
winding += x[0];
@@ -5617,61 +5618,94 @@
56175618
winding.push(winding[0]);
56185619
}
56195620
segments.forEach(function(segment) {
5620-
var p0 = segment[0], p1 = segment[segment.length - 1];
5621+
var p0 = segment[0], p1 = segment[segment.length - 1], a, b;
56215622
if (p0[0] !== p1[0] || p0[1] !== p1[1]) {
5622-
var b = {
5623-
point: p1,
5624-
angle: angle(p1),
5625-
points: [],
5626-
other: null
5627-
}, a = {
5623+
a = {
56285624
point: p0,
5629-
angle: angle(p0),
56305625
points: segment,
5631-
other: b
5626+
other: null,
5627+
visited: false,
5628+
entry: true,
5629+
subject: true
5630+
};
5631+
b = {
5632+
point: p0,
5633+
angle: angle(p0),
5634+
points: [ p0 ],
5635+
other: a,
5636+
visited: false,
5637+
entry: false,
5638+
subject: false
5639+
};
5640+
a.other = b;
5641+
subject.push(a);
5642+
clip.push(b);
5643+
a = {
5644+
point: p1,
5645+
points: [ p1 ],
5646+
other: null,
5647+
visited: false,
5648+
entry: false,
5649+
subject: true
5650+
};
5651+
b = {
5652+
point: p1,
5653+
angle: angle(p1),
5654+
points: [ p1 ],
5655+
other: a,
5656+
visited: false,
5657+
entry: true,
5658+
subject: false
56325659
};
5633-
intersections.push(a, b);
5634-
unvisited++;
5660+
a.other = b;
5661+
subject.push(a);
5662+
clip.push(b);
56355663
} else {
56365664
var point = segment[0], n = segment.length - 1, i = 0;
56375665
context.moveTo(point[0], point[1]);
56385666
while (++i < n) context.lineTo((point = segment[i])[0], point[1]);
56395667
context.closePath();
56405668
}
56415669
});
5642-
if (!unvisited) return;
5643-
var start = intersections[0], tmp = null;
5644-
intersections.sort(function(a, b) {
5670+
clip.sort(function(a, b) {
56455671
return b.angle - a.angle;
56465672
});
5647-
for (var i = 0; i < intersections.length; ) {
5648-
intersections[i].next = intersections[++i % intersections.length];
5649-
}
5650-
while (unvisited) {
5651-
while (start.visited || !start.other) {
5652-
if (start === tmp) return;
5653-
start = start.next;
5673+
[ subject, clip ].forEach(function(intersections) {
5674+
for (var i = 0, a = intersections[0], b; i < intersections.length; ) {
5675+
a.next = b = intersections[++i % intersections.length];
5676+
b.prev = a;
5677+
a = b;
56545678
}
5655-
var intersection = start, moved = false, points, point;
5679+
});
5680+
if (!subject.length) return;
5681+
var start = subject[0], current, points, point;
5682+
while (1) {
5683+
current = start;
5684+
while (current.visited) if ((current = current.next) === start) return;
5685+
points = current.points;
5686+
context.moveTo((point = points.shift())[0], point[1]);
56565687
do {
5657-
if (!intersection.other) {
5658-
unvisited--;
5659-
break;
5688+
current.visited = current.other.visited = true;
5689+
if (current.entry) {
5690+
if (current.subject) {
5691+
for (var i = 0; i < points.length; i++) context.lineTo((point = points[i])[0], point[1]);
5692+
} else {
5693+
interpolate(current, current.next, 1, context);
5694+
}
5695+
current = current.next;
5696+
} else {
5697+
if (current.subject) {
5698+
points = current.prev.points;
5699+
for (var i = points.length; --i >= 0; ) context.lineTo((point = points[i])[0], point[1]);
5700+
} else {
5701+
interpolate(current, current.prev, -1, context);
5702+
}
5703+
current = current.prev;
56605704
}
5661-
intersection.visited = true;
5662-
point = (points = intersection.points)[0];
5663-
if (moved) context.lineTo(point[0], point[1]); else context.moveTo(point[0], point[1]),
5664-
moved = true;
5665-
for (var i = 1; i < points.length; i++) context.lineTo((point = points[i])[0], point[1]);
5666-
interpolate(intersection = intersection.other, intersection = intersection.next, context);
5667-
unvisited--;
5668-
} while (intersection !== start);
5669-
if (moved) {
5670-
context.closePath();
5671-
moved = false;
5672-
}
5673-
tmp = start;
5674-
start = start.next;
5705+
current = current.other;
5706+
points = current.points;
5707+
} while (!current.visited);
5708+
context.closePath();
56755709
}
56765710
}
56775711
function d3_geo_circleAngle(center) {
@@ -5741,7 +5775,7 @@
57415775
angle: -i * π / 2
57425776
}, {
57435777
angle: -(i + 1) * π / 2
5744-
}, context);
5778+
}, 1, context);
57455779
}
57465780
}
57475781
function d3_geo_compose(a, b) {
@@ -6235,11 +6269,11 @@
62356269
function d3_geo_antemeridianAngle(point) {
62366270
return -(point[0] < 0 ? point[1] - π / 2 : π / 2 - point[1]);
62376271
}
6238-
function d3_geo_antemeridianInterpolate(from, to, context) {
6272+
function d3_geo_antemeridianInterpolate(from, to, direction, context) {
62396273
from = from.point;
62406274
to = to.point;
62416275
if (Math.abs(from[0] - to[0]) > ε) {
6242-
var s = from[0] < to[0] ? π : -π, φ = s / 2;
6276+
var s = (from[0] < to[0] ? 1 : -1) * direction * π, φ = s / 2;
62436277
context.lineTo(-s, φ);
62446278
context.lineTo(0, φ);
62456279
context.lineTo(s, φ);

‎d3.min.js‎

Lines changed: 4 additions & 4 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎src/geo/circle.js‎

Lines changed: 59 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -135,11 +135,12 @@ function d3_geo_circleClip(degrees, rotate) {
135135
function d3_geo_circleInterpolate(radians, precision) {
136136
var cr = Math.cos(radians),
137137
sr = Math.sin(radians);
138-
return function(from, to, context) {
138+
return function(from, to, direction, context) {
139+
var step = direction * precision;
139140
from = from.angle;
140141
to = to.angle;
141142
if (from < to) from += 2 * Math.PI;
142-
for (var step = precision, t = from; t > to; t -= step) {
143+
for (var step = precision, t = from; direction > 0 ? t > to : t < to; t -= step) {
143144
var c = Math.cos(t),
144145
s = Math.sin(t),
145146
point = d3_geo_circleSpherical([
@@ -153,8 +154,8 @@ function d3_geo_circleInterpolate(radians, precision) {
153154
}
154155

155156
function d3_geo_circleClipPolygon(coordinates, context, clipLine, interpolate, angle) {
156-
var unvisited = 0, // number of unvisited entering intersections
157-
intersections = [],
157+
var subject = [],
158+
clip = [],
158159
segments = [],
159160
buffer = d3_geo_circleBufferSegments(clipLine),
160161
winding = 0;
@@ -183,18 +184,22 @@ function d3_geo_circleClipPolygon(coordinates, context, clipLine, interpolate, a
183184
d3_geo_circleInterpolateCircle(interpolate, x);
184185
winding.push(winding[0]);
185186
}
186-
// Create a circular linked list using the intersected segment start and
187-
// end points, sorted by relative angles.
188-
// TODO sort by angle first, then set in/out flags.
189187
segments.forEach(function(segment) {
190188
var p0 = segment[0],
191-
p1 = segment[segment.length - 1];
189+
p1 = segment[segment.length - 1],
190+
a,
191+
b;
192192
if (p0[0] !== p1[0] || p0[1] !== p1[1]) {
193-
var b = {point: p1, angle: angle(p1), points: [], other: null},
194-
a = {point: p0, angle: angle(p0), points: segment, other: b};
195-
//b.other = a;
196-
intersections.push(a, b);
197-
unvisited++;
193+
a = {point: p0, points: segment, other: null, visited: false, entry: true, subject: true};
194+
b = {point: p0, angle: angle(p0), points: [p0], other: a, visited: false, entry: false, subject: false};
195+
a.other = b;
196+
subject.push(a);
197+
clip.push(b);
198+
a = {point: p1, points: [p1], other: null, visited: false, entry: false, subject: true};
199+
b = {point: p1, angle: angle(p1), points: [p1], other: a, visited: false, entry: true, subject: false};
200+
a.other = b;
201+
subject.push(a);
202+
clip.push(b);
198203
} else {
199204
// TODO attach subsumed holes to the correct Polygons. For now, we can
200205
// add these as separate Polygons, since typically we draw everything
@@ -207,41 +212,49 @@ function d3_geo_circleClipPolygon(coordinates, context, clipLine, interpolate, a
207212
context.closePath();
208213
}
209214
});
210-
if (!unvisited) return;
211215
// Sort intersection points by relative angles.
212-
var start = intersections[0],
213-
tmp = null;
214-
intersections.sort(function(a, b) { return b.angle - a.angle; });
215-
// Construct circular linked list.
216-
for (var i = 0; i < intersections.length;) {
217-
intersections[i].next = intersections[++i % intersections.length];
218-
}
219-
while (unvisited) {
220-
// Look for unvisited entering intersections.
221-
while (start.visited || !start.other) {
222-
if (start === tmp) return;
223-
start = start.next;
216+
clip.sort(function(a, b) { return b.angle - a.angle; });
217+
// Construct circular linked lists.
218+
[subject, clip].forEach(function(intersections) {
219+
for (var i = 0, a = intersections[0], b; i < intersections.length;) {
220+
a.next = b = intersections[++i % intersections.length];
221+
b.prev = a;
222+
a = b;
224223
}
225-
var intersection = start,
226-
moved = false,
227-
points,
228-
point;
224+
});
225+
if (!subject.length) return;
226+
var start = subject[0],
227+
current,
228+
points,
229+
point;
230+
while (1) {
231+
// Find first unvisited intersection.
232+
current = start;
233+
while (current.visited) if ((current = current.next) === start) return;
234+
points = current.points;
235+
context.moveTo((point = points.shift())[0], point[1]);
229236
do {
230-
if (!intersection.other) { unvisited--; break; }
231-
intersection.visited = true;
232-
point = (points = intersection.points)[0];
233-
if (moved) context.lineTo(point[0], point[1]);
234-
else context.moveTo(point[0], point[1]), moved = true;
235-
for (var i = 1; i < points.length; i++) context.lineTo((point = points[i])[0], point[1]);
236-
interpolate(intersection = intersection.other, intersection = intersection.next, context);
237-
unvisited--;
238-
} while (intersection !== start);
239-
if (moved) {
240-
context.closePath();
241-
moved = false;
242-
}
243-
tmp = start;
244-
start = start.next;
237+
current.visited = current.other.visited = true;
238+
if (current.entry) {
239+
if (current.subject) {
240+
for (var i = 0; i < points.length; i++) context.lineTo((point = points[i])[0], point[1]);
241+
} else {
242+
interpolate(current, current.next, 1, context);
243+
}
244+
current = current.next;
245+
} else {
246+
if (current.subject) {
247+
points = current.prev.points;
248+
for (var i = points.length; --i >= 0;) context.lineTo((point = points[i])[0], point[1]);
249+
} else {
250+
interpolate(current, current.prev, -1, context);
251+
}
252+
current = current.prev;
253+
}
254+
current = current.other;
255+
points = current.points;
256+
} while (!current.visited);
257+
context.closePath();
245258
}
246259
}
247260

@@ -338,6 +351,6 @@ function d3_geo_circleWinding(p0, p) {
338351

339352
function d3_geo_circleInterpolateCircle(interpolate, context) {
340353
for (var i = 0; i < 4; i++) {
341-
interpolate({angle: -i * π / 2}, {angle: -(i + 1) * π / 2}, context);
354+
interpolate({angle: -i * π / 2}, {angle: -(i + 1) * π / 2}, 1, context);
342355
}
343356
}

‎src/geo/projection.js‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -245,11 +245,11 @@ function d3_geo_antemeridianAngle(point) {
245245
return -(point[0] < 0 ? point[1] - π / 2 : π / 2 - point[1]);
246246
}
247247

248-
function d3_geo_antemeridianInterpolate(from, to, context) {
248+
function d3_geo_antemeridianInterpolate(from, to, direction, context) {
249249
from = from.point;
250250
to = to.point;
251251
if (Math.abs(from[0] - to[0]) > ε) {
252-
var s = from[0] < to[0] ? π : -π,
252+
var s = (from[0] < to[0] ? 1 : -1) * direction * π,
253253
φ = s / 2;
254254
context.lineTo(-s, φ);
255255
context.lineTo( 0, φ);

0 commit comments

Comments
 (0)