Skip to content

Commit 9405e45

Browse files
mbostockmbostock
committed
Merge remote-tracking branch 'origin/fix-geo-pip' into 3.3.4
2 parents 2563048 + eff0a11 commit 9405e45

4 files changed

Lines changed: 44 additions & 19 deletions

File tree

‎d3.js‎

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -2820,7 +2820,7 @@ d3 = function() {
28202820
return ((a = a.point)[0] < 0 ? a[1] - π / 2 - ε : π / 2 - a[1]) - ((b = b.point)[0] < 0 ? b[1] - π / 2 - ε : π / 2 - b[1]);
28212821
}
28222822
function d3_geo_pointInPolygon(point, polygon) {
2823-
var meridian = point[0], parallel = point[1], meridianNormal = [ Math.sin(meridian), -Math.cos(meridian), 0 ], polarAngle = 0, polar = false, southPole = false, winding = 0;
2823+
var meridian = point[0], parallel = point[1], meridianNormal = [ Math.sin(meridian), -Math.cos(meridian), 0 ], polarAngle = 0, winding = 0;
28242824
d3_geo_areaRingSum.reset();
28252825
for (var i = 0, n = polygon.length; i < n; ++i) {
28262826
var ring = polygon[i], m = ring.length;
@@ -2831,7 +2831,6 @@ d3 = function() {
28312831
point = ring[j];
28322832
var λ = point[0], φ = point[1] / 2 + π / 4, sinφ = Math.sin(φ), cosφ = Math.cos(φ), dλ = λ - λ0, antimeridian = Math.abs(dλ) > π, k = sinφ0 * sinφ;
28332833
d3_geo_areaRingSum.add(Math.atan2(k * Math.sin(dλ), cosφ0 * cosφ + k * Math.cos(dλ)));
2834-
if (Math.abs(φ) < ε) southPole = true;
28352834
polarAngle += antimeridian ? dλ + (dλ >= 0 ? 2 : -2) * π : dλ;
28362835
if (antimeridian ^ λ0 >= meridian ^ λ >= meridian) {
28372836
var arc = d3_geo_cartesianCross(d3_geo_cartesian(point0), d3_geo_cartesian(point));
@@ -2846,9 +2845,8 @@ d3 = function() {
28462845
if (!j++) break;
28472846
λ0 = λ, sinφ0 = sinφ, cosφ0 = cosφ, point0 = point;
28482847
}
2849-
if (Math.abs(polarAngle) > ε) polar = true;
28502848
}
2851-
return (!southPole && !polar && d3_geo_areaRingSum < 0 || polarAngle < -ε) ^ winding & 1;
2849+
return (polarAngle < -ε || polarAngle < ε && d3_geo_areaRingSum < 0) ^ winding & 1;
28522850
}
28532851
var d3_geo_clipAntimeridian = d3_geo_clip(d3_true, d3_geo_clipAntimeridianLine, d3_geo_clipAntimeridianInterpolate, d3_geo_clipAntimeridianPolygonContains);
28542852
function d3_geo_clipAntimeridianLine(listener) {

‎d3.min.js‎

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

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

Lines changed: 4 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -8,8 +8,6 @@ function d3_geo_pointInPolygon(point, polygon) {
88
parallel = point[1],
99
meridianNormal = [Math.sin(meridian), -Math.cos(meridian), 0],
1010
polarAngle = 0,
11-
polar = false,
12-
southPole = false,
1311
winding = 0;
1412
d3_geo_areaRingSum.reset();
1513

@@ -36,7 +34,6 @@ function d3_geo_pointInPolygon(point, polygon) {
3634
k = sinφ0 * sinφ;
3735
d3_geo_areaRingSum.add(Math.atan2(k * Math.sin(dλ), cosφ0 * cosφ + k * Math.cos(dλ)));
3836

39-
if (Math.abs(φ) < ε) southPole = true;
4037
polarAngle += antimeridian ? dλ + (dλ >= 0 ? 2 : -2) * π : dλ;
4138

4239
// Are the longitudes either side of the point's meridian, and are the
@@ -54,18 +51,18 @@ function d3_geo_pointInPolygon(point, polygon) {
5451
if (!j++) break;
5552
λ0 = λ, sinφ0 = sinφ, cosφ0 = cosφ, point0 = point;
5653
}
57-
if (Math.abs(polarAngle) > ε) polar = true;
5854
}
5955

6056
// First, determine whether the South pole is inside or outside:
6157
//
6258
// It is inside if:
63-
// * the polygon doesn't wind around it, and its area is negative (counter-clockwise).
64-
// * otherwise, if the polygon winds around it in a clockwise direction.
59+
// * the polygon winds around it in a clockwise direction.
60+
// * the polygon does not (cumulatively) wind around it, but has a negative
61+
// (counter-clockwise) area.
6562
//
6663
// Second, count the (signed) number of times a segment crosses a meridian
6764
// from the point to the South pole. If it is zero, then the point is the
6865
// same side as the South pole.
6966

70-
return (!southPole && !polar && d3_geo_areaRingSum < 0 || polarAngle < -ε) ^ (winding & 1);
67+
return (polarAngle < -ε || polarAngle < ε && d3_geo_areaRingSum < 0) ^ (winding & 1);
7168
}

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

Lines changed: 37 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -122,6 +122,36 @@ suite.addBatch({
122122
"inside": function(pointInPolygon) {
123123
assert.ok(pointInPolygon([0, 20]));
124124
}
125+
},
126+
"narrow equatorial hole": {
127+
topic: function(pointInPolygon) {
128+
var circle = _.geo.circle().origin([0, -90]);
129+
return pointInPolygon([
130+
circle.angle(90 - .01)().coordinates[0],
131+
circle.angle(90 + .01)().coordinates[0].reverse()
132+
]);
133+
},
134+
"outside": function(pointInPolygon) {
135+
assert.ok(!pointInPolygon([0, 0]));
136+
},
137+
"inside": function(pointInPolygon) {
138+
assert.ok(pointInPolygon([0, -90]));
139+
}
140+
},
141+
"narrow equatorial strip": {
142+
topic: function(pointInPolygon) {
143+
var circle = _.geo.circle().origin([0, -90]);
144+
return pointInPolygon([
145+
circle.angle(90 + .01)().coordinates[0],
146+
circle.angle(90 - .01)().coordinates[0].reverse()
147+
]);
148+
},
149+
"outside": function(pointInPolygon) {
150+
assert.ok(!pointInPolygon([0, -90]));
151+
},
152+
"inside": function(pointInPolygon) {
153+
assert.ok(pointInPolygon([0, 0]));
154+
}
125155
}
126156
},
127157
"ring": {
@@ -317,15 +347,15 @@ suite.addBatch({
317347
return pointInPolygon([[[180, -90], [-135, 0], [135, 0], [180, -90]]]);
318348
},
319349
"inside": function(pointInPolygon) {
320-
assert.ok(pointInPolygon([180, 0]));
321-
assert.ok(pointInPolygon([150, 0]));
322-
assert.ok(pointInPolygon([180, -30]));
323-
assert.ok(pointInPolygon([150, -80]));
350+
assert.ok(pointInPolygon([0, 0]));
351+
assert.ok(pointInPolygon([180, 1]));
352+
assert.ok(pointInPolygon([-90, -80]));
324353
},
325354
"outside": function(pointInPolygon) {
326-
assert.ok(!pointInPolygon([0, 0]));
327-
assert.ok(!pointInPolygon([180, 1]));
328-
assert.ok(!pointInPolygon([-90, -80]));
355+
assert.ok(!pointInPolygon([180, 0]));
356+
assert.ok(!pointInPolygon([150, 0]));
357+
assert.ok(!pointInPolygon([180, -30]));
358+
assert.ok(!pointInPolygon([150, -80]));
329359
}
330360
},
331361
"triangle touching the North pole": {

0 commit comments

Comments
 (0)