累积面积的计算

Question

累积面积的计算

c++cdelphigis

16

我正在寻找一个GIS/几何算法：

在一个大面积（例如城市）随机分布了1000个点，如何找出所有有超过15个点的小区域？就像下面这张图片一样：

enter image description here

每个点都有自己的纬度和经度坐标。小区域的大小小于200米 x 200米。

- Leo

你使用哪种数据结构来管理你的点？ - Jørn E. Angeltveit

所有点都存储在数据库表中。 - Leo

数据库中没有一个可以做到这个的选择语句吗？ - Johan

1

顺便说一句，非常好的问题。喜欢它的清晰度。 - Johan

2个回答

0

不确定您的性能要求是什么。但是一个天真的实现方式是，对于每个点，将其与所有其他点的距离的倒数相加：

for i := 0 to 999 do
  for j := 0 to 999 do
    if i<>j then
      Point[i].Score := Point[i].Score + ( 1 / Distance(Point[i], Point[j]) );

每个聚集区中心附近的点将具有最高分数。

- Thorsten Engler

这种算法的性能为O(n^2)，对于任何大量的点都应该避免使用。对于1000个点，它会进行100万次计算。对于10000个点，它会进行1亿次计算！ - Cosmin Prund

我完全意识到这一点。“不确定您的性能要求是什么”和“天真的实现将是”。对于1000个点进行100万次计算，在现代CPU上仍然可以在相当合理的时间内完成，而提问者表示他有1000个点。这种方法的优点是它很容易实现，并且可能以可接受的性能运行（但这只有提问者才能决定，因为他没有给我们足够的信息来确定）。 - Thorsten Engler

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Arnaud Bouchez · Accepted Answer

您应该了解RTREE结构。请参阅http://en.wikipedia.org/wiki/R-tree。

您可以在SQLite3引擎中实现此类算法。请参阅http://www.sqlite.org/rtree.html。

我们的开源版本已经包含了Delphi 6至XE的RTREE扩展，自1.8版起默认编译。