算法用于装配点到电网 [英] Algorithm for fitting points to a grid

问题描述

我有形成一个（不完全）网格在二维空间中的点的列表：

I have a list of points in 2D space that form an (imperfect) grid:

x     x        x         x

 x    x       x           x

                 x
x      x                x

 x     x      x           x

什么是将它们装配到刚性网格（即创建一个双dimendional阵列和在哪里工作在阵列中的每个点适合）？

What's the best way to fit these to a rigid grid (i.e. create a two-dimendional array and work out where each point fits in that array)?

有在电网无孔，但我不知道在什么事先的尺寸。

There are no holes in the grid, but I don't know in advance what its dimensions are.

编辑：网格不一定是常规（非行/ COLS之间的均匀间距）

The grid is not necessarily regular (not even spacing between rows/cols)

推荐答案

在最后，我用这个算法，灵感来自于烧杯中的：

In the end I used this algorithm, inspired by beaker's:

1. 计算网格的所有可能的尺寸，给定的点的总数
2. 对于每一个可能的尺寸，适合指向尺寸并计算排列的变化：
   • 订购点由x值
   • 组点到列：第一R点构成的第一列，其中r是行数
   • 在每一列，以y值责令点，以确定他们在哪一行
   • 对于每一行/列，calcuate y值的范围/ x值
   • 在序列上的差异是最大的范围内找到

1. Calculate all the possible dimensions of the grid, given the total number of points
2. For each possible dimension, fit the points to that dimension and calculate the variance in alignment:
   • Order the points by x-value
   • Group the points into columns: the first r points form the first column, where r is the number of rows
   • Within each column, order the points by y-value to determine which row they're in
   • For each row/column, calcuate the range of y-values/x-values
   • The variance in alignment is the maximum range found

这篇关于算法用于装配点到电网的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！