如何生成指定半径内的随机圆形坐标？

Question

我正在尝试生成随机坐标（纬度，经度），这些坐标位于以某些坐标（x，y）为中心点，半径为5公里的圆内。我正在使用ruby编写代码，并使用该方法，但是不知何故，我得到的结果并不在指定的5公里半径范围内。

def location(lat, lng, max_dist_meters)
  max_radius = Math.sqrt((max_dist_meters ** 2) / 2.0)
  lat_offset = rand(10 ** (Math.log10(max_radius / 1.11)-5))
  lng_offset = rand(10 ** (Math.log10(max_radius / 1.11)-5))
  lat += [1,-1].sample * lat_offset
  lng += [1,-1].sample * lng_offset
  lat = [[-90, lat].max, 90].min
  lng = [[-180, lng].max, 180].min
  [lat, lng]
end

- Denis S.

---

为什么不生成一个随机半径和角度，并将它们应用到你的中心点？ - mu is too short

在圆内随机生成的坐标将与圆心具有随机距离。我相信这就是mu所说的"random radius"。生成一个角度来指示方向，并确定前进的距离，是在圆内获取点的一种自然方法。 - pjs

谢谢大家的回复，我应该在上面的方法中改变和添加什么才能得到正确的结果？ - Denis S.

你需要更仔细地定义“随机坐标”。如果坐标位于固定网格上，使得相邻坐标（水平或垂直）之间的距离是固定的，那么你不能使用角度和距离来获取这些坐标。如果你选择了最接近给定极坐标的“矩形”坐标，那么会严重偏向中心附近的坐标——也就是说，它不是随机的。请编辑以澄清坐标的布局。 - Cary Swoveland

使用常量分布生成随机半径会使图形偏向圆的中心。 - sawa

Answer 1

你的代码

max_radius = Math.sqrt((max_dist_meters ** 2) / 2.0)

这只是max_dist_meters.abs / Math.sqrt(2)或者max_dist_meters * 0.7071067811865475。

10 ** (Math.log10(max_radius / 1.11)-5)

这可以写成9.00901E-6 * max_radius，所以它是6.370325E−6 * max_dist_meters。

rand(10 ** (Math.log10(max_radius / 1.11)-5))

现在来到有趣的部分：rand(x) 当 x 在 -1 和 1 之间时就是 rand()。因此，如果 max_dist_meters 小于 1/6.370325E−6 ~ 156977.86，你前三行代码所做的只是：

lat_offset = rand()
lng_offset = rand()

当max_dist_meters = 5000时，您的方法将返回一个随机点，该点可能离原点1°经度和1°纬度。最多可能会超过157公里。

更糟糕的是，如果x在156978和313955之间，您的代码等价于:

lat_offset = lng_offset = 0

自 Ruby 2.4 版本起

[[-90, lat].max, 90].min

可以这样写：lat.clamp(-90, 90)

可能的解决方案

为了在半径为max_radius的圆盘上获得均匀随机点分布，需要非均匀分布的随机半径：

def random_point_in_disk(max_radius)
  r = max_radius * rand ** 0.5
  theta = rand * 2 * Math::PI
  [r * Math.cos(theta), r * Math.sin(theta)]
end

这是一个有一百万个随机点的图：

这是使用@Schwern的代码生成的相同图：

一旦你有了这个方法，就可以应用一些基本的数学知识将米转换为纬度和经度。只需记住：1°纬度始终为111.2公里，但在赤道时1°经度也为111.2公里；而在极地时则为0公里。

def random_point_in_disk(max_radius)
  r = max_radius * rand**0.5
  theta = rand * 2 * Math::PI
  [r * Math.cos(theta), r * Math.sin(theta)]
end

EarthRadius = 6371 # km
OneDegree = EarthRadius * 2 * Math::PI / 360 * 1000 # 1° latitude in meters

def random_location(lon, lat, max_radius)
  dx, dy = random_point_in_disk(max_radius)
  random_lat = lat + dy / OneDegree
  random_lon = lon + dx / ( OneDegree * Math::cos(lat * Math::PI / 180) )
  [random_lon, random_lat]
end

对于这种计算，没有必要安装一个重达800磅的GIS巨人。

几点说明：

• 通常我们按纬度先后顺序谈论，但在GIS中，通常首先是lon，因为x在y之前。
• cos(lat)被认为是恒定的，所以max_radius不应该太大。几十公里不应该有任何问题。球面上的圆盘形状会变得奇怪和扁平。
• 不要在距离极点太近的地方使用此方法，否则您将获得任意大的坐标。

为了测试它，让我们在不同位置创建200公里半径的随机点：

10_000.times do
  [-120, -60, 0, 60, 120].each do |lon|
    [-85, -45, 0, 45, 85].each do |lat|
      puts random_location(lon, lat, 200_000).join(' ')
    end
  end
