Как убрать коллинеарные точки из списка точек?

Question

Учитывая список точек (A1, A2, A3, ...., AN), каждая точка Ai имеет Ai_x, Ai_y, и Ai_z указывает координаты x, y, z соответственно.

Предположим, чтос учетом трех точек AONE, ATWO, ATHREE, существует функция с именем checkColinear, т.е. checkColinear (AONE, ATWO, ATHREE) возвращает TRUE, если точки AONE, ATWO и ATHREE коллинеарны.

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

Спасибо

Answer 1

Наивным способом является проверка каждого набора из 3-х точек, то есть O (N ^ 3). Я полагаю, вы хотите что-то быстрее.

Вы можете сделать немного лучше (O (N ^ 2 * log N) для невырожденных случаев), создав массив уклонов. Обведите каждую пару точек и сохраните наклон в массиве (вместе с индексами массива 2 точек). Сортировать массив по наклону. Затем просмотрите массив - например, Вы можете найти 5 записей в строке с наклоном 2.5 из пар (2,3), (6,7), (9,4), (3,5), (2,5). Точки № 2, № 3 и № 5 здесь коллинеарны.

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

Я также только что нашел эту ссылку с тем же базовым подходом: http://lists.canonical.org/pipermail/kragen-hacks/2008-March/000482.html