Skip to content

Commit 9eb878e

Browse files
jasondaviesjasondavies
committed
Fix clipping bug for complex polygons.
Intersection points are sorted along the clipping region edge relative to a particular point. In the case of antimeridian clipping, this point is the South pole. Previously, the first intersection was assumed to be an entering intersection, but this is not always the case. The fix is to see whether the clip region start point (the point relative to which sorting occurs) is inside or outside the polygon being drawn. If it is inside, then the first intersection point must be outside, and so forth. The same applies to d3.geo.clipExtent. Provision was already made for this, but this has now been optimised to use a single point instead of picking one of the four corners. Another optimisation was to reuse this clip region start point to determine whether to interpolate all the way around the clip region edge. Previously, this was done by testing an arbitrary point in the clip region. The above fix seemed to have broken one of the tests, and this has been fixed by modifying the point-in-polygon routine slightly to handle points that might lie exactly on the polygon edge. Finally, I noticed a regression with the recent clipExtent fix, where a polygon incorrectly being marked as “clean” (no intersections) on a per-ring instead of per-polygon basis.
1 parent a76aed5 commit 9eb878e

8 files changed

Lines changed: 34 additions & 39 deletions

File tree

‎d3.js‎

Lines changed: 15 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -2611,7 +2611,7 @@ d3 = function() {
26112611
function d3_true() {
26122612
return true;
26132613
}
2614-
function d3_geo_clipPolygon(segments, compare, inside, interpolate, listener) {
2614+
function d3_geo_clipPolygon(segments, compare, clipStartInside, interpolate, listener) {
26152615
var subject = [], clip = [];
26162616
segments.forEach(function(segment) {
26172617
if ((n = segment.length - 1) <= 0) return;
@@ -2664,8 +2664,8 @@ d3 = function() {
26642664
d3_geo_clipPolygonLinkCircular(subject);
26652665
d3_geo_clipPolygonLinkCircular(clip);
26662666
if (!subject.length) return;
2667-
if (inside) for (var i = 1, e = !inside(clip[0].point), n = clip.length; i < n; ++i) {
2668-
clip[i].entry = e = !e;
2667+
for (var i = 0, entry = clipStartInside, n = clip.length; i < n; ++i) {
2668+
clip[i].entry = entry = !entry;
26692669
}
26702670
var start = subject[0], current, points, point;
26712671
while (1) {
@@ -2708,9 +2708,9 @@ d3 = function() {
27082708
a.next = b = array[0];
27092709
b.prev = a;
27102710
}
2711-
function d3_geo_clip(pointVisible, clipLine, interpolate, clipPoint) {
2711+
function d3_geo_clip(pointVisible, clipLine, interpolate, clipStart) {
27122712
return function(rotate, listener) {
2713-
var line = clipLine(listener), rotatedClipPoint = rotate.invert(clipPoint[0], clipPoint[1]);
2713+
var line = clipLine(listener), rotatedClipStart = rotate.invert(clipStart[0], clipStart[1]);
27142714
var clip = {
27152715
point: point,
27162716
lineStart: lineStart,
@@ -2728,9 +2728,10 @@ d3 = function() {
27282728
clip.lineStart = lineStart;
27292729
clip.lineEnd = lineEnd;
27302730
segments = d3.merge(segments);
2731+
var clipStartInside = d3_geo_pointInPolygon(rotatedClipStart, polygon);
27312732
if (segments.length) {
2732-
d3_geo_clipPolygon(segments, d3_geo_clipSort, null, interpolate, listener);
2733-
} else if (d3_geo_pointInPolygon(rotatedClipPoint, polygon)) {
2733+
d3_geo_clipPolygon(segments, d3_geo_clipSort, clipStartInside, interpolate, listener);
2734+
} else if (clipStartInside) {
27342735
listener.lineStart();
27352736
interpolate(null, null, 1, listener);
27362737
listener.lineEnd();
@@ -2841,7 +2842,7 @@ d3 = function() {
28412842
var intersection = d3_geo_cartesianCross(meridianNormal, arc);
28422843
d3_geo_cartesianNormalize(intersection);
28432844
var φarc = (antimeridian ^ dλ >= 0 ? -1 : 1) * d3_asin(intersection[2]);
2844-
if (parallel > φarc) {
2845+
if (parallel > φarc || parallel === φarc && (arc[0] || arc[1])) {
28452846
winding += antimeridian ^ dλ >= 0 ? 1 : -1;
28462847
}
28472848
}
@@ -2851,7 +2852,7 @@ d3 = function() {
28512852
}
28522853
return (polarAngle < -ε || polarAngle < ε && d3_geo_areaRingSum < 0) ^ winding & 1;
28532854
}
2854-
var d3_geo_clipAntimeridian = d3_geo_clip(d3_true, d3_geo_clipAntimeridianLine, d3_geo_clipAntimeridianInterpolate, [ -π, 0 ]);
2855+
var d3_geo_clipAntimeridian = d3_geo_clip(d3_true, d3_geo_clipAntimeridianLine, d3_geo_clipAntimeridianInterpolate, [ -π, -π / 2 ]);
28552856
function d3_geo_clipAntimeridianLine(listener) {
28562857
var λ0 = NaN, φ0 = NaN, sλ0 = NaN, clean;
28572858
return {
@@ -2920,7 +2921,7 @@ d3 = function() {
29202921
}
29212922
function d3_geo_clipCircle(radius) {
29222923
var cr = Math.cos(radius), smallRadius = cr > 0, notHemisphere = Math.abs(cr) > ε, interpolate = d3_geo_circleInterpolate(radius, 6 * d3_radians);
2923-
return d3_geo_clip(visible, clipLine, interpolate, [ radius, 0 ]);
2924+
return d3_geo_clip(visible, clipLine, interpolate, smallRadius ? [ 0, -radius ] : [ -π, radius - π ]);
29242925
function visible(λ, φ) {
29252926
return Math.cos(λ) * Math.cos(φ) > cr;
29262927
}
@@ -3043,11 +3044,12 @@ d3 = function() {
30433044
listener = bufferListener;
30443045
segments = [];
30453046
polygon = [];
3047+
clean = true;
30463048
},
30473049
polygonEnd: function() {
30483050
listener = listener_;
30493051
segments = d3.merge(segments);
3050-
var inside = clean && insidePolygon([ x0, y0 ]), visible = segments.length;
3052+
var clipStartInside = insidePolygon([ x0, y1 ]), inside = clean && clipStartInside, visible = segments.length;
30513053
if (inside || visible) {
30523054
listener.polygonStart();
30533055
if (inside) {
@@ -3056,17 +3058,13 @@ d3 = function() {
30563058
listener.lineEnd();
30573059
}
30583060
if (visible) {
3059-
d3_geo_clipPolygon(segments, compare, pointInside, interpolate, listener);
3061+
d3_geo_clipPolygon(segments, compare, clipStartInside, interpolate, listener);
30603062
}
30613063
listener.polygonEnd();
30623064
}
30633065
segments = polygon = ring = null;
30643066
}
30653067
};
3066-
function pointInside(point) {
3067-
var a = corner(point, -1), i = insidePolygon([ a === 0 || a === 3 ? x0 : x1, a > 1 ? y1 : y0 ]);
3068-
return i;
3069-
}
30703068
function insidePolygon(p) {
30713069
var wn = 0, n = polygon.length, y = p[1];
30723070
for (var i = 0; i < n; ++i) {
@@ -3105,7 +3103,7 @@ d3 = function() {
31053103
function lineStart() {
31063104
clip.point = linePoint;
31073105
if (polygon) polygon.push(ring = []);
3108-
first = clean = true;
3106+
first = true;
31093107
v_ = false;
31103108
x_ = y_ = NaN;
31113109
}

‎d3.min.js‎

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

‎src/geo/clip-antimeridian.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@ var d3_geo_clipAntimeridian = d3_geo_clip(
77
d3_true,
88
d3_geo_clipAntimeridianLine,
99
d3_geo_clipAntimeridianInterpolate,
10-
[-π, 0]);
10+
[-π, -π / 2]);
1111

1212
// Takes a line and cuts into visible segments. Return values:
1313
// 0: there were intersections or the line was empty.

‎src/geo/clip-circle.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@ function d3_geo_clipCircle(radius) {
1212
notHemisphere = Math.abs(cr) > ε, // TODO optimise for this common case
1313
interpolate = d3_geo_circleInterpolate(radius, 6 * d3_radians);
1414

15-
return d3_geo_clip(visible, clipLine, interpolate, [radius, 0]);
15+
return d3_geo_clip(visible, clipLine, interpolate, smallRadius ? [0, -radius] : [-π, radius - π]);
1616

1717
function visible(λ, φ) {
1818
return Math.cos(λ) * Math.cos(φ) > cr;

‎src/geo/clip-extent.js‎

Lines changed: 5 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -43,11 +43,13 @@ function d3_geo_clipExtent(x0, y0, x1, y1) {
4343
listener = bufferListener;
4444
segments = [];
4545
polygon = [];
46+
clean = true;
4647
},
4748
polygonEnd: function() {
4849
listener = listener_;
4950
segments = d3.merge(segments);
50-
var inside = clean && insidePolygon([x0, y0]),
51+
var clipStartInside = insidePolygon([x0, y1]),
52+
inside = clean && clipStartInside,
5153
visible = segments.length;
5254
if (inside || visible) {
5355
listener.polygonStart();
@@ -57,20 +59,14 @@ function d3_geo_clipExtent(x0, y0, x1, y1) {
5759
listener.lineEnd();
5860
}
5961
if (visible) {
60-
d3_geo_clipPolygon(segments, compare, pointInside, interpolate, listener);
62+
d3_geo_clipPolygon(segments, compare, clipStartInside, interpolate, listener);
6163
}
6264
listener.polygonEnd();
6365
}
6466
segments = polygon = ring = null;
6567
}
6668
};
6769

68-
function pointInside(point) {
69-
var a = corner(point, -1),
70-
i = insidePolygon([a === 0 || a === 3 ? x0 : x1, a > 1 ? y1 : y0]);
71-
return i;
72-
}
73-
7470
function insidePolygon(p) {
7571
var wn = 0, // the winding number counter
7672
n = polygon.length,
@@ -123,7 +119,7 @@ function d3_geo_clipExtent(x0, y0, x1, y1) {
123119
function lineStart() {
124120
clip.point = linePoint;
125121
if (polygon) polygon.push(ring = []);
126-
first = clean = true;
122+
first = true;
127123
v_ = false;
128124
x_ = y_ = NaN;
129125
}

‎src/geo/clip-polygon.js‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@ import "spherical";
44
// General spherical polygon clipping algorithm: takes a polygon, cuts it into
55
// visible line segments and rejoins the segments by interpolating along the
66
// clip edge.
7-
function d3_geo_clipPolygon(segments, compare, inside, interpolate, listener) {
7+
function d3_geo_clipPolygon(segments, compare, clipStartInside, interpolate, listener) {
88
var subject = [],
99
clip = [];
1010

@@ -39,8 +39,8 @@ function d3_geo_clipPolygon(segments, compare, inside, interpolate, listener) {
3939
d3_geo_clipPolygonLinkCircular(clip);
4040
if (!subject.length) return;
4141

42-
if (inside) for (var i = 1, e = !inside(clip[0].point), n = clip.length; i < n; ++i) {
43-
clip[i].entry = (e = !e);
42+
for (var i = 0, entry = clipStartInside, n = clip.length; i < n; ++i) {
43+
clip[i].entry = entry = !entry;
4444
}
4545

4646
var start = subject[0],

‎src/geo/clip.js‎

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -3,10 +3,10 @@ import "../core/noop";
33
import "../math/trigonometry";
44
import "clip-polygon";
55

6-
function d3_geo_clip(pointVisible, clipLine, interpolate, clipPoint) {
6+
function d3_geo_clip(pointVisible, clipLine, interpolate, clipStart) {
77
return function(rotate, listener) {
88
var line = clipLine(listener),
9-
rotatedClipPoint = rotate.invert(clipPoint[0], clipPoint[1]);
9+
rotatedClipStart = rotate.invert(clipStart[0], clipStart[1]);
1010

1111
var clip = {
1212
point: point,
@@ -26,9 +26,10 @@ function d3_geo_clip(pointVisible, clipLine, interpolate, clipPoint) {
2626
clip.lineEnd = lineEnd;
2727

2828
segments = d3.merge(segments);
29+
var clipStartInside = d3_geo_pointInPolygon(rotatedClipStart, polygon);
2930
if (segments.length) {
30-
d3_geo_clipPolygon(segments, d3_geo_clipSort, null, interpolate, listener);
31-
} else if (d3_geo_pointInPolygon(rotatedClipPoint, polygon)) {
31+
d3_geo_clipPolygon(segments, d3_geo_clipSort, clipStartInside, interpolate, listener);
32+
} else if (clipStartInside) {
3233
listener.lineStart();
3334
interpolate(null, null, 1, listener);
3435
listener.lineEnd();

‎src/geo/point-in-polygon.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,7 @@ function d3_geo_pointInPolygon(point, polygon) {
4444
var intersection = d3_geo_cartesianCross(meridianNormal, arc);
4545
d3_geo_cartesianNormalize(intersection);
4646
var φarc = (antimeridian ^ dλ >= 0 ? -1 : 1) * d3_asin(intersection[2]);
47-
if (parallel > φarc) {
47+
if (parallel > φarc || parallel === φarc && (arc[0] || arc[1])) {
4848
winding += antimeridian ^ dλ >= 0 ? 1 : -1;
4949
}
5050
}

0 commit comments

Comments
 (0)