end

使用 gnuplot，这是结果图表：

耶！我刚刚重新发明了 Tissot's indicatrix，只晚了150年：

- Eric Duminil

---

我喜欢你提到了转换回经纬度的问题，做得很好！ - pjs

这个公式中的theta是什么意思？我试着搜索一下2pi是什么意思，但结果只让我陷入了一个兔子洞。请同时包括r的含义。 - captainskippah

@doesnotmatter 这是极坐标系中的角度：https://zh.wikipedia.org/wiki/%E6%9E%81%E5%9D%90%E6%A0%87%E7%B3%BB。 - Eric Duminil

有人有想法如何用C#实现这个功能吗？'def random_point_in_disk(max_radius) r = max_radius * rand ** 0.5 theta = rand * 2 * Math::PI [r * Math.cos(theta), r * Math.sin(theta)] end' - STORM

@STORM: 这是 我的第一个C#程序。从我的理解来看，它应该给出与我上面的Ruby代码相同的随机分布。 - Eric Duminil

Answer 2

def location(x_origin, y_origin, radius)
  x_offset, y_offset = nil, nil
  rad = radius.to_f

  begin
    x_offset = rand(-rad..rad)
    y_offset = rand(-rad..rad)
  end until Math.hypot(x_offset, y_offset) < radius

  [x_origin + x_offset, y_origin + y_offset] 
end

- Mori

---

@CarySwoveland 你把随机性和均匀性等同起来了。另一种解决方案肯定是随机的，只是不均匀。 - pjs

@CarySwoveland 不，你想的是离散均匀性。在数学上，我们不是从一个固定的N个项目集中选择项目，而是在连续空间上进行样本抽取，因此可能的点数（理论上）是无限的。（好吧，计算上它不是无限的，但非常大...）一维均匀性意味着期望点数与区间长度成比例；在二维中，均匀性意味着与面积成比例；在三维中，与体积成比例；等等。 - pjs

@CarySwoveland：如果你想要更多关于统一性的信息，请看一下我的答案。 - Eric Duminil

@EricDuminil 这并不完全清楚它是否更加高效。这可以比拟使用Marsaglia的“极坐标法”与Box-Muller变换来生成高斯随机变量。基于接受/拒绝的极坐标法通常被发现能够胜过Box-Muller方法，而这让很多人感到惊讶，因为它避免了正弦/余弦三角函数的耗时计算。 - pjs

@EricDuminil 正确。更好的方法是比较 x*x + y*y < radius_squared，除非你的优化编译器足够聪明，能够意识到它不需要取对数、乘法和指数运算来计算平方。 - pjs

Answer 3

有一个宝石可以做你需要的事情。

https://github.com/sauloperez/random-location

只需安装 gem 并在您的代码中引用它：

：

gem install random-location
require 'random-location'
RandomLocation.near_by(41.38506, 2.17340, 10000)

- mopx

Answer 4

我建议生成随机半径和随机角度。然后，您可以使用这些来生成一个坐标，使用Math.sin和Math.cos函数。

def location(max_radius)
    # 0 to max radius.
    # Using a range ensures max_radius is included.
    radius = Random.rand(0.0..max_radius)

    # 0 to 2 Pi excluding 2 Pi because that's just 0.
    # Using Random.rand() because Kernel#rand() does not honor floats.
    radians = Random.rand(2 * Math::PI)

    # Math.cos/sin work in radians, not degrees.
    x = radius * Math.cos(radians)
    y = radius * Math.sin(radians)

    return [x, y]
end

我会把这个转换为经纬度并添加一个中心点。

实际上，我建议找到一个支持操作如“在此形状内给我一个随机点”、“此点是否在此形状内”的几何库，并会为您执行经纬度转换的库，因为这些东西很容易出现微妙的错误。

你可以在Ruby geometry gem的基础上构建，它为你提供了基本形状的类。如果你的数据在数据库中，许多数据库都支持像PostgreSQL的几何类型，更强大的PostGIS附加组件，甚至MySQL有空间数据类型。

- Schwern

---

这会产生靠近圆心的点。如果你想让点在整个圆上均匀分布，可以将 radius = rand(0.0..max_radius) 替换为 radius = max_radius * Math.sqrt(rand)。 - pjs

您希望点数与面积成比例，而圆的面积随半径的平方增长，因此需要进行平方根修正以正确调整事物。 - pjs

如果你不相信我的直觉面积论证，请参考http://mathworld.wolfram.com/DiskPointPicking.html。我认为Mathematica的创建者在这方面有信誉。 - pjs

请参见http://narimanfarsad.blogspot.com/2012/11/uniformly-distributed-points-inside.html 以获得更严谨的证明。 - pjs

@Schwern：此外，这种“奇怪的行为”在文档中有所描述：rand(1.9)被解释为rand(1)，其结果总是0。 - Eric Duminil