Преобразование для избавления от коллинеарных точек

Я пишу программу для решения задачи по геометрии.

Мой алгоритм не очень хорошо обрабатывает коллинеарную точку.

Есть ли какое-либо преобразование, которое я могу применить к точкам, чтобы избавиться от коллинеарности?


transformation transform math geometry
person user182945    schedule 30.05.2010    source источник
comment
Это полностью зависит от задачи... Один из способов убрать коллинеарность — просто добавить к каждой точке некоторый шум, т. е. (x, y, z) ↦ (x + 0,01*(random() — 0,5), y + 0,01* (random() - 0,5), z + 0,01(random() - 0,5)) если random() возвращает случайное действительное число в [0, 1[.   -  person Andreas Rejbrand    schedule 30.05.2010
comment
Вы хотите преобразование, которое удаляет (почти) коллинеарные точки, или вы хотите, чтобы все точки были преобразованы таким образом, чтобы они были менее коллинеарными?   -  person Pieter    schedule 30.05.2010
comment
Я хочу сохранить все точки, но я хочу, чтобы они были менее коллинеарными   -  person user182945    schedule 30.05.2010

Ответы (2)


arrow_upward
5
arrow_downward

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

Один из способов устранить коллинеарность — просто добавить шум в каждую точку, т. е. (x, y, z) ↦ (x + 0,01*(random() — 0,5), y + 0,01*(random() — 0,5), z + 0,01(random() - 0,5)) если random() возвращает случайное действительное число в [0, 1[.

person Andreas Rejbrand    schedule 30.05.2010
comment
Вы всегда можете работать в 4-х измерениях и добавлять шум по 4-й оси. Для некоторых алгоритмов это решит проблемы с небольшими заметными изменениями после обратного проецирования в 3 измерения. Но без понятия, в чем заключается исходная проблема, кто знает, уместно ли это. - person sigfpe; 31.05.2010

arrow_upward
0
arrow_downward

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

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

Условие колинеарности:

       x1  y1  1
  det  x2  y2  1  = 0
       x3  y3  1
person Dr. belisarius    schedule 31.05.2010
comment
Вычисление определителей происходит медленно. Лучший тест состоит в том, чтобы сформировать два вектора переноса v1 := (x3, y3) - (x2, y2) и v2 := (x2, y2) - (x1, y1) и проверить, параллельны ли они, т. е. если v1 = к v2. v1 и v2 параллельны тогда и только тогда, когда (v1, v2) = |v1| |v2|. - person Andreas Rejbrand; 01.06.2010
comment
@ Андреас Детерминанты в общем случае работают медленно. Здесь нужно всего 5 сумм и три умножения. Ваше предложение предполагает (могу ошибаться) 4 суммы одно деление и одно умножение... не ооочень разные! :) - person Dr. belisarius; 01.06.2010
comment
@belisarius: Нет, я понял, что через пять минут комментарий доступен только для чтения. Но я думаю, что мой подход немного проще реализовать, по крайней мере, если ОП не так хорошо знаком с детерминантами. - person Andreas Rejbrand; 01.06.2010
comment
Еще один вариант заключается в том, что равенство выполняется в неравенстве треугольника, применяемом к двум векторам переноса, тогда и только тогда, когда три точки лежат на одной прямой. - person Andreas Rejbrand; 01.06.2010
comment
Кажется, что четыре суммы, два умножения и сравнение являются наиболее экономичными (y2-y3) (x1-x3) = (y1-y3) (x2-x3) Геометрическая интерпретация такова, что наклоны двух прямых из указать на то, что остальные равны - person Dr. belisarius; 02.06.2010