球体上密度最高的位置 [英] Location of highest density on a sphere

问题描述

我在球体表面有很多点.如何计算具有最大点密度的球体的面积/点?我需要非常快地完成这项工作.例如，如果这是一个正方形，我想我可以创建一个网格，然后让分数投票选出网格的哪一部分是最好的.我尝试将点转换为球坐标，然后做一个网格，这两种方法都不起作用，因为北极周围的点在球体上很近，但在转换后很远.

I have a lot of points on the surface of the sphere. How can I calculate the area/spot of the sphere that has the largest point density? I need this to be done very fast. If this was a square for example I guess I could create a grid and then let the points vote which part of the grid is the best. I have tried with transforming the points to spherical coordinates and then do a grid, both this did not work well since points around north pole are close on the sphere but distant after the transform.

谢谢

推荐答案

添加一些其他替代方案:可以通过细化内接多面体在类球体几何上定义许多(几乎)规则网格.

To add some other, alternative schemes to the mix: it's possible to define a number of (almost) regular grids on sphere-like geometries by refining an inscribed polyhedron.

第一个选项称为二十面体网格，它是球面的三角剖分.通过连接每个顶点的三角形中心，您还可以基于底层三角剖分创建双六边形网格:

The first option is called an icosahedral grid, which is a triangulation of the spherical surface. By joining the centres of the triangles about each vertex, you can also create a dual hexagonal grid based on the underlying triangulation:

如果您不喜欢三角形(和/或六边形)，另一种选择是立方球体网格，它是通过细分内接立方体的面并将结果投影到球面上形成的:

Another option, if you dislike triangles (and/or hexagons) is the cubed-sphere grid, formed by subdividing the faces of an inscribed cube and projecting the result onto the spherical surface:

在任何一种情况下，重要的一点是生成的网格几乎是规则的——所以要评估球体上密度最高的区域，您可以简单地执行直方图式分析，计算每个网格单元的样本数.

In either case, the important point is that the resulting grids are almost regular -- so to evaluate the region of highest density on the sphere you can simply perform a histogram-style analysis, counting the number of samples per grid cell.

正如许多评论者指出的那样，为了解决网格中的轻微不规则性，可以通过除以每个网格单元的面积来标准化直方图计数.然后将所得密度作为每单位面积"度量给出.要计算每个网格单元的面积，有两种选择:(i) 您可以计算每个单元的平坦"面积，假设边缘是直线——当网格足够时，这样的近似值可能非常好密集，或者 (ii) 您可以通过评估必要的表面积分来计算真实"表面积.

As a number of commenters have pointed out, to account for the slight irregularity in the grid it's possible to normalise the histogram counts by dividing through by the area of each grid cell. The resulting density is then given as a "per unit area" measure. To calculate the area of each grid cell there are two options: (i) you could calculate the "flat" area of each cell, by assuming that the edges are straight lines -- such an approximation is probably pretty good when the grid is sufficiently dense, or (ii) you can calculate the "true" surface areas by evaluating the necessary surface integrals.

如果您有兴趣高效地执行必要的单元内点"查询，一种方法是将网格构建为 四叉树——从一个粗糙的内接多面体开始，将它的面细化成一棵子面树.要定位封闭单元，您可以简单地从根遍历树，这通常是一个 O(log(n)) 操作.

If you are interested in performing the requisite "point-in-cell" queries efficiently, one approach is to construct the grid as a quadtree -- starting with a coarse inscribed polyhedron and refining it's faces into a tree of sub-faces. To locate the enclosing cell you can simply traverse the tree from the root, which is typically an O(log(n)) operation.

您可以在此处获得有关这些网格类型的一些其他信息.

You can get some additional information regarding these grid types here.

这篇关于球体上密度最高的位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！