c++ - 你怎么能把一组数字变成大部分的整数呢？

Question

少量背景知识:我正在研究一个在 map 制作者之间架起桥梁的转换器 (Tiled)以 XML 格式输出，以及一个引擎 (Angel2D)输入lua表。其中大部分是直截了当的

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

但最好选择转换因子，使输出的大多数数字都是小整数(或小整数的分数)，因为这样更容易处理(OpenGL 单位的重点是他们很容易合作)。

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

我的第一次尝试是使用给定的最小数字；这导致没有小于 1 的分数，但通常会导致许多小数位，其中因数不对齐。

然后我尝试了序列的模式，这导致了尽可能多的 1，但通常会导致背景图像的 float 非常长。

我目前的方法获取整个序列的 GCD，当它工作时，效果很好，但很容易被一个坏苹果抛出轨道。

请注意，虽然我可以很容易地传递我给出的数字，或者选择一些固定因子，或者使用我上面指定的转换之一，但我正在寻找一种方法来可靠地将这个整数列表缩小到较小的范围，整数或简单分数，因为这对最终用户来说很可能并不奇怪；这不是一次性转换。

最终用户倾向于使用 1.0 作为他们操作的“基础”(因为它简单明了)，因此实体的大小围绕这个聚集更有意义。

Answer 1

'作为值的某些百分比的因素的最大数字'怎么样？ 所以 GCD 是值的“最大数，它是 100% 的因数”。 您可以选择最大的数字，例如 60% 的值。我不知道这是否是一个技术术语，但它有点像“粗略的 GCD，如果不是精确的 GCD”。

您可能需要反复试验才能找到它(可能是二分查找)。但你也可以考虑抽样。 IE。如果您有一百万个数据点，只需随机选择 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--;
}