数学：缩放坐标系以使某些点获得整数坐标

Question

这更像是一个数学问题。尽管如此，我正在寻找解决它的伪代码算法。

给定一维坐标系和若干点。点的坐标可能是浮点数。

现在我正在寻找一个因子来缩放这个坐标系，使得所有的点都在固定的数字上（即整数坐标）。

如果我没有弄错的话，只要点的数量不是无限的，就应该有一个解决方案。

如果我错了，这个问题没有解析解，那么我对一个尽可能接近的算法感兴趣。（即坐标看起来像15.0001）

如果你对具体的问题感兴趣： 我想克服Adobe Flash中著名的像素捕捉问题，当整个舞台被缩放时，会剪切位图边界的半个像素。我想找到一个理想的舞台缩放因子，使我的位图被放置在整个（屏幕）像素坐标上。

由于我在舞台上放置了两个位图，每个方向（x，y）的点数将为4。

谢谢！

- clamp

---

没有通用的解决方案，例如无理数。 - raven

@Jaime Pardos：但无理数不能表示为（有限的）浮点数，这似乎是他所拥有的。 @OP：一种通用但在实践中可能很愚蠢的解决方案是将浮点数表示为整数的分数，直到达到所需的精度。然后，您的比例因子是所有分母的乘积。 - gspr

谢谢，是的，让我们在这个问题中排除无理数。 - clamp

Answer 1

建议您将浮点数转换为有理数。固定一个公差epsilon，对于每个坐标，找到其在epsilon范围内的最佳有理逼近。

该算法和定义在这里 本节中概述。

一旦您将所有坐标转换为有理数，缩放比例由分母的最小公倍数给出。

请注意，后者可能会变得非常巨大，因此您可能需要尝试不同的epsilon值来控制分母。

- Alexandre C.

Answer 2

如果我处在你的情况下，我的个人倾向是使用有理数而不是浮点数。而你正在寻找的算法是寻找最小公倍数。

- Oleksandr Pryimak

---

谢谢，但这是不可能的，因为一旦舞台被缩放，Flash会引入浮点坐标。 - clamp

浮点数本质上是有理数。尽管利用它们允许的完整精度范围可能不切实际。 - biziclop

你可以将浮点数视为有理数（顺便说一下，它确实是有理数）。 - Oleksandr Pryimak

Answer 3

浮点数是一个整数，乘以二的幂次方（幂次方可能为负）。

因此，在您的输入中找到最大必要的二次幂，这将给您一个可行的比例因子。二的幂不仅仅是浮点数的指数的负一倍，它还有更多的内容（根据有效数字中最不重要的1位在哪里）。

这也是最优的，因为如果x乘以2的幂次方是奇数，则x在其浮点表示中已经处于最简有理形式，没有更小的整数可以将x乘以得到整数。

显然，如果您的输入中有大量和小量混合，则结果整数倾向于大于64位。因此，有一种分析解决方案，但考虑到您想要对结果进行的操作，可能并不是非常好的解决方案。

请注意，此方法将浮点数视为精确表示，但实际上它们并不是。通过将每个浮点数表示为具有较小分母的有理数（在某些定义的公差内），然后取所有分母的最小公倍数，您可能会获得更明智的结果。

问题在于近似过程——如果输入的浮点数是0.334[*]，我通常无法确定给它的人是否真的意味着0.334，或者它是有一些不准确的1/3。因此，我不知道是否要使用一个比例因子为3，并说缩放后的结果为1，还是使用一个比例因子为500，并说缩放后的结果为167。这只是一个输入，更不用说一堆输入了。

如果有4个输入并允许最终容差为0.0001，则可以找到每个输入的10个最接近的有限小数，然后尝试10^4种不同的可能性，并查看生成的比例因子是否给出任何远离整数的值。暴力搜索似乎很麻烦，但你至少可以在进行搜索时将搜索范围限制在一定范围内。此外，“最大分母”可以用因式分解中存在的质数来表示，而不仅仅是数字，因为如果你能在它们之间找到很多公共因子，那么它们就会有较小的lcm，因此在缩放后偏离整数的程度也会更小。

[*] 不是0.334是一个精确的浮点值，而是那种情况。十进制的例子更容易理解。

- Steve Jessop

Answer 4

如果你在谈论单精度浮点数，那么根据维基百科，这个数字可以被表示为以下形式：

从这个公式中，你可以推断出如果你乘以2¹²⁷⁺²³，你总是会得到一个整数。(实际上，当e为0时，你必须使用另一个公式来处理“次正常”数字的特殊范围，因此2¹²⁶⁺²³就足够了。有关详细信息，请参见链接的维基百科文章。)

要在代码中实现这一点，你可能需要进行一些位操作，从浮点值的位中提取上述公式中的因子。然后，你将需要某种支持无限大小数字的支持来表示缩放的整数结果(例如.NET中的BigInteger)。大多数语言/平台中的普通原始类型通常被限制在更小的尺寸。

- Wim Coenen

Answer 5

这实际上是涉及到统计推断和噪声消除的问题。这是我即将尝试的方法。我假设你想要获得一个规则的二维网格，但类似的方法也可以用于三维或更多维度的规则网格。

首先列出所有差异并注意到(dx,dy)和(-dx,-dy)表示相同的位移，因此存在一种等价关系。将那些在预先指定的阈值(epsilon)内彼此接近的差异分组。Epsilon应足够大，以捕捉由于随机噪声或图像分辨率不足而产生的测量误差，但又不能太小，以免意外合并簇。

按它们的平均大小(dr = root(dx^2 + dy^2))对聚类进行排序。

如果原始网格确实是由两个独立基向量生成的规则间距网格，那么最小的两个线性独立簇将表明如此。最小的簇位于(0,0)中心。下一个最小的簇(dx0,dy0)具有第一个基向量，加上+/-号(-dx0，-dy0)表示相同的位移，回忆一下。

下一个最小的集群可能会线性依赖于(dx0，dy0)的倍数（在阈值epsilon内）。找到不是(dx0，dy0)的倍数的最小集群。将其称为(dx1，dy1)。

现在你有足够的信息来标记原始向量。按照字典顺序（x,y）>（x'，y'），如果x>x'或者x=x'且y>y'，对向量进行分组。取最小的(x0，y0)，并将整数(0,0)分配给它。取所有其他的(x,y)，并找到分解(x,y)=(x0,y0)+M0(x,y)(dx0,dy0)+M1(x,y)(dx1,dy1)，并将其分配整数(m0(x,y),m1(x,y))=(round(M0),round(M1))。

现在对整数进行最小二乘拟合，使其符合方程(x,y)=(ux,uy)m0(x,y)(u0x,u0y)+m1(x,y)(u1x,u1y)，以找到(ux,uy)，(u0x,u0y)和(u1x,u1y)。这将确定网格。

测试此匹配以确定所有点是否在给定阈值范围内符合此拟合（也许使用相同的 epsilon 阈值来实现此目的）。

这个相同例程的一维版本也应该适用于声谱仪上的一维，以识别语音图中的基本频率。只有在这种情况下，ux 的假设值（替换（ux，uy））为0，而且只需要寻找对于齐次方程 x = m0(x) u0x 的拟合。

- NinjaDarth