Найдите, какой квадрат одинакового размера содержит данную координату
Проблема
Я работаю над библиотекой обработки изображений, которая делит изображение и анализирует его по частям.
У меня есть изображение заданной высоты H и ширины W (в пикселях), и я хочу разделить его на коэффициент n (части n по горизонтали и части n по вертикали, то есть всего n**2 частей). Например, изображение 320x240 с n = 6 будет выглядеть примерно так: 
.
Короче говоря, мне нужна функция 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}. Координаты всегда начинаются с верхнего левого угла в {0, 0} (обычный способ для библиотек манипулирования изображениями, которые я видел), а x и y всегда являются целыми числами, хотя, конечно, их можно преобразовать впоследствии.
Мое нынешнее понимание и вопросы
Для меня очевидным решением было бы получить ширину и высоту одного внутреннего прямоугольника (w и h на диаграмме) и выполнить два простых деления, чтобы получить координаты.
rectangle.h := rectangle.H / n
rectangle.w := rectangle.W / n
func f(x, y) {
xCoord := floor(x / rectangle.w)
yCoord := floor(y / rectangle.h)
return {xCoord, yCoord}
}
Я думаю, что это математически правильно для задачи (скажите мне, если это не так), но я не уверен, как это будет взаимодействовать с различными конкретными типами программирования. Например, для f(319, 239), если бы я сохранил rectangle.h как целое число, без проблем, xCoord == 5. Но что происходит с xCoord? Если rectangle.h было целым числом, то rectangle.h == 53 и floor(319 / rectangle.h) == 6, что является переполнением. Если все с плавающей запятой, то rectangle.h == 53.333333333333336 и floor(319 / rectangle.h) == 5 как я хочу, но теперь меня беспокоят ошибки с плавающей запятой в каком-то крайнем случае, о котором я не подумал. Это не моя область знаний, поэтому я не знаю, обоснованно ли беспокойство. Я также мог бы просто взять большие пушки и использовать тип Decimal или Rational, но это библиотека изображений, которая, как я ожидаю, будет широко использоваться (это хобби-проект, поэтому никаких жестких требований нет, но в худшем случае может потребоваться пакетная обработка из сотен изображений), я хочу сделать его максимально эффективным и, если возможно, придерживаться базовых типов данных.
Я также мог бы просто сохранить все прямоугольники как структуру и линейно проверять, находятся ли заданные координаты в каком-либо из них, но это кажется неэффективным и излишне грубым для этой задачи. Подобные проблемы, которые я обнаружил, предполагают использование R-деревьев, но, наоборот, для этой версии проблемы это кажется излишним.
По сути, я спрашиваю, есть ли неочевидный способ решить эту проблему, сохраняя при этом эффективность кода, учитывая его назначение. Если бы для этого существовал стандарт или «хорошая практика», это было бы идеально. Кроме того, как я уже сказал, я не являюсь экспертом ни в программном обеспечении для обработки изображений, ни в арифметике с плавающей запятой. Я параноик по поводу возможности ошибок с плавающей запятой? Будет ли использование типа данных типа bignum слишком затратным для этого приложения?
Если это актуально, это в Go, но я ищу независимые ответы, если это вообще возможно.
@EricPostpischil да, координаты всегда начинаются с (0, 0), из верхнего левого угла. И да, координаты всегда задаются целыми числами. Внесу поправки, чтобы уточнить
Ответы 1
У вас есть большой диапазон, скажем N = 100, который вы разбиваете на N = 7 сегменты одинаковой длины, каждый из которых предположительно имеет W/N длину.
У вас есть позиция в этом диапазоне i, и вы хотите знать, в какой сегмент она попадает.
Вы бы посчитали i / (W/N) = i * (N/W), что плохо, или улучшенное выражение.
(i * N) / W
Это улучшено, поскольку деление, являющееся критической операцией, вносящей числовую ошибку, идет последней. Умножение является точным и не вносит ошибок.
Вам следует делать это с помощью целочисленной арифметики, потому что это делается неявно. Теперь у вас есть индекс этого интервала в диапазоне от floor до 0.
Это арифметически верно.
Если вам нужно знать границы этих интервалов, конечно, это тоже можно сделать.
Вы хотите, чтобы сумма этих частей равнялась всей ширине: N-1
Если вы только что вычислили (W / n) * N = W и суммировали или умножили это значение, независимо от арифметики с плавающей запятой или целочисленной арифметикой, есть шанс не достичь цели W/n.
Деление следует выполнять в последнюю очередь, а суммирование/умножение – в первую очередь.
У вас есть выбор между целочисленной арифметикой и арифметикой с плавающей запятой, которая в основном заключается в разнице в округлении.
Вот немного Python для демонстрации арифметики.
>>> W = 100; N = 7
>>> W/N
14.285714285714286
>>> K = np.arange(N+1); K
array([0, 1, 2, 3, 4, 5, 6, 7])
>>> (K * W) // N; np.diff(_)
array([ 0, 14, 28, 42, 57, 71, 85, 100])
array([14, 14, 14, 15, 14, 14, 15])
>>> (K * W / N).round().astype(int); np.diff(_)
array([ 0, 14, 29, 43, 57, 71, 86, 100])
array([14, 15, 14, 14, 14, 15, 14])
Если вам нужно итеративно суммировать вещи, вы можете сделать это:
>>> acc = 0
>>> for k in K:
... print(f"{acc // N:3d} {round(acc / N):3d}")
... acc += W
0 0
14 14
28 29
42 43
57 57
71 71
85 86
100 100
Вы пишете, что высота и ширина указаны в пикселях. Являются ли ваша первоначальная высота, ширина, начальная координата x и начальная координата y целым числом пикселей или числом пикселей с плавающей запятой (или чем-то еще). Изображение всегда начинается с (0, 0)?