Skip to content

Commit b0659e0

Browse files
jasondaviesjasondavies
committed
Preserve polygon exterior/interior ring ordering.
According to GeoJSON, the first ring in a polygon should be the exterior, and subsequent rings should be holes that are inside the exterior ring. This fix ensures that the rejoining of clipped segments preserves these semantics, by generating multiple polygons if necessary rather than generating all rings within a single polygon as it did previously. Fixes d3#1558.
1 parent 2c93d9c commit b0659e0

8 files changed

Lines changed: 259 additions & 184 deletions

File tree

‎d3.js‎

Lines changed: 88 additions & 78 deletions
Original file line numberDiff line numberDiff line change
@@ -186,7 +186,8 @@ d3 = function() {
186186
return entries;
187187
};
188188
d3.merge = function(arrays) {
189-
return Array.prototype.concat.apply([], arrays);
189+
var n = arrays.length;
190+
return n ? n > 1 ? Array.prototype.concat.apply([], arrays) : arrays[0] : [];
190191
};
191192
d3.range = function(start, stop, step) {
192193
if (arguments.length < 3) {
@@ -2611,16 +2612,15 @@ d3 = function() {
26112612
function d3_true() {
26122613
return true;
26132614
}
2614-
function d3_geo_clipPolygon(segments, compare, clipStartInside, interpolate, listener) {
2615-
var subject = [], clip = [];
2616-
segments.forEach(function(segment) {
2617-
if ((n = segment.length - 1) <= 0) return;
2618-
var n, p0 = segment[0], p1 = segment[n];
2615+
function d3_geo_clipPolygon(segments, compare, clipStartInside, pointInPolygon, interpolate, listener) {
2616+
var subject = [], clip = [], rings = [], n = segments.length;
2617+
for (var i = 0; i < n; ++i) {
2618+
var segment = segments[i];
2619+
if ((m = segment.length - 1) <= 0) continue;
2620+
var m, p0 = segment[0], p1 = segment[m];
26192621
if (d3_geo_sphericalEqual(p0, p1)) {
2620-
listener.lineStart();
2621-
for (var i = 0; i < n; ++i) listener.point((p0 = segment[i])[0], p0[1]);
2622-
listener.lineEnd();
2623-
return;
2622+
rings.push(segment);
2623+
continue;
26242624
}
26252625
var a = {
26262626
point: p0,
@@ -2659,43 +2659,83 @@ d3 = function() {
26592659
a.other = b;
26602660
subject.push(a);
26612661
clip.push(b);
2662-
});
2663-
clip.sort(compare);
2664-
d3_geo_clipPolygonLinkCircular(subject);
2665-
d3_geo_clipPolygonLinkCircular(clip);
2666-
if (!subject.length) return;
2667-
for (var i = 0, entry = clipStartInside, n = clip.length; i < n; ++i) {
2668-
clip[i].entry = entry = !entry;
2669-
}
2670-
var start = subject[0], current, points, point;
2671-
while (1) {
2672-
current = start;
2673-
while (current.visited) if ((current = current.next) === start) return;
2674-
points = current.points;
2675-
listener.lineStart();
2676-
do {
2677-
current.visited = current.other.visited = true;
2678-
if (current.entry) {
2679-
if (current.subject) {
2680-
for (var i = 0; i < points.length; i++) listener.point((point = points[i])[0], point[1]);
2662+
}
2663+
if (subject.length) {
2664+
clip.sort(compare);
2665+
d3_geo_clipPolygonLinkCircular(subject);
2666+
d3_geo_clipPolygonLinkCircular(clip);
2667+
for (var i = 0, entry = clipStartInside, n = clip.length; i < n; ++i) {
2668+
clip[i].entry = entry = !entry;
2669+
}
2670+
var start = subject[0], current, points, point, listener_ = listener;
2671+
if (rings.length) listener = d3_geo_clipBufferListener();
2672+
while (1) {
2673+
current = start;
2674+
while (current.visited) if ((current = current.next) === start) break;
2675+
if (current.visited) break;
2676+
points = current.points;
2677+
listener.polygonStart();
2678+
listener.lineStart();
2679+
do {
2680+
current.visited = current.other.visited = true;
2681+
if (current.entry) {
2682+
if (current.subject) {
2683+
for (var i = 0; i < points.length; i++) listener.point((point = points[i])[0], point[1]);
2684+
} else {
2685+
interpolate(current.point, current.next.point, 1, listener);
2686+
}
2687+
current = current.next;
26812688
} else {
2682-
interpolate(current.point, current.next.point, 1, listener);
2689+
if (current.subject) {
2690+
points = current.prev.points;
2691+
for (var i = points.length; --i >= 0; ) listener.point((point = points[i])[0], point[1]);
2692+
} else {
2693+
interpolate(current.point, current.prev.point, -1, listener);
2694+
}
2695+
current = current.prev;
26832696
}
2684-
current = current.next;
2685-
} else {
2686-
if (current.subject) {
2687-
points = current.prev.points;
2688-
for (var i = points.length; --i >= 0; ) listener.point((point = points[i])[0], point[1]);
2689-
} else {
2690-
interpolate(current.point, current.prev.point, -1, listener);
2697+
current = current.other;
2698+
points = current.points;
2699+
} while (!current.visited);
2700+
listener.lineEnd();
2701+
listener.polygonEnd();
2702+
}
2703+
if (n = rings.length) {
2704+
var exteriors = listener.buffer();
2705+
listener = listener_;
2706+
for (var j = 0, m = exteriors.length; j < m; ++j) {
2707+
var exterior = exteriors[j];
2708+
listener.polygonStart();
2709+
d3_geo_clipPolygonStreamRing(exterior, listener);
2710+
for (var i = 0; i < n; ++i) {
2711+
var ring = rings[i];
2712+
if (ring && pointInPolygon(ring[0], [ exterior ])) {
2713+
d3_geo_clipPolygonStreamRing(ring, listener);
2714+
rings[i] = null;
2715+
}
26912716
}
2692-
current = current.prev;
2717+
listener.polygonEnd();
26932718
}
2694-
current = current.other;
2695-
points = current.points;
2696-
} while (!current.visited);
2697-
listener.lineEnd();
2719+
}
2720+
} else if ((n = rings.length) || clipStartInside) {
2721+
listener.polygonStart();
2722+
if (clipStartInside) {
2723+
listener.lineStart();
2724+
interpolate(null, null, 1, listener);
2725+
listener.lineEnd();
2726+
}
2727+
for (var i = 0; i < n; ++i) {
2728+
d3_geo_clipPolygonStreamRing(rings[i], listener);
2729+
}
2730+
listener.polygonEnd();
2731+
}
2732+
}
2733+
function d3_geo_clipPolygonStreamRing(ring, listener) {
2734+
listener.lineStart();
2735+
for (var i = 0, n = ring.length - 1, p; i < n; ++i) {
2736+
listener.point((p = ring[i])[0], p[1]);
26982737
}
2738+
listener.lineEnd();
26992739
}
27002740
function d3_geo_clipPolygonLinkCircular(array) {
27012741
if (!(n = array.length)) return;
@@ -2721,22 +2761,12 @@ d3 = function() {
27212761
clip.lineEnd = ringEnd;
27222762
segments = [];
27232763
polygon = [];
2724-
listener.polygonStart();
27252764
},
27262765
polygonEnd: function() {
27272766
clip.point = point;
27282767
clip.lineStart = lineStart;
27292768
clip.lineEnd = lineEnd;
2730-
segments = d3.merge(segments);
2731-
var clipStartInside = d3_geo_pointInPolygon(rotatedClipStart, polygon);
2732-
if (segments.length) {
2733-
d3_geo_clipPolygon(segments, d3_geo_clipSort, clipStartInside, interpolate, listener);
2734-
} else if (clipStartInside) {
2735-
listener.lineStart();
2736-
interpolate(null, null, 1, listener);
2737-
listener.lineEnd();
2738-
}
2739-
listener.polygonEnd();
2769+
d3_geo_clipPolygon(d3.merge(segments), d3_geo_clipSort, d3_geo_pointInPolygon(rotatedClipStart, polygon), d3_geo_pointInPolygon, interpolate, listener);
27402770
segments = polygon = null;
27412771
},
27422772
sphere: function() {
@@ -2777,19 +2807,11 @@ d3 = function() {
27772807
function ringEnd() {
27782808
pointRing(ring[0][0], ring[0][1]);
27792809
ringListener.lineEnd();
2780-
var clean = ringListener.clean(), ringSegments = buffer.buffer(), segment, n = ringSegments.length;
2810+
var clean = ringListener.clean(), ringSegments = buffer.buffer(), n = ringSegments.length;
27812811
ring.pop();
27822812
polygon.push(ring);
27832813
ring = null;
27842814
if (!n) return;
2785-
if (clean & 1) {
2786-
segment = ringSegments[0];
2787-
var n = segment.length - 1, i = -1, point;
2788-
listener.lineStart();
2789-
while (++i < n) listener.point((point = segment[i])[0], point[1]);
2790-
listener.lineEnd();
2791-
return;
2792-
}
27932815
if (n > 1 && clean & 2) ringSegments.push(ringSegments.pop().concat(ringSegments.shift()));
27942816
segments.push(ringSegments.filter(d3_geo_clipSegmentLength1));
27952817
}
@@ -2809,6 +2831,8 @@ d3 = function() {
28092831
line.push([ λ, φ ]);
28102832
},
28112833
lineEnd: d3_noop,
2834+
polygonStart: d3_noop,
2835+
polygonEnd: d3_noop,
28122836
buffer: function() {
28132837
var buffer = lines;
28142838
lines = [];
@@ -3047,25 +3071,11 @@ d3 = function() {
30473071
clean = true;
30483072
},
30493073
polygonEnd: function() {
3050-
listener = listener_;
3051-
segments = d3.merge(segments);
3052-
var clipStartInside = insidePolygon([ x0, y1 ]), inside = clean && clipStartInside, visible = segments.length;
3053-
if (inside || visible) {
3054-
listener.polygonStart();
3055-
if (inside) {
3056-
listener.lineStart();
3057-
interpolate(null, null, 1, listener);
3058-
listener.lineEnd();
3059-
}
3060-
if (visible) {
3061-
d3_geo_clipPolygon(segments, compare, clipStartInside, interpolate, listener);
3062-
}
3063-
listener.polygonEnd();
3064-
}
3074+
d3_geo_clipPolygon(d3.merge(segments), compare, pointInPolygon([ x0, y1 ], polygon), pointInPolygon, interpolate, listener = listener_);
30653075
segments = polygon = ring = null;
30663076
}
30673077
};
3068-
function insidePolygon(p) {
3078+
function pointInPolygon(p, polygon) {
30693079
var wn = 0, n = polygon.length, y = p[1];
30703080
for (var i = 0; i < n; ++i) {
30713081
for (var j = 1, v = polygon[i], m = v.length, a = v[0], b; j < m; ++j) {

‎d3.min.js‎

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

‎src/arrays/merge.js‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,7 @@
11
d3.merge = function(arrays) {
2-
return Array.prototype.concat.apply([], arrays);
2+
var n = arrays.length;
3+
return n ? n > 1
4+
? Array.prototype.concat.apply([], arrays)
5+
: arrays[0]
6+
: [];
37
};

‎src/geo/clip-extent.js‎

Lines changed: 2 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -46,28 +46,12 @@ function d3_geo_clipExtent(x0, y0, x1, y1) {
4646
clean = true;
4747
},
4848
polygonEnd: function() {
49-
listener = listener_;
50-
segments = d3.merge(segments);
51-
var clipStartInside = insidePolygon([x0, y1]),
52-
inside = clean && clipStartInside,
53-
visible = segments.length;
54-
if (inside || visible) {
55-
listener.polygonStart();
56-
if (inside) {
57-
listener.lineStart();
58-
interpolate(null, null, 1, listener);
59-
listener.lineEnd();
60-
}
61-
if (visible) {
62-
d3_geo_clipPolygon(segments, compare, clipStartInside, interpolate, listener);
63-
}
64-
listener.polygonEnd();
65-
}
49+
d3_geo_clipPolygon(d3.merge(segments), compare, pointInPolygon([x0, y1], polygon), pointInPolygon, interpolate, listener = listener_);
6650
segments = polygon = ring = null;
6751
}
6852
};
6953

70-
function insidePolygon(p) {
54+
function pointInPolygon(p, polygon) {
7155
var wn = 0, // the winding number counter
7256
n = polygon.length,
7357
y = p[1];

0 commit comments

Comments
 (0)