Наиболее точное вычисление ординат пересечения линии с плавающей точкой? - PullRequest
4 голосов
/ 22 мая 2009

Я вычисляю ординату y точки на линии в данной абсциссе x. Линия определяется координатами двух конечных точек (x0, y0) (x1, y1). Координаты конечных точек являются числами с плавающей точкой, и для использования в графическом процессоре вычисление должно выполняться с точностью до числа с плавающей точкой.

Математика и, следовательно, наивная реализация тривиальны.

Пусть t = (x - x0) / (x1 - x0), тогда y = (1 - t) * y0 + t * y1 = y0 + t * (y1 - y0).

Проблема в том, что x1 - x0 мало. Результат внесет ошибку отмены. В сочетании с одним из х - х0 в делении я ожидаю значительную ошибку в т.

Вопрос в том, существует ли другой способ определить y с большей точностью?

т.е.. я должен сначала вычислить (x - x0) * (y1 - y0) и разделить на (x1 - x0) после?

Разница y1 - y0 всегда будет большой.

Ответы [ 8 ]

3 голосов
/ 22 мая 2009

В значительной степени ваша основная проблема является фундаментальной. Когда (x1-x0) мало, это означает, что в мантиссе x1 и x0 есть только несколько битов, которые различаются. И, как следствие, существует только ограниченное число операций с плавающей точкой между x0 и x1. Например. если отличаются только младшие 4 бита мантиссы, между ними может быть не более 14 значений.

В вашем лучшем алгоритме термин t представляет эти младшие биты. И, например, если x0 и x1 отличаются на 4 бита, то t может принимать только 16 значений. Расчет этих возможных значений достаточно надежен. Независимо от того, рассчитываете ли вы 3E0 / 14E0 или 3E-12 / 14E-12, результат будет близок к математическому значению 3 / 14.

Ваша формула имеет дополнительное преимущество: y0 <= y <= y1, поскольку 0 <= t <= 1 </p>.

(я предполагаю, что вы достаточно знаете о представлениях с плавающей точкой, и поэтому «(x1-x0) маленький» действительно означает «маленький, по сравнению со значениями самих x1 и x0». Разница 1E-1 маленький, когда x0 = 1E3, но большой, если x0 = 1E-6)

2 голосов
/ 22 мая 2009

Вы можете взглянуть на источники Qt "QLine" (если я правильно помню); они реализовали алгоритм определения пересечений, взятый из одной книги «Graphics Gems» (ссылка должна быть в комментариях к коду, книга была на EDonkey пару лет назад), которая, в свою очередь, имеет некоторые гарантии применимости для заданное разрешение экрана, когда вычисления выполняются с заданной битовой шириной (они используют арифметику с фиксированной точкой, если я не ошибаюсь).

1 голос
/ 22 мая 2009

Я реализовал эталонную программу для сравнения эффекта различных выражений.

Я вычислил y с использованием двойной точности, а затем вычислил y с использованием одинарной точности с разными выражениями

Вот проверенное выражение:

inline double getYDbl( double x, double x0, double y0, double x1, double y1 )
{
    double const t = (x - x0)/(x1 - x0);
    return y0 + t*(y1 - y0);
} 

inline float getYFlt1( float x, float x0, float y0, float x1, float y1 )
{
    double const t = (x - x0)/(x1 - x0);
    return y0 + t*(y1 - y0);
} 

inline float getYFlt2( float x, float x0, float y0, float x1, float y1 )
{
    double const t = (x - x0)*(y1 - y0);
    return y0 + t/(x1 - x0);
} 

inline float getYFlt3( float x, float x0, float y0, float x1, float y1 )
{
    double const t = (y1 - y0)/(x1 - x0);
    return y0 + t*(x - x0);
} 

inline float getYFlt4( float x, float x0, float y0, float x1, float y1 )
{
    double const t = (x1 - x0)/(y1 - y0);
    return y0 + (x - x0)/t;
} 

Я вычислил среднее значение и стандартное отклонение разницы между результатом двойной точности и результатом одинарной точности.

Результатом является то, что в среднем нет 1000 или 10К случайных значений. Я использовал компилятор icc с оптимизацией и без нее, а также g ++.

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

Я не знаю, перекомпилируют ли компиляторы выражение.

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

1 голос
/ 22 мая 2009

Если у вас есть возможность сделать это, вы можете ввести в ваш расчет два случая, в зависимости от abs (x1-x0)

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

// Input is X
xmin = min(x0,x1);
xmax = max(x0,x1);
ymin = min(y0,y1);
ymax = max(y0,y1);
for (int i=0;i<20;i++) // get 20 bits in result
{
  xmid = (xmin+xmax)*0.5;
  ymid = (ymin+ymax)*0.5;
  if ( x < xmid ) { xmax = xmid; ymax = ymid; } // first half
  else { xmin = xmid; ymin = ymid; } // second half
}
// Output is some value in [ymin,ymax]
Y = ymin;
0 голосов
/ 22 мая 2009

Как сказал MSalters, проблема уже в исходных данных.

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

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


Идея:
Если у вас есть более точные данные при генерации линий, вы можете изменить представление с ((x0, y0), (x1, y1)) на (x0, y0, угол, длина). Вы можете сохранить угол или уклон, у склона есть полюс, но угол требует триггерных функций ... безобразно.

Конечно, это не сработает, если вам часто нужна конечная точка, и у вас так много строк, что вы не можете хранить дополнительные данные, я понятия не имею. Но, может быть, есть другое представление, которое хорошо подходит для ваших нужд.

* У 1014 * двойников достаточно разрешения в большинстве ситуаций, но это также удвоило бы рабочий набор.
0 голосов
/ 22 мая 2009

Как насчет вычисления чего-то вроде:

t = sign * power2 ( sqrt (abs(x - x0))/ sqrt (abs(x1 - x0)))

Идея состоит в том, чтобы использовать математическую эквивалентную формулу, в которой низкий (x1-x0) имеет меньший эффект. (не уверен, что написанное мной соответствует этому критерию)

0 голосов
/ 22 мая 2009

Проверьте, является ли расстояние между x0 и x1 маленьким, то есть fabs (x1 - x0) в зависимости от x. У вас бесконечно много значений y, и поэтому вы должны относиться к этому случаю иначе.

0 голосов
/ 22 мая 2009

Если ваши исходные данные уже являются плавающими, то у вас уже есть фундаментальная неточность.

Чтобы объяснить дальше, представьте, если бы вы делали это графически. У вас есть двухмерный лист миллиметровой бумаги, на котором отмечены 2 точки.

Случай 1: Эти точки очень точны и отмечены очень острым карандашом. Легко нарисовать линию, соединяющую их, и легко получить y с заданным x (или наоборот).

Случай 2: Эти точки были отмечены большой жирной фломастером, как маркер бинго. Очевидно, что нарисованная вами линия будет менее точной. Вы проходите через центр пятен? Верхний край? Нижний край? Верх одного, низ другого? Очевидно, есть много разных вариантов. Если две точки расположены близко друг к другу, то разница будет еще больше.

Плавающим элементам присущ определенный уровень неточности, так как они представляют числа, поэтому они больше соответствуют случаю 2, чем случаю 1 (который можно предположить, эквивалентен использованию произвольной точности librray). Ни один алгоритм в мире не может компенсировать это. Неточные данные в, Неточные данные в

...