我有球体的表面上的很多点。 我如何计算具有最大点密度球体的面积/点？ 我需要这样做非常快。如果这是例如方形我想我可以创建一个网格，然后让点票而电网的一部分，是最好的。 我曾尝试与转变点球面坐标，然后做一个网格，这两者并没有很好地工作，因为围绕北极点收盘球，但后面的变换遥远。

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）可以计算每个小区的平坦区域中，通过假设边为直线 - 这种近似可能是pretty的良好时格是足够致密，或（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.

如果您有兴趣进行必要的点式电池的查询效率，一种方法是构建网格作为的四叉树 - 从粗刻多面体和改进它面临到的子脸一棵树。要找到封闭小区，你可以简单地遍历从根，这是一个典型的 0的树（的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.