D3 vs Scipy（Voronoi 图实现）
D3 vs Scipy (Voronoi diagram implementation)
背景
我正在处理 csv 文件中包含的一组 8000 个地理点。一方面，我创建了使用这些点构建的 Voronoi 图的可视化 - 它是使用 D3 库完成的。另一方面，我使用 Scipy.
在 Python 中计算这些 Voronoi 图
我的工作逻辑很简单——我在 Python 那边处理我的数据，制作热图、分析等等，然后我使用 D3 可视化效果。但是今天无意间发现Scipy和D3做的Voronoi图不一样。我注意到在使用 geojson.io 绘制在 Python 中制作的 Voronois 的 GeoJsons 之后，我只是想看看我是否可以将那里的所有内容可视化。
正如我所说，Voronois 是不同的 - 其中一些有不同的角度，有些甚至有额外的顶点。
问题：
为什么会这样？为什么这两个库（D3 和 Scipy）计算出的 Voronoi 图不同？
进一步说明
如何在 D3 端完成：基于 Chris Zetter 示例 http://chriszetter.com/blog/2014/06/15/building-a-voronoi-map-with-d3-and-leaflet/ 我将纬度和经度转换为自定义投影以在 mapbox 地图上将其可视化。
var voronoi = d3.geom.voronoi()
.x(function(d) { return d.x; })
.y(function(d) { return d.y; })
.clipExtent([[N_W.x , N_W.y],[S_E.x, S_E.y]])
我根据地图边界内可见的点 + 一些填充 (filteredPoints) 创建 Voronoi
filteredPoints = points.filter(function(d) {
var latlng = new L.LatLng(d.latitude, d.longitude);
if (!drawLimit.contains(latlng)) { return false };
// this translates points from coordinates to pixels
var point = map.latLngToLayerPoint(latlng);
key = point.toString();
if (existing.has(key)) { return false };
existing.add(key);
d.x = point.x;
d.y = point.y;
return true;
});
voronoi(filteredPoints).forEach(function(d) { d.point.cell = d});
Python这边是怎么做的：我用scipy.spatial.Voronoi.
from scipy.spatial import Voronoi
def create_voronois():
points = numpy.array(points_list)
vor = Voronoi(points)
其中 "points_list" 是我的 8000 个地理点的列表。
编辑：
我的可视化屏幕截图 - 黑色边框是用 D3 制作的 Voronois，白色边框是由 scipy.spatial.Voronoi 制作的。我们可以看到 scipy 是错误的。有人比较过这两个库吗？
编码为运行。它使用计算错误的 Voronois 打印 GeoJson。
import numpy
from scipy.spatial import Voronoi
from geojson import FeatureCollection, Feature, Polygon
points = [
[22.7433333333000, 53.4869444444000],
[23.2530555556000, 53.5683333333000],
[23.1066666667000, 53.7200000000000],
[22.8452777778000, 53.7758333333000],
[23.0952777778000, 53.4413888889000],
[23.4152777778000, 53.5233333333000],
[22.9175000000000, 53.5322222222000],
[22.7197222222000 ,53.7322222222000],
[22.9586111111000, 53.4594444444000],
[23.3425000000000, 53.6541666667000],
[23.0900000000000, 53.5777777778000],
[23.2283333333000, 53.4713888889000],
[23.3488888889000, 53.5072222222000],
[23.3647222222000 ,53.6447222222000]]
def create_voronois(points_list):
points = numpy.array(points_list)
vor = Voronoi(points)
point_voronoi_list = []
feature_list = []
for region in range(len(vor.regions) - 1):
vertice_list = []
for x in vor.regions[region]:
vertice = vor.vertices[x]
vertice = (vertice[1], vertice[0])
vertice_list.append(vertice)
polygon = Polygon([vertice_list])
feature = Feature(geometry=polygon, properties={})
feature_list.append(feature)
feature_collection = FeatureCollection(feature_list)
print feature_collection
create_voronois(points)
显然，您的 javascript 代码在计算 Voronoi 图之前对数据应用了转换。此转换不会保留点的相对距离，因此不会生成与您的 scipy 代码相同的结果。请注意，我并不是说您的 d3 版本不正确。鉴于数据是纬度和经度，您在 javascript 代码中所做的可能是正确的。但是要将其与 scipy 代码进行比较，如果您希望获得相同的 Voronoi 图，则必须进行相同的转换。
下面的脚本显示，如果您保留输入点的相对距离，scipy 的 Voronoi 函数和 d3.geom.voronoi 生成相同的图表。
这是一个使用 scipy 的 Voronoi 代码的脚本：
import numpy
from scipy.spatial import Voronoi, voronoi_plot_2d
import matplotlib.pyplot as plt
points = [
[22.7433333333000, 53.4869444444000],
[23.2530555556000, 53.5683333333000],
[23.1066666667000, 53.7200000000000],
[22.8452777778000, 53.7758333333000],
[23.0952777778000, 53.4413888889000],
[23.4152777778000, 53.5233333333000],
[22.9175000000000, 53.5322222222000],
[22.7197222222000, 53.7322222222000],
[22.9586111111000, 53.4594444444000],
[23.3425000000000, 53.6541666667000],
[23.0900000000000, 53.5777777778000],
[23.2283333333000, 53.4713888889000],
[23.3488888889000, 53.5072222222000],
[23.3647222222000, 53.6447222222000]]
vor = Voronoi(points)
voronoi_plot_2d(vor)
plt.axis('equal')
plt.xlim(22.65, 23.50)
plt.ylim(53.35, 53.85)
plt.show()
它生成这个图：
现在这里有一个 javascript 程序，它使用 d3.geom.voronoi:
<html>
<head>
<script type="text/javascript" src="http://mbostock.github.com/d3/d3.js"></script>
<script type="text/javascript" src="http://mbostock.github.com/d3/d3.geom.js"></script>
</head>
<body>
<div id="chart">
</div>
<script type="text/javascript">
// This code is a hacked up version of http://bl.ocks.org/njvack/1405439
var w = 800,
h = 400;
var data = [
[22.7433333333000, 53.4869444444000],
[23.2530555556000, 53.5683333333000],
[23.1066666667000, 53.7200000000000],
[22.8452777778000, 53.7758333333000],
[23.0952777778000, 53.4413888889000],
[23.4152777778000, 53.5233333333000],
[22.9175000000000, 53.5322222222000],
[22.7197222222000, 53.7322222222000],
[22.9586111111000, 53.4594444444000],
[23.3425000000000, 53.6541666667000],
[23.0900000000000, 53.5777777778000],
[23.2283333333000, 53.4713888889000],
[23.3488888889000, 53.5072222222000],
[23.3647222222000, 53.6447222222000]
];
// Translate and scale the points. The same scaling factor (2*h) must be used
// on x and y to preserve the relative distances among the points.
// The y coordinates are also flipped.
var vertices = data.map(function(point) {return [2*h*(point[0]-22.5), h - 2*h*(point[1]-53.4)]})
var svg = d3.select("#chart")
.append("svg:svg")
.attr("width", w)
.attr("height", h);
var paths, points;
points = svg.append("svg:g").attr("id", "points");
paths = svg.append("svg:g").attr("id", "point-paths");
paths.selectAll("path")
.data(d3.geom.voronoi(vertices))
.enter().append("svg:path")
.attr("d", function(d) { return "M" + d.join(",") + "Z"; })
.attr("id", function(d,i) {
return "path-"+i; })
.attr("clip-path", function(d,i) { return "url(#clip-"+i+")"; })
.style("fill", d3.rgb(230, 230, 230))
.style('fill-opacity', 0.4)
.style("stroke", d3.rgb(50,50,50));
points.selectAll("circle")
.data(vertices)
.enter().append("svg:circle")
.attr("id", function(d, i) {
return "point-"+i; })
.attr("transform", function(d) { return "translate(" + d + ")"; })
.attr("r", 2)
.attr('stroke', d3.rgb(0, 50, 200));
</script>
</body>
</html>
它生成：
根据对结果的目视检查，我认为它们生成了相同的 Voronoi 图。
背景
我正在处理 csv 文件中包含的一组 8000 个地理点。一方面，我创建了使用这些点构建的 Voronoi 图的可视化 - 它是使用 D3 库完成的。另一方面，我使用 Scipy.
在 Python 中计算这些 Voronoi 图我的工作逻辑很简单——我在 Python 那边处理我的数据，制作热图、分析等等，然后我使用 D3 可视化效果。但是今天无意间发现Scipy和D3做的Voronoi图不一样。我注意到在使用 geojson.io 绘制在 Python 中制作的 Voronois 的 GeoJsons 之后，我只是想看看我是否可以将那里的所有内容可视化。
正如我所说，Voronois 是不同的 - 其中一些有不同的角度，有些甚至有额外的顶点。
问题：
为什么会这样？为什么这两个库（D3 和 Scipy）计算出的 Voronoi 图不同？
进一步说明
如何在 D3 端完成：基于 Chris Zetter 示例 http://chriszetter.com/blog/2014/06/15/building-a-voronoi-map-with-d3-and-leaflet/ 我将纬度和经度转换为自定义投影以在 mapbox 地图上将其可视化。
var voronoi = d3.geom.voronoi()
.x(function(d) { return d.x; })
.y(function(d) { return d.y; })
.clipExtent([[N_W.x , N_W.y],[S_E.x, S_E.y]])
我根据地图边界内可见的点 + 一些填充 (filteredPoints) 创建 Voronoi
filteredPoints = points.filter(function(d) {
var latlng = new L.LatLng(d.latitude, d.longitude);
if (!drawLimit.contains(latlng)) { return false };
// this translates points from coordinates to pixels
var point = map.latLngToLayerPoint(latlng);
key = point.toString();
if (existing.has(key)) { return false };
existing.add(key);
d.x = point.x;
d.y = point.y;
return true;
});
voronoi(filteredPoints).forEach(function(d) { d.point.cell = d});
Python这边是怎么做的：我用scipy.spatial.Voronoi.
from scipy.spatial import Voronoi
def create_voronois():
points = numpy.array(points_list)
vor = Voronoi(points)
其中 "points_list" 是我的 8000 个地理点的列表。
编辑：
我的可视化屏幕截图 - 黑色边框是用 D3 制作的 Voronois，白色边框是由 scipy.spatial.Voronoi 制作的。我们可以看到 scipy 是错误的。有人比较过这两个库吗？
编码为运行。它使用计算错误的 Voronois 打印 GeoJson。
import numpy
from scipy.spatial import Voronoi
from geojson import FeatureCollection, Feature, Polygon
points = [
[22.7433333333000, 53.4869444444000],
[23.2530555556000, 53.5683333333000],
[23.1066666667000, 53.7200000000000],
[22.8452777778000, 53.7758333333000],
[23.0952777778000, 53.4413888889000],
[23.4152777778000, 53.5233333333000],
[22.9175000000000, 53.5322222222000],
[22.7197222222000 ,53.7322222222000],
[22.9586111111000, 53.4594444444000],
[23.3425000000000, 53.6541666667000],
[23.0900000000000, 53.5777777778000],
[23.2283333333000, 53.4713888889000],
[23.3488888889000, 53.5072222222000],
[23.3647222222000 ,53.6447222222000]]
def create_voronois(points_list):
points = numpy.array(points_list)
vor = Voronoi(points)
point_voronoi_list = []
feature_list = []
for region in range(len(vor.regions) - 1):
vertice_list = []
for x in vor.regions[region]:
vertice = vor.vertices[x]
vertice = (vertice[1], vertice[0])
vertice_list.append(vertice)
polygon = Polygon([vertice_list])
feature = Feature(geometry=polygon, properties={})
feature_list.append(feature)
feature_collection = FeatureCollection(feature_list)
print feature_collection
create_voronois(points)
显然，您的 javascript 代码在计算 Voronoi 图之前对数据应用了转换。此转换不会保留点的相对距离，因此不会生成与您的 scipy 代码相同的结果。请注意，我并不是说您的 d3 版本不正确。鉴于数据是纬度和经度，您在 javascript 代码中所做的可能是正确的。但是要将其与 scipy 代码进行比较，如果您希望获得相同的 Voronoi 图，则必须进行相同的转换。
下面的脚本显示，如果您保留输入点的相对距离，scipy 的 Voronoi 函数和 d3.geom.voronoi 生成相同的图表。
这是一个使用 scipy 的 Voronoi 代码的脚本：
import numpy
from scipy.spatial import Voronoi, voronoi_plot_2d
import matplotlib.pyplot as plt
points = [
[22.7433333333000, 53.4869444444000],
[23.2530555556000, 53.5683333333000],
[23.1066666667000, 53.7200000000000],
[22.8452777778000, 53.7758333333000],
[23.0952777778000, 53.4413888889000],
[23.4152777778000, 53.5233333333000],
[22.9175000000000, 53.5322222222000],
[22.7197222222000, 53.7322222222000],
[22.9586111111000, 53.4594444444000],
[23.3425000000000, 53.6541666667000],
[23.0900000000000, 53.5777777778000],
[23.2283333333000, 53.4713888889000],
[23.3488888889000, 53.5072222222000],
[23.3647222222000, 53.6447222222000]]
vor = Voronoi(points)
voronoi_plot_2d(vor)
plt.axis('equal')
plt.xlim(22.65, 23.50)
plt.ylim(53.35, 53.85)
plt.show()
它生成这个图：
现在这里有一个 javascript 程序，它使用 d3.geom.voronoi:
<html>
<head>
<script type="text/javascript" src="http://mbostock.github.com/d3/d3.js"></script>
<script type="text/javascript" src="http://mbostock.github.com/d3/d3.geom.js"></script>
</head>
<body>
<div id="chart">
</div>
<script type="text/javascript">
// This code is a hacked up version of http://bl.ocks.org/njvack/1405439
var w = 800,
h = 400;
var data = [
[22.7433333333000, 53.4869444444000],
[23.2530555556000, 53.5683333333000],
[23.1066666667000, 53.7200000000000],
[22.8452777778000, 53.7758333333000],
[23.0952777778000, 53.4413888889000],
[23.4152777778000, 53.5233333333000],
[22.9175000000000, 53.5322222222000],
[22.7197222222000, 53.7322222222000],
[22.9586111111000, 53.4594444444000],
[23.3425000000000, 53.6541666667000],
[23.0900000000000, 53.5777777778000],
[23.2283333333000, 53.4713888889000],
[23.3488888889000, 53.5072222222000],
[23.3647222222000, 53.6447222222000]
];
// Translate and scale the points. The same scaling factor (2*h) must be used
// on x and y to preserve the relative distances among the points.
// The y coordinates are also flipped.
var vertices = data.map(function(point) {return [2*h*(point[0]-22.5), h - 2*h*(point[1]-53.4)]})
var svg = d3.select("#chart")
.append("svg:svg")
.attr("width", w)
.attr("height", h);
var paths, points;
points = svg.append("svg:g").attr("id", "points");
paths = svg.append("svg:g").attr("id", "point-paths");
paths.selectAll("path")
.data(d3.geom.voronoi(vertices))
.enter().append("svg:path")
.attr("d", function(d) { return "M" + d.join(",") + "Z"; })
.attr("id", function(d,i) {
return "path-"+i; })
.attr("clip-path", function(d,i) { return "url(#clip-"+i+")"; })
.style("fill", d3.rgb(230, 230, 230))
.style('fill-opacity', 0.4)
.style("stroke", d3.rgb(50,50,50));
points.selectAll("circle")
.data(vertices)
.enter().append("svg:circle")
.attr("id", function(d, i) {
return "point-"+i; })
.attr("transform", function(d) { return "translate(" + d + ")"; })
.attr("r", 2)
.attr('stroke', d3.rgb(0, 50, 200));
</script>
</body>
</html>
它生成：
根据对结果的目视检查，我认为它们生成了相同的 Voronoi 图。