如何将一组数字转换为大多数是整数？

Question

一些背景信息：我正在开发一个转换器，用于连接一个输出XML格式的地图制作软件(Tiled)和一个接收lua表格的引擎(Angel2D)。大部分内容都很简单。

然而，Tiled输出像素偏移量（绝对值的整数），而Angel2D输入OpenGL单位（相对值的浮点数）；需要一个这两者之间的转换因子（例如32px=1gu）。由于OpenGL单位是抽象的，并且如果对象太小或太大，则摄像机可以缩放，实际的转换因子并不重要；我可以使用一个随机数，用户只需缩放即可。

但最好选择这样的转换因子，使得大多数输出数字都是小数或小数部分，因为这样更容易处理（而OpenGL单位的整个目的就是易于处理）。

如何可靠地找到这样的转换因子？

我最初尝试使用给定的最小数字；这导致没有小于1的分数，但通常会导致因子不对齐而产生很多小数位。
然后我尝试了序列的模式，这导致可能的最大数量的1，但通常会导致非常长的背景图像浮点数。
我的当前方法是获取整个序列的GCD，当它起作用时，效果很好，但单个坏苹果容易使其失效。
请注意，虽然我可以轻松地传递我得到的数字，或选择一些固定因子，或使用我上面指定的转换之一，但我正在寻找可靠地将这个整数列表缩放为小的整数或简单分数的方法，因为这最可能对最终用户来说不会出乎意料；这不是一次性的转换。
最终用户倾向于将1.0作为操作的“基础”（因为它简单明了），因此实体的大小更接近于这个值。

- Alice

---

直接从Tiled传递整数值到OpenGL即可。只要整数的绝对值小于2 ** 23，将它们转换为浮点数时就不会丢失信息。 - datenwolf

@datenwolf 虽然这样做可以起作用，但它并不真正适合最终用户的工作流程或是“出人意料”。 - Alice

如何找出一些可接受的因子，并构造一个拥有它们作为因数的数字。需要的是最小的质数，因为中间的合数是它们的乘积。要同时考虑它们作为除数，可以将原始数字按所有质数的公共因子进行缩放，然后在其中运行GCD，所有x和所有y。235711*13=30030，因此在运行GCD之前将所有内容都按整数30030进行缩放。然后GCD(...) / 30030就是您想要使用的分数基数。请注意，许多数字可以进一步简化，即2/2等于1。 - Apriori

Answer 1

如何找到“一些值的最大公因数”，例如100%的值的最大公因数就是这些值的最大公因数。你也可以选择60%的值的最大公因数，虽然这不是一个精确的最大公因数，但可以作为一个“粗略的最大公因数”。你可能需要通过尝试和错误来找到它，或者使用二分查找。另外，你也可以考虑对样本进行采样，例如从一百万个数据点中随机选择100或1000个，以找到能够整除目标百分比的数字，这也许已经足够了。以下是一些伪C语言代码。

/** return percent of values in sampleset for which x is a factor */
double percentIsFactorOf(x, sampleset) {
  int factorCount = 0;

  for (sample : sampleset) 
     if (sample%x == 0) factorCount++;

  return (double)factorCount/sampleset.size;    
}

/** find largest value which is a factor of goalPercentage of sampleset */
double findGoodEnoughCommonFactor(sampleset, goalPercentage) {
   // slow n^2 alogrithm here - add binary search, sampling, or something smarter to improve if you like
   int start = max(sampleset);
   while (percentIsFactorOf(start, sampleset)< goalPercent)
     start--;
}

- Zach Fewtrell

---

这是一个好主意，但我希望得到一个更精确的解决方案，而不是近似或蛮力解决方案。 - Alice

Answer 2

如果您的输入在N ^ 2（即两个维度空间覆盖自然数域，即非负整数），并且您需要输出到R ^ 2（即两个维度空间覆盖实数域，在本例中将使用浮点数表示/近似）。

暂时忘记缩放，并且让输出与输入处于相同的比例尺。第一步是意识到输入坐标<0,0>不代表输出中的<0,0>，它代表像素中心的<0.5f，0.5f>。类似地，输入<2,3>变为<2.5,3.5>。通常可以按照以下方式执行转换：

float x_prime = (float)x + 0.5f;
float y_prime = (float)y + 0.5f;

接下来，你可能想选择一个缩放因子，正如你所提到的。我一直发现选择一些真实世界的单位非常有用，通常是米。这样你就可以推理出你试图模拟的其他物理方面，因为它们有单位；例如速度、加速度，现在可以是每秒米，或每秒平方米。你正在制作的东西有多少米高或宽？一个像素相当于多少米？选择一些有意义的东西，然后你的公式就变成了：

float x_prime = ((float)x + 0.5f) * (float)units_per_pixel;
float y_prime = ((float)y + 0.5f) * (float)units_per_pixel;

您可能不希望所有输出坐标都在正象限内，也就是说，您可能希望原点位于对象的中心。如果是这样，您可能希望起始坐标系的字段包括负整数，或者提供一些偏移量到真正的中心。假设您提供了一个像素偏移量到真正的中心。那么您的转换将变成这样：

float x_prime = ((float)x + 0.5f - (float)x_offset) * (float)units_per_pixel;
float y_prime = ((float)y + 0.5f - (float)y_offset) * (float)units_per_pixel;

- Apriori

---

这是一篇很好的分析，但问题在于我正在编写一个工具；您提到的中间步骤（选择有意义的内容）是我无法了解的。虽然我会允许最终用户选择他们认为有意义的转换系数，但我希望默认方法能够找到一个转换系数，大多数情况下都会生成小而整数的结果，这样更容易被理解。 - Alice

@Alice：那么对于默认比例，我建议尝试以下方法：将0到1之间的数字缩放到0到100之间，这就是百分比的工作原理，普遍认为它们很直观。直接的方法是按100/max(magnitude(all_points))的因子进行缩放。然而，异常值会使你混乱不堪。你可以尝试丢弃前10%的幅度并取其中的最大值，即100除以第90个百分位数的幅度。 - Apriori

但我想这并没有真正解决整数的问题。然而，对我来说，如果在一个众所周知的范围内，如0到100之间，那么这些值会更直观，而不是通过消除小数部分来实现。 - Apriori

Answer 3

我不知道你所说的“GL单位”是什么。

在最抽象的层面上，GL没有单位。顶点坐标最初处于对象空间中，并经过半打用户定义的转换，最终产生具有熟悉单位（像素）的坐标（窗口空间）。

即使在窗口空间中，坐标仍然不是整数。实际上，您不希望它是整数，否则三角形会跳来跳去，而且通常不会像三角形那样，如果它们的顶点位置被捕捉到整数像素坐标。

相反，GL将子像素精度引入混合。坐标最终仍然被量化为整数值，但每个整数可能涵盖8位子像素精度下的1/256像素。如下图所示，像素覆盖测试是在子像素级别上完成的：

_{(来源：microsoft.com)}

GL从不尝试找到像你所讨论的那样的转换因子，它只是将像素坐标的数字空间分成固定的整数和小数部分... 换句话说，使用固定点。您可以考虑采用相同的方法。

- Andon M. Coleman

---

被调用以在OpenGL中设置位置的函数是(glTranslatef)[https://www.talisman.org/opengl-1.1/Reference/glTranslate.html]，它涉及X、Y和Z坐标。那么，你会如何称呼其中一个抽象单位？我曾看到它被称为OGL单位，并认为这个术语很有用；关键是我从具体的基于像素的单位开始，希望以尽可能“不出人意料”的方式转换到OpenGL的抽象单位上，以便最终用户能够处理小数字。 - Alice

@Alice：这些坐标是无单位的。glTranslate（...）适用于平移矩阵。它将当前矩阵乘以另一个应用平移的矩阵。由于矩阵定义了坐标空间变换，因此矩阵本身是无单位的。在 GL 中，只有在视口变换之后，坐标才开始以像素（或任何具体单位）为单位进行测量，在此之前，单位可以是任何你想要的东西。 - Andon M. Coleman

@Alice：如果你刚开始使用像素单位，并且希望物体空间坐标为整数，请使用正交投影矩阵并将比例限制为整数值。唯一可能有趣的事情是像素中心实际上是 i + 0.5。因此，在窗口空间中，位于像素中心（x，y）的点将是（x+0.5，y+0.5）。 - Andon M. Coleman

Answer 4

放弃你的背景信息，我明白你试图解决的根本问题是：

给定有限个（正）整数{x_1，... x_N}，找到一些（有理）数f，使得所有x_i / f都是“好的”。

如果您坚持认为“好”意味着整数且尽可能小，则GCD是这个问题的（数学上）确切答案。如果GCD为1，则没有更好的解决方案。

如果“好”意味着有理数且分子和分母都很小，则问题变得更加有趣，具体取决于“小”的含义，可以在最大值（f = max）和最小公共分母（f = GCD）之间进行权衡。然而，请注意，小的分子/分母并不意味着小的浮点表示，例如1/3 = 0.333333...在十进制中。

如果您想要短小的浮点数（floating points），请确保f是您的基数的幂，即10或2，具体取决于数字是否应该对用户看起来很短或实际上具有合理的机器表示。 这就是用于浮点数的科学表示法，这可能是如何使十进制数在第一次看起来漂亮的最佳答案。

- Echsecutor

Answer 5

你可以重复使用用于向量归一化的代码，并将值归一化为最大值为1；例如：

3D向量归一化的公式在此处很好用。首先获取长度：

|a| = sqrt((ax * ax) + (ay * ay) + (az * az))

然后，您需要将每个组件的值除以长度：

x = ax/|a|
y = ay/|a|
z = az/|a|

现在所有的x，y，z值都将落入-1到1的最大值，与OpenGL基坐标系相同。

我知道这不会生成您想要的整数系统，但它确实可以使范围更小、更统一。

假设你只想限制范围为整数，只需使用以下函数，它将把归一化的值转换为仅限于整数的范围值：

#include <algorithm>    // this allows the use of std::min
int maxVal = 256
unsigned char convertToSpread(float floatValueToConvert){
    return (unsigned char) (std::min((maxVal-1), (int) (floatValueToConvert * maxVal)));
}

上述代码将把您的值在0到255之间分配，只需增加maxVal的值并将unsigned char更改为适合您需求的数据类型即可。因此，如果您需要1024个值，只需将maxVal更改为1024，将unsigned char更改为unsigned int。

希望这能帮到您，如果您需要更多信息，请告诉我，我可以详细说明 :)

- GMasucci