algorithm - 如何在没有立方坐标的情况下找到多边形的质心？

Question

这个问题类似于一个现有的问题，除了当前问题需要多边形质心公式而不是立方体坐标，这对我的应用程序至关重要。

我正在处理的应用程序的性质需要整数坐标。为了计算面积，我们可以将位数加倍，即从 32 位到 64 位或从 64 位到 128 位，这样坐标乘法就不会溢出。对于多边形的质心，我们实现了标准公式，与上面引用的 SO 问题以及其他许多在线资源中的公式相同。但是，因为多边形公式的标准质心本质上是坐标的立方（通过将坐标乘以面积），所以我们不能使用它；我们已经在一些测试中看到了整数溢出。

因此问题是：是否可以在不立方坐标的情况下找到多边形的质心？

标签： algorithmintegercomputational-geometry

Answer 1

这个问题可以通过确定坐标可以取多少个不同的值来回答。对于该区域，很明显所有 R² 值都是可能的（其中 R 是坐标范围）。

我看不出它不是 R³ 的质心（取一个实心正方形并在任何地方删除一个点，这已经为您提供了 R² 不同的质心）。因此，您将需要 R³ 数字来区分可能的结果。

但是为什么你需要精确的坐标呢？

如果您准备使用 128 位算术，则可以支持最多 42 位的范围，这比 12 位要好。