Skip to content

Commit a502859

Browse files
mbostockmbostock
committed
Add d3.geom module.
For now, just Sutherland-Hodgman clipping and area of a convex polygon.
1 parent 57059e3 commit a502859

6 files changed

Lines changed: 158 additions & 2 deletions

File tree

‎Makefile‎

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,10 +9,12 @@ JS_COMPILER = \
99
all: \
1010
d3.js \
1111
d3.min.js \
12-
d3.geo.js \
13-
d3.geo.min.js \
1412
d3.csv.js \
1513
d3.csv.min.js \
14+
d3.geo.js \
15+
d3.geo.min.js \
16+
d3.geom.js \
17+
d3.geom.min.js \
1618
d3.time.js \
1719
d3.time.min.js
1820

@@ -74,6 +76,10 @@ d3.time.js: \
7476
src/time/time.js \
7577
src/time/format.js
7678

79+
d3.geom.js: \
80+
src/geom/geom.js \
81+
src/geom/polygon.js
82+
7783
%.min.js: %.js Makefile src/externs.js
7884
@rm -f $@
7985
$(JS_COMPILER) --js $< --js_output_file $@

‎d3.geom.js‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
d3.geom = {};
2+
// Note: requires coordinates to be clockwise and convex!
3+
d3.geom.polygon = function(coordinates) {
4+
var n = coordinates.length;
5+
6+
coordinates.area = function() {
7+
var i = 0,
8+
a = coordinates[n - 1][0] * coordinates[0][1],
9+
b = coordinates[n - 1][1] * coordinates[0][0];
10+
while (++i < n) {
11+
a += coordinates[i - 1][0] * coordinates[i][1];
12+
b += coordinates[i - 1][1] * coordinates[i][0];
13+
}
14+
return (a - b) * .5;
15+
};
16+
17+
// The Sutherland-Hodgman clipping algorithm.
18+
coordinates.intersection = function(subject) {
19+
var output = subject,
20+
input,
21+
i = -1,
22+
j,
23+
m,
24+
a = coordinates[n - 1],
25+
b,
26+
c,
27+
d;
28+
while (++i < n) {
29+
input = output.slice();
30+
output = [];
31+
b = coordinates[i];
32+
c = input[(m = input.length) - 1];
33+
j = -1;
34+
while (++j < m) {
35+
d = input[j];
36+
if (d3_geom_polygonInside(d, a, b)) {
37+
if (!d3_geom_polygonInside(c, a, b)) {
38+
output.push(d3_geom_polygonIntersect(c, d, a, b));
39+
}
40+
output.push(d);
41+
} else if (d3_geom_polygonInside(c, a, b)) {
42+
output.push(d3_geom_polygonIntersect(c, d, a, b));
43+
}
44+
c = d;
45+
}
46+
a = b;
47+
}
48+
return output;
49+
};
50+
51+
return coordinates;
52+
};
53+
54+
function d3_geom_polygonInside(p, a, b) {
55+
return (b[0] - a[0]) * (p[1] - a[1]) >= (b[1] - a[1]) * (p[0] - a[0]);
56+
}
57+
58+
// Intersect two infinite lines cd and ab.
59+
function d3_geom_polygonIntersect(c, d, a, b) {
60+
var x1 = c[0], x2 = d[0], x3 = a[0], x4 = b[0],
61+
y1 = c[1], y2 = d[1], y3 = a[1], y4 = b[1],
62+
x13 = x1 - x3,
63+
x21 = x2 - x1,
64+
x43 = x4 - x3,
65+
y13 = y1 - y3,
66+
y21 = y2 - y1,
67+
y43 = y4 - y3,
68+
ua = (x43 * y13 - y43 * x13) / (y43 * x21 - x43 * y21);
69+
return [x1 + ua * x21, y1 + ua * y21];
70+
}

‎d3.geom.min.js‎

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

‎src/externs.js‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -148,6 +148,14 @@ d3.geo = {
148148
}
149149
};
150150

151+
// d3.geom
152+
d3.geom = {
153+
polygon: {
154+
area: 1,
155+
intersection: 1
156+
}
157+
};
158+
151159
// d3.csv
152160
d3.csv = {
153161
parse: 1,

‎src/geom/geom.js‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
d3.geom = {};

‎src/geom/polygon.js‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
// Note: requires coordinates to be clockwise and convex!
2+
d3.geom.polygon = function(coordinates) {
3+
var n = coordinates.length;
4+
5+
coordinates.area = function() {
6+
var i = 0,
7+
a = coordinates[n - 1][0] * coordinates[0][1],
8+
b = coordinates[n - 1][1] * coordinates[0][0];
9+
while (++i < n) {
10+
a += coordinates[i - 1][0] * coordinates[i][1];
11+
b += coordinates[i - 1][1] * coordinates[i][0];
12+
}
13+
return (a - b) * .5;
14+
};
15+
16+
// The Sutherland-Hodgman clipping algorithm.
17+
coordinates.intersection = function(subject) {
18+
var output = subject,
19+
input,
20+
i = -1,
21+
j,
22+
m,
23+
a = coordinates[n - 1],
24+
b,
25+
c,
26+
d;
27+
while (++i < n) {
28+
input = output.slice();
29+
output = [];
30+
b = coordinates[i];
31+
c = input[(m = input.length) - 1];
32+
j = -1;
33+
while (++j < m) {
34+
d = input[j];
35+
if (d3_geom_polygonInside(d, a, b)) {
36+
if (!d3_geom_polygonInside(c, a, b)) {
37+
output.push(d3_geom_polygonIntersect(c, d, a, b));
38+
}
39+
output.push(d);
40+
} else if (d3_geom_polygonInside(c, a, b)) {
41+
output.push(d3_geom_polygonIntersect(c, d, a, b));
42+
}
43+
c = d;
44+
}
45+
a = b;
46+
}
47+
return output;
48+
};
49+
50+
return coordinates;
51+
};
52+
53+
function d3_geom_polygonInside(p, a, b) {
54+
return (b[0] - a[0]) * (p[1] - a[1]) >= (b[1] - a[1]) * (p[0] - a[0]);
55+
}
56+
57+
// Intersect two infinite lines cd and ab.
58+
function d3_geom_polygonIntersect(c, d, a, b) {
59+
var x1 = c[0], x2 = d[0], x3 = a[0], x4 = b[0],
60+
y1 = c[1], y2 = d[1], y3 = a[1], y4 = b[1],
61+
x13 = x1 - x3,
62+
x21 = x2 - x1,
63+
x43 = x4 - x3,
64+
y13 = y1 - y3,
65+
y21 = y2 - y1,
66+
y43 = y4 - y3,
67+
ua = (x43 * y13 - y43 * x13) / (y43 * x21 - x43 * y21);
68+
return [x1 + ua * x21, y1 + ua * y21];
69+
}

0 commit comments

Comments
 (0)