查找哪个相同大小的正方形包含给定的坐标

Question

问题

我正在开发一个图像处理库，它可以分割图像并逐部分分析它。

我有一个给定高度

H

和宽度

W

（以像素为单位）的图像，并且想将其除以

n

因子（

n

水平部分和

n

垂直部分，所以总共

n**2

部分）。例如，带有

n = 6

的 320x240 图像看起来像 this。

所以，简而言之，我想要一个函数

f(x, y)

可以告诉我给定的坐标或像素属于这些正方形中的哪个。例如，

f(0, 0) == 0

、

f(160, 120) == 21

、

f(319, 239) == 35

；或者，包含正方形的坐标/偏移量：

f(0, 0) == {0, 0}

、

f(160, 120) == {3, 3}

、

f(319, 239) == {5, 5}

我目前的理解和疑问

对我来说，显而易见的解决方案是获取单个正方形的宽度和高度（图中的

w

和

h

）并进行两个简单的除法以获得坐标。

square.h := square.H / n
square.w := square.W / n

func f(x, y) {
    xCoord := floor(x / square.w)
    yCoord := floor(y / square.h)
    return {xCoord, yCoord}
}

我认为这在数学上对于这个问题来说是正确的（告诉我是否不正确），但我不确定这将如何与不同的具体编程类型相互作用。例如，对于

f(319, 239)

，如果我将

square.h

保存为整数，没问题，

xCoord == 5

。但是

xCoord

会发生什么呢？如果

square.w

是整数，则

square.h == 53

和

floor(319 / square.h) ==  6

，这是溢出。如果一切都是浮点，那么

square.h == 53.333333333333336

和

floor(319 / square.h) == 5

如我所愿，但现在我担心在一些我没有想到的极端情况下出现浮点错误。这不是我的专业领域，所以我不知道这种担心是否合理。我也可以拿出大枪并使用十进制或有理数类型，但这是一个我预计会大量使用的图像库（这是一个业余爱好项目，所以没有硬性要求，但最糟糕的是它可能需要批处理数百张图像），我希望使其尽可能高效合理，并尽可能坚持基本数据类型。

我也可以将所有矩形存储为一个结构，并线性检查给定的坐标是否在其中的任何一个中，但这对于这个问题来说似乎效率低下且不必要地粗暴。我发现的类似问题建议使用 R 树，但相反，这对于这个版本的问题来说似乎有点过分了。

基本上，我问的是，考虑到其目的，是否有一种非显而易见的方法可以解决这个问题，同时保持代码的效率。如果有一个标准或“良好实践”，那将是理想的。另外，正如我所说，我既不是图像处理软件也不是浮点运算方面的专家。我是否对浮点错误的可能性感到偏执？对于这个应用程序来说，使用类似 bignum 的数据类型成本是否太大？

如果相关的话，这是在 Go 中，但如果可能的话，我正在寻找不可知的答案。

Answer 1

你想要整数。

您的选择：

• 使用整数除法，是哪几层楼
• 使用浮点运算并以舍入结束

这里有一些 Python 来演示算术。

>>> 100/7
14.285714285714286

>>> np.arange(8)
array([0, 1, 2, 3, 4, 5, 6, 7])

>>> np.arange(8) * 100 // 7; np.diff(_)
array([  0,  14,  28,  42,  57,  71,  85, 100])
array([14, 14, 14, 15, 14, 14, 15])

>>> (np.arange(8) * 100 / 7).round().astype(int); np.diff(_)
array([  0,  14,  29,  43,  57,  71,  86, 100])
array([14, 15, 14, 14, 14, 15, 14])