math: масштабировать систему координат, чтобы определенные точки получали целочисленные координаты

Question

это скорее математическая проблема.nonethelesse Я ищу алгоритм в псевдокоде для его решения.

дано является одномерной системой координат с количеством точек.координаты точек могут быть в плавающей точке.

теперь я ищу фактор, который масштабирует эту систему координат, чтобы все точки были на фиксированном числе (то есть целочисленная координата)

если я не ошибаюсь, решение этой проблемы должно быть найдено, если число точек не бесконечно.

, если я ошибаюсь и нет аналитического решения дляЭта проблема, меня интересует алгоритм, который приближает решение как можно ближе.(то есть координаты будут выглядеть как 15.0001)

, если вы заинтересованы в конкретной проблеме: я хотел бы преодолеть хорошо известную проблему захвата пикселей в Adobe Flash, которая сокращает половину пикселей на границе растровых изображений, еслився сцена масштабируется.Я хотел бы найти идеальный коэффициент масштабирования для сцены, при котором мои растровые изображения помещаются в целые (экранные) пиксельные координаты.

, поскольку я размещаю две растровые изображения на сцене, количество точек будет4 в каждом направлении (x, y).

спасибо!

Answer 1

Как и предполагалось, вы должны преобразовать числа с плавающей запятой в рациональные. Зафиксируйте допуск эпсилон, и для каждой координаты найдите наилучшее рациональное приближение в эпсилоне.

Алгоритм и определения изложены там в этом разделе .

После преобразования всех координат в рациональные числа масштабирование дается наименьшим общим кратным из знаменателей.

Обратите внимание, что это последнее число может стать довольно большим, поэтому вы можете поэкспериментировать с эпсилоном, чтобы контролировать знаменатели.

Answer 2

Это действительно проблема статистического вывода в сочетании с уменьшением шума. Это метод, который я собираюсь опробовать в ближайшее время. Я предполагаю, что вы пытаетесь получить равномерно расположенную двумерную сетку, но аналогичный метод может работать с равномерно распределенной сеткой 3 или более измерений.

Сначала перечислите все различия и обратите внимание, что (dx, dy) и (-dx, -dy) обозначают одно и то же смещение, поэтому существует отношение эквивалентности. Сгруппируйте те различия, которые находятся в пределах заранее заданного порога (эпсилон) друг друга. Эпсилон должен быть достаточно большим, чтобы фиксировать ошибки измерения из-за случайного шума или отсутствия разрешения изображения, но достаточно маленьким, чтобы случайно не объединить кластеры.

Сортировка кластеров по их среднему размеру (dr = root (dx ^ 2 + dy ^ 2)).

Если исходная сетка действительно регулярно располагалась и генерировалась двумя независимыми базисными векторами, то два наименьших линейно независимых кластера будут указывать на это. Наименьший кластер - это центр с центром в (0, 0). Следующий наименьший кластер (dx0, dy0) имеет первый базисный вектор до знака +/- (-dx0, -dy0) обозначает то же смещение, напомним.

Следующие наименьшие кластеры могут линейно зависеть от этого (вплоть до порогового значения эпсилон) в силу кратности (dx0, dy0). Найдите наименьший кластер, который НЕ кратен (dx0, dy0). Назовите это (dx1, dy1).

Теперь у вас достаточно пометить оригинальные векторы. Сгруппируйте вектор, увеличив лексикографический порядок (x, y)> (x ', y'), если x> x 'или x = x' и y> y '. Возьмите наименьшее (x0, y0) и присвойте ему целое число (0, 0). Возьмите все остальные (x, y) и найдите разложение (x, y) = (x0, y0) + M0 (x, y) (dx0, dy0) + M1 (x, y) (dx1, dy1) и присвойте это целые числа (m0 (x, y), m1 (x, y)) = (round (M0), round (M1)).

Теперь подгоняем целые числа наименьших квадратов к векторам уравнений (x, y) = (ux, uy) m0 (x, y) (u0x, u0y) + m1 (x, y) (u1x , u1y) найти (ux, uy), (u0x, u0y) и (u1x, u1y). Это идентифицирует сетку.

Проверьте это совпадение, чтобы определить, все ли точки находятся в пределах заданного порога этого соответствия (возможно, для этой цели используется один и тот же порог эпсилон).

1-D версия этой же процедуры должна также работать в одном измерении на спектрографе, чтобы идентифицировать основную частоту в голосовом отпечатке. Только в этом случае предполагаемое значение для ux (которое заменяет (ux, uy)) равно 0, и нужно только найти соответствие однородному уравнению x = m0 (x) u0x.

Answer 3

Если вы говорите о числах с плавающей запятой одинарной точности , то число можно выразить так в соответствии с википедией:

Из этой формулы вы можете сделать вывод, что вы всегда получаете целое число, если умножить на 2 ^{127 + 23} . (На самом деле, когда e равно 0, вы должны использовать другую формулу для специального диапазона «субнормальных» чисел, поэтому достаточно 2 ^{126 + 23} . Подробнее см. В статье в Википедии) 1014 *

Чтобы сделать это в коде, вам, вероятно, потребуется выполнить переворот в битах , чтобы извлечь факторы в приведенной выше формуле из битов в значении с плавающей запятой. И тогда вам понадобится какая-то поддержка для чисел неограниченного размера, чтобы выразить целочисленный результат масштабирования (например, BigInteger в .NET). Обычные примитивные типы в большинстве языков / платформ обычно ограничены гораздо меньшими размерами.

Answer 4

Число с плавающей запятой - это целое число, умноженное на степень два (степень может быть отрицательной).

Итак, найдите наибольшую необходимую степень двух среди ваших входов, и это даст вам масштабный коэффициент, который будет работать. Степень двойки не только в 1 раз превышает показатель степени с плавающей точкой, она несколько больше, чем это (в зависимости от того, где в значащем и младшем значащем 1 бите находится).

Это также оптимально, потому что, если x умноженное на 2 является нечетным целым числом, тогда x в его представлении с плавающей запятой уже было в простейшей рациональной форме, нет меньшего целого числа, которое можно умножить на x, чтобы получить целое число.

Очевидно, что если у вас есть смесь больших и малых значений среди ваших входных данных, то результирующие целые числа будут иметь тенденцию быть больше, чем 64 бит. Так что есть аналитическое решение, но, возможно, не очень хорошее, учитывая то, что вы хотите сделать с результатами.

Обратите внимание, что этот подход рассматривает float как точное представление, которым они не являются. Вы можете получить более разумные результаты, представив каждое число с плавающей точкой как рациональное число с меньшим знаменателем (в пределах некоторого определенного допуска), а затем выбрав наименьшее общее кратное из всех знаменателей.

Однако проблема заключается в процессе аппроксимации - если входное значение с плавающей запятой равно 0,334 [*], то я не могу в целом быть уверенным, действительно ли человек, который дал его мне, имел в виду 0,334, или это 1/3 с некоторыми неточность. Поэтому я не знаю, использовать ли масштабный коэффициент 3 и сказать, что масштабированный результат равен 1, или использовать масштабный коэффициент 500 и сказать, что масштабированный результат равен 167. И это только с 1 входом, не говоря уже о куче из них .

Имея 4 входа и допустимый конечный допуск 0,0001, вы, возможно, могли бы найти 10 ближайших рациональных чисел к каждому входу с определенным максимальным знаменателем, а затем попробовать 10 ^ 4 различных возможностей и посмотреть, дает ли результирующий масштабный коэффициент какие-либо значения, которые слишком далеко от целого числа. Грубая сила кажется мерзкой, но вы, по крайней мере, сможете немного ограничить поиск по ходу дела. Также «максимальный знаменатель» может быть выражен в терминах простых чисел, присутствующих в факторизации, а не просто числа, так как если вы сможете найти среди них много общих факторов, то они будут иметь меньший lcm и, следовательно, меньшее отклонение от целых чисел. после масштабирования.

[*] Не то, чтобы 0.334 было точным значением с плавающей запятой, но такого рода вещи. Десятичные примеры проще.

Answer 5

Моя собственная склонность, если бы я был в вашей ситуации, заключалась бы в использовании рациональных чисел, а не с плавающей точкой.И алгоритмы, которые вы ищете, находят наименьший общий знаменатель.