如何有效地枚举球体的所有点在n维网格 [英] How to efficiently enumerate all points of sphere in n-dimensional grid

问题描述

说，我们有一个N维网格和一些点X在它与坐标（X1，X2，...，XN）。 为简单起见，我们可以假定电网是无界的。

Say, we have an N-dimensional grid and some point X in it with coordinates (x1, x2, ..., xN). For simplicity we can assume that the grid is unbounded.

让要有一个半径为R，该半径与X中心的球体，即在网格中的集合中的所有点，使得从x他们的曼哈顿距离等于R.

Let there be a radius R and a sphere of this radius with center in X, that is the set of all points in grid such that their manhattan distance from X is equal to R.

我怀疑他们将是2 * N * R这样的点。

I suspect that their will be 2*N*R such points.

我的问题是：我怎么一一列举在高效和简单的方式？由枚举我的意思的算法，其中，由于N，X和R将产生形成本领域（其中点是它的座标表）的点的列表。

My question is: how do I enumerate them in efficient and simple way? By "enumerate" I mean the algorithm, which, given N, X and R will produce the list of points which form this sphere (where point is the list of it's coordinates).

更新：最初，我叫公制我用汉明距离错误。我向大家致歉谁回答了这个问题。感谢史蒂夫·杰索普指出了这一点。

UPDATE: Initially I called the metric I used "Hamming distance" by mistake. My apologies to all who answered the question. Thanks to Steve Jessop for pointing this out.

推荐答案

考虑最小轴对齐的立方体的界定的超球，并写了一个程序来枚举网格点的超立方体内。

Consider the minimal axis-aligned hypercube that bounds the hypersphere and write a procedure to enumerate the grid points inside the hypercube.

那么你只需要一个简单的过滤功能，可以让你放弃是立方体，但不是在超球点。

Then you only need a simple filter function that allows you to discard the points that are on the cube but not in the hypersphere.

这是小尺寸的简单和有效的解决方案。例如，对于2D，列举为正方形被丢弃的边界的点的20％;为6D，超立方体点的近90％都将被丢弃。

This is a simple and efficient solution for small dimensions. For instance, for 2D, 20% of the points enumerated for the bounding square are discarded; for 6D, almost 90% of the hypercube points are discarded.

对于更高的层面，你将不得不使用更复杂的方法：遍历每一个层面（您可能需要使用递归函数，如果维数是可变的）。对于每一个循环，你将有根据已经计算网格成分的值来调整最小和最大的值。好了，试试做的2D，列举了一圈的点，一旦你了解它，推广的程序更高的尺寸将是pretty的简单。

For higher dimensions, you will have to use a more complex approach: loop over every dimension (you may need to use a recursive function if the number of dimensions is variable). For every loop you will have to adjust the minimal and maximal values depending on the values of the already calculated grid components. Well, try doing it for 2D, enumerating the points of a circle and once you understand it, generalizing the procedure to higher dimensions would be pretty simple.

更新：errh，等一下，你要使用的曼哈顿距离。调用交叉多面体球可能是正确的，但我觉得这是很混乱！在任何情况下，你可以使用相同的方法。

update: errh, wait a minute, you want to use the Manhattan distance. Calling the cross polytope "sphere" may be correct but I found it quite confusing! In any case you can use the same approach.

如果您只想列举在十字架上的多面体的超曲面的点，好了，解决办法也很相似，你必须遍历适当限制每一个层面。例如：

If you only want to enumerate the points on the hyper-surface of the cross polytope, well, the solution is also very similar, you have to loop over every dimension with appropriate limits. For instance:

for (i = 0; i <= n; i++)
  for (j = 0; j + i <= n; j++)
    ...
       for (l = 0; l + ...+ j + i <= n; l++) {
         m = n - l - ... - j - i;
         printf(pat, i, j, ..., l, m);
       }

有关生成的每一点，那么你将不得不考虑所有的变化导致否定任何组件覆盖所有的面，然后用矢量X取代它们。

For every point generated that way, then you will have to consider all the variations resulting of negating any of the components to cover all the faces and then displace them with the vector X.

更新

Perl实现为的情况下，其中X = 0：

Perl implementation for the case where X = 0:

#!/usr/bin/perl

use strict;
use warnings;

sub enumerate {
    my ($d, $r) = @_;

    if ($d == 1) {
        return ($r ? ([-$r], [$r]) : [0])
    }
    else {
        my @r;
        for my $i (0..$r) {
            for my $s (enumerate($d - 1, $r - $i)) {
                for my $j ($i ? (-$i, $i) : 0) {
                    push @r, [@$s, $j]
                }
            }
        }
        return @r;
    }
}

@ARGV == 2 or die "Usage:\n  $0 dimension radius\n\n";
my ($d, $r) = @ARGV;
my @r = enumerate($d, $r);
print "[", join(',', @$_), "]\n" for @r;

这篇关于如何有效地枚举球体的所有点在n维网格的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！