Skip to content

Commit cba8a77

Browse files
jasondaviesjasondavies
committed
Improve Polygon clipping.
1. We no longer perform an equality check on GeoJSON polygon endpoints, since we know that the first and last points should be equal. 2. However, there are special cases where a polygon just touches the clip edge, generating two coincident intersection points. Here we avoid generating a coincident point, and continue as normal. 3. Another special case is where we have coincident intersection points e.g. due to a self-intersecting polygon. Here we continue calculating the winding number as if this is a closed polygon (so we know whether to insert a polygon around the whole clip edge).
1 parent 28fb58b commit cba8a77

5 files changed

Lines changed: 177 additions & 133 deletions

File tree

‎d3.js‎

Lines changed: 82 additions & 75 deletions
Original file line numberDiff line numberDiff line change
@@ -5546,26 +5546,38 @@
55465546
}
55475547
function clipLine(coordinates, context, winding) {
55485548
if (!(n = coordinates.length)) return;
5549-
var point0 = rotate(coordinates[0]), inside = visible(point0), keepWinding = winding != null, n;
5550-
if (inside) context.moveTo(point0[0], point0[1]);
5549+
var point0 = rotate(coordinates[0]), point2, inside = visible(point0), keepWinding = winding != null, closed = keepWinding && inside, n, move0, line0;
5550+
if (inside) context.moveTo((move0 = point0)[0], point0[1]);
55515551
for (var i = 1; i < n; i++) {
55525552
var point1 = rotate(coordinates[i]), v = visible(point1);
55535553
if (v !== inside) {
5554-
keepWinding = false;
55555554
if (inside = v) {
5556-
point0 = intersect(point1, point0);
5557-
context.moveTo(point0[0], point0[1]);
5555+
point2 = intersect(point1, point0);
5556+
if (!line0 || Math.abs(line0[0] - point2[0]) > ε || Math.abs(line0[1] - point2[1]) > ε) {
5557+
if (move0) keepWinding = false;
5558+
context.moveTo((move0 = point2)[0], point2[1]);
5559+
}
5560+
if (keepWinding) winding += d3_geo_circleWinding(point2, point1);
5561+
point0 = point2;
55585562
} else {
5559-
point0 = intersect(point0, point1);
5560-
context.lineTo(point0[0], point0[1]);
5563+
line0 = point2 = intersect(point0, point1);
5564+
context.lineTo(point2[0], point2[1]);
5565+
if (keepWinding) {
5566+
if (Math.abs(move0[0] - point2[0]) > ε || Math.abs(move0[1] - point2[1]) > ε) {
5567+
keepWinding = false;
5568+
} else {
5569+
winding += d3_geo_circleWinding(point0, move0);
5570+
}
5571+
}
5572+
point0 = point2;
55615573
}
5562-
} else if (keepWinding) {
5563-
winding += d3_geo_circleWinding(point0, point1);
55645574
}
5575+
if (keepWinding) winding += d3_geo_circleWinding(point0, point1);
55655576
if (v) context.lineTo(point1[0], point1[1]);
55665577
point0 = point1;
55675578
}
5568-
return keepWinding && winding;
5579+
if (closed && v) context.closePath();
5580+
return keepWinding && (!move0 || Math.abs(move0[0] - point0[0]) < ε && Math.abs(move0[1] - point0[1]) < ε) && winding;
55695581
}
55705582
function intersect(a, b) {
55715583
var pa = d3_geo_circleCartesian(a, [ 0, 0, 0 ]), pb = d3_geo_circleCartesian(b, [ 0, 0, 0 ]);
@@ -5584,88 +5596,79 @@
55845596
var step = direction * precision;
55855597
from = from.angle;
55865598
to = to.angle;
5587-
if (from < to) from += 2 * Math.PI;
5599+
if (from < to) from += 2 * π;
55885600
for (var step = precision, t = from; direction > 0 ? t > to : t < to; t -= step) {
55895601
var c = Math.cos(t), s = Math.sin(t), point = d3_geo_circleSpherical([ cr, -sr * c, -sr * s ]);
55905602
context.lineTo(point[0], point[1]);
55915603
}
55925604
};
55935605
}
55945606
function d3_geo_circleClipPolygon(coordinates, context, clipLine, interpolate, angle) {
5595-
var subject = [], clip = [], segments = [], buffer = d3_geo_circleBufferSegments(clipLine), winding = 0;
5607+
var subject = [], clip = [], segments = [], buffer = d3_geo_circleBufferSegments(clipLine), winding = 0, count = 0;
55965608
coordinates.forEach(function(ring) {
55975609
var x = buffer(ring, context), ringSegments = x[1];
55985610
winding += x[0];
55995611
var n = ringSegments.length;
5600-
if (n > 1) {
5601-
var firstSegment = ringSegments[0], lastSegment = ringSegments[n - 1], p0 = firstSegment[0], p1 = lastSegment[lastSegment.length - 1];
5602-
if (p0[0] === p1[0] && p0[1] === p1[1]) {
5603-
ringSegments.shift();
5604-
ringSegments.pop();
5605-
ringSegments.push(lastSegment.concat(firstSegment));
5606-
}
5612+
if (!n) return;
5613+
count += n;
5614+
if (x[0] !== false) {
5615+
var segment = ringSegments[0], point = segment[0], n = segment.length - 1, i = 0;
5616+
context.moveTo(point[0], point[1]);
5617+
while (++i < n) context.lineTo((point = segment[i])[0], point[1]);
5618+
context.closePath();
5619+
return;
56075620
}
56085621
segments = segments.concat(ringSegments);
56095622
});
5610-
if (segments.length ? winding > 0 : winding < 0) {
5611-
segments.push(winding = []);
5612-
x = {
5623+
if (count ? winding > 0 : winding < 0) {
5624+
var moved = false;
5625+
d3_geo_circleInterpolateCircle(interpolate, {
56135626
lineTo: function(x, y) {
5614-
winding.push([ x, y ]);
5627+
(moved ? context.lineTo : (moved = true, context.moveTo))(x, y);
56155628
}
5616-
};
5617-
d3_geo_circleInterpolateCircle(interpolate, x);
5618-
winding.push(winding[0]);
5629+
});
5630+
context.closePath();
56195631
}
56205632
segments.forEach(function(segment) {
5621-
var p0 = segment[0], p1 = segment[segment.length - 1], a, b;
5622-
if (p0[0] !== p1[0] || p0[1] !== p1[1]) {
5623-
a = {
5624-
point: p0,
5625-
points: segment,
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
5659-
};
5660-
a.other = b;
5661-
subject.push(a);
5662-
clip.push(b);
5663-
} else {
5664-
var point = segment[0], n = segment.length - 1, i = 0;
5665-
context.moveTo(point[0], point[1]);
5666-
while (++i < n) context.lineTo((point = segment[i])[0], point[1]);
5667-
context.closePath();
5668-
}
5633+
var p0 = segment[0], p1 = segment[segment.length - 1], a = {
5634+
point: p0,
5635+
points: segment,
5636+
other: null,
5637+
visited: false,
5638+
entry: true,
5639+
subject: true
5640+
}, b = {
5641+
point: p0,
5642+
angle: angle(p0),
5643+
points: [ p0 ],
5644+
other: a,
5645+
visited: false,
5646+
entry: false,
5647+
subject: false
5648+
};
5649+
a.other = b;
5650+
subject.push(a);
5651+
clip.push(b);
5652+
a = {
5653+
point: p1,
5654+
points: [ p1 ],
5655+
other: null,
5656+
visited: false,
5657+
entry: false,
5658+
subject: true
5659+
};
5660+
b = {
5661+
point: p1,
5662+
angle: angle(p1),
5663+
points: [ p1 ],
5664+
other: a,
5665+
visited: false,
5666+
entry: true,
5667+
subject: false
5668+
};
5669+
a.other = b;
5670+
subject.push(a);
5671+
clip.push(b);
56695672
});
56705673
clip.sort(function(a, b) {
56715674
return b.angle - a.angle;
@@ -5754,7 +5757,11 @@
57545757
lineTo: function(x, y) {
57555758
segment.push([ x, y ]);
57565759
},
5757-
closePath: d3_noop
5760+
closePath: function() {
5761+
if (segments.length < 2) return;
5762+
segments.pop();
5763+
segments.push(segment = segment.concat(segments.shift()));
5764+
}
57585765
}, 0), segments ];
57595766
};
57605767
}

‎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: 67 additions & 53 deletions
Original file line numberDiff line numberDiff line change
@@ -73,31 +73,49 @@ function d3_geo_circleClip(degrees, rotate) {
7373
function clipLine(coordinates, context, winding) {
7474
if (!(n = coordinates.length)) return;
7575
var point0 = rotate(coordinates[0]),
76+
point2,
7677
inside = visible(point0),
7778
keepWinding = winding != null,
78-
n;
79-
if (inside) context.moveTo(point0[0], point0[1]);
79+
closed = keepWinding && inside,
80+
n,
81+
move0,
82+
line0;
83+
if (inside) context.moveTo((move0 = point0)[0], point0[1]);
8084
for (var i = 1; i < n; i++) {
8185
var point1 = rotate(coordinates[i]),
8286
v = visible(point1);
8387
if (v !== inside) {
84-
keepWinding = false;
8588
if (inside = v) {
8689
// outside going in
87-
point0 = intersect(point1, point0);
88-
context.moveTo(point0[0], point0[1]);
90+
point2 = intersect(point1, point0);
91+
// avoid coincident points
92+
if (!line0 || (Math.abs(line0[0] - point2[0]) > ε || Math.abs(line0[1] - point2[1]) > ε)) {
93+
if (move0) keepWinding = false;
94+
context.moveTo((move0 = point2)[0], point2[1]);
95+
}
96+
if (keepWinding) winding += d3_geo_circleWinding(point2, point1);
97+
point0 = point2;
8998
} else {
9099
// inside going out
91-
point0 = intersect(point0, point1);
92-
context.lineTo(point0[0], point0[1]);
100+
line0 = point2 = intersect(point0, point1);
101+
context.lineTo(point2[0], point2[1]);
102+
// check to see if this generates a closed polygon
103+
if (keepWinding) {
104+
if (Math.abs(move0[0] - point2[0]) > ε || Math.abs(move0[1] - point2[1]) > ε) {
105+
keepWinding = false;
106+
} else {
107+
winding += d3_geo_circleWinding(point0, move0);
108+
}
109+
}
110+
point0 = point2;
93111
}
94-
} else if (keepWinding) {
95-
winding += d3_geo_circleWinding(point0, point1);
96112
}
113+
if (keepWinding) winding += d3_geo_circleWinding(point0, point1);
97114
if (v) context.lineTo(point1[0], point1[1]);
98115
point0 = point1;
99116
}
100-
return keepWinding && winding;
117+
if (closed && v) context.closePath();
118+
return keepWinding && (!move0 || Math.abs(move0[0] - point0[0]) < ε && Math.abs(move0[1] - point0[1]) < ε) && winding;
101119
}
102120

103121
// Intersects the great circle between a and b with the clip circle.
@@ -139,7 +157,7 @@ function d3_geo_circleInterpolate(radians, precision) {
139157
var step = direction * precision;
140158
from = from.angle;
141159
to = to.angle;
142-
if (from < to) from += 2 * Math.PI;
160+
if (from < to) from += 2 * π;
143161
for (var step = precision, t = from; direction > 0 ? t > to : t < to; t -= step) {
144162
var c = Math.cos(t),
145163
s = Math.sin(t),
@@ -158,59 +176,51 @@ function d3_geo_circleClipPolygon(coordinates, context, clipLine, interpolate, a
158176
clip = [],
159177
segments = [],
160178
buffer = d3_geo_circleBufferSegments(clipLine),
161-
winding = 0;
179+
winding = 0,
180+
count = 0;
162181
coordinates.forEach(function(ring) {
163182
var x = buffer(ring, context),
164183
ringSegments = x[1];
165184
winding += x[0];
166-
// Since these are closed rings, we join segments if necessary.
167185
var n = ringSegments.length;
168-
if (n > 1) {
169-
var firstSegment = ringSegments[0],
170-
lastSegment = ringSegments[n - 1],
171-
p0 = firstSegment[0],
172-
p1 = lastSegment[lastSegment.length - 1];
173-
if (p0[0] === p1[0] && p0[1] === p1[1]) {
174-
ringSegments.shift();
175-
ringSegments.pop();
176-
ringSegments.push(lastSegment.concat(firstSegment));
177-
}
186+
if (!n) return;
187+
count += n;
188+
189+
if (x[0] !== false) {
190+
var segment = ringSegments[0],
191+
point = segment[0],
192+
n = segment.length - 1,
193+
i = 0;
194+
context.moveTo(point[0], point[1]);
195+
while (++i < n) context.lineTo((point = segment[i])[0], point[1]);
196+
context.closePath();
197+
return;
178198
}
179199
segments = segments.concat(ringSegments);
180200
});
181-
if (segments.length ? winding > 0 : winding < 0) {
182-
segments.push(winding = []);
183-
x = {lineTo: function(x, y) { winding.push([x, y]); }};
184-
d3_geo_circleInterpolateCircle(interpolate, x);
185-
winding.push(winding[0]);
201+
202+
if (count ? winding > 0 : winding < 0) {
203+
var moved = false;
204+
d3_geo_circleInterpolateCircle(interpolate, {
205+
lineTo: function(x, y) {
206+
(moved ? context.lineTo : (moved = true, context.moveTo))(x, y);
207+
}
208+
});
209+
context.closePath();
186210
}
187211
segments.forEach(function(segment) {
188212
var p0 = segment[0],
189213
p1 = segment[segment.length - 1],
190-
a,
191-
b;
192-
if (p0[0] !== p1[0] || p0[1] !== p1[1]) {
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);
203-
} else {
204-
// TODO attach subsumed holes to the correct Polygons. For now, we can
205-
// add these as separate Polygons, since typically we draw everything
206-
// as a subpath in SVG so it doesn't matter if the holes don't match
207-
// their polygons. This would be done by calculating some kind of
208-
// winding number.
209-
var point = segment[0], n = segment.length - 1, i = 0;
210-
context.moveTo(point[0], point[1]);
211-
while (++i < n) context.lineTo((point = segment[i])[0], point[1]);
212-
context.closePath();
213-
}
214+
a = {point: p0, points: segment, other: null, visited: false, entry: true, subject: true},
215+
b = {point: p0, angle: angle(p0), points: [p0], other: a, visited: false, entry: false, subject: false};
216+
a.other = b;
217+
subject.push(a);
218+
clip.push(b);
219+
a = {point: p1, points: [p1], other: null, visited: false, entry: false, subject: true};
220+
b = {point: p1, angle: angle(p1), points: [p1], other: a, visited: false, entry: true, subject: false};
221+
a.other = b;
222+
subject.push(a);
223+
clip.push(b);
214224
});
215225
// Sort intersection points by relative angles.
216226
clip.sort(function(a, b) { return b.angle - a.angle; });
@@ -324,7 +334,11 @@ function d3_geo_circleBufferSegments(f) {
324334
point: d3_noop,
325335
moveTo: function(x, y) { segments.push(segment = [[x, y]]); },
326336
lineTo: function(x, y) { segment.push([x, y]); },
327-
closePath: d3_noop
337+
closePath: function() {
338+
if (segments.length < 2) return;
339+
segments.pop();
340+
segments.push(segment = segment.concat(segments.shift()));
341+
}
328342
}, 0),
329343
segments
330344
];

‎test/geo/circle-test.js‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,9 @@ suite.addBatch({
99
"circle": {
1010
topic: d3.geo.circle,
1111
"generates a Polygon": function(circle) {
12-
assert.deepEqual(circle().type, "Polygon"); // TODO test coordinates
12+
var o = circle();
13+
assert.equal(o.type, "Polygon");
14+
assert.inDelta(o.coordinates, [[[-90, 0], [-90, 6], [-90, 12], [-90, 18], [-90, 24], [-90, 30], [-90, 36], [-90, 42], [-90, 48], [-90, 54], [-90, 60], [-90, 66], [-90, 72], [-90, 78], [-90, 84], [-77.803070, 90], [-45, 90], [90, 84], [90, 78], [90, 72], [90, 66], [90, 60], [90, 54], [90, 48], [90, 42], [90, 36], [90, 30], [90, 24], [90, 18], [90, 12], [90, 6], [90, 0], [90, -6], [90, -12], [90, -18], [90, -24], [90, -30], [90, -36], [90, -42], [90, -48], [90, -54], [90, -60], [90, -66], [90, -72], [90, -78], [90, -84], [86.730543, -90], [71.565051, -90], [-90, -84], [-90, -78], [-90, -72], [-90, -66], [-90, -60], [-90, -54], [-90, -48], [-90, -42], [-90, -36], [-90, -30], [-90, -24], [-90, -18], [-90, -12], [-90, -6], [-90, 0]]], 1e-6);
1315
}
1416
}
1517
});

0 commit comments

Comments
 (0)