Алгоритм нахождения ближайших 3 точек, которые при триангуляции охватывают другую точку - PullRequest
2 голосов
/ 20 ноября 2010

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

Уточнение: Под "ближайшим" я подразумеваю минимальную сумму расстояний до точки.


Это в основном из любопытства. Я подумал, что это будет хороший способ оценить «значение» точки, если она неизвестна, но окружающие точки известны. С 3 окружающими точками вы можете экстраполировать значение. Раньше я не слышал о такой проблеме, она не кажется тривиальной, поэтому я подумал, что это может быть забавное упражнение, даже если это не лучший способ что-то оценить.

Ответы [ 6 ]

10 голосов
/ 20 ноября 2010

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

two triangles, neither of which is closer

Синий треугольник ближе на основе лексикографического сравнения расстояний между точками, в то время каккрасный треугольник ближе на основе суммы расстояний между точками.

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

Итак, как насчет этого алгоритма эскиза?

  1. Предположим, что выбранная точка находится в начале координат (упрощает описание алгоритма).
  2. Сортировка точек по расстоянию от начала координат: P (1) - ближайший, P ( n ) - самый дальний.
  3. Начните с i = 3, s = ∞.
  4. Для каждой тройки точек P ( a ), P ( b ), P ( i ) с a <<em> b <<em> i , если треугольник содержит начало координат, пусть s = min ( s , | P ( a) | + | P ( b ) | + | P ( i ) |).
  5. Если с ≤ | P (1) |+ | P (2) |+ | P ( i ) |, останов.
  6. Если i = n , останов.
  7. В противном случае, приращение i и вернитесь к шагу 4.

Очевидно, что в худшем случае это O (n³).

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

alt text

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

Это также O (n³) в худшем случае, норазумный порядок посещения пар (A, B) должен привести к скорейшему выходу во многих проблемных случаях.

4 голосов
/ 20 ноября 2010

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

См. График.
alt text

Красный треугольник имеет периметр около 4 R, в то время как черный имеет 3 кв.м. [3] -> 5,2 R

4 голосов
/ 20 ноября 2010
  1. Как подсказывает @thejh, отсортируйте ваши точки по расстоянию от выбранной точки.
  2. Начиная с первых 3 точек, найдите треугольник, покрывающий выбранную точку.
  3. Если треугольник не найден, расширьте свой диапазон, чтобы включить следующую ближайшую точку, и попробуйте все комбинации.
  4. Как только треугольник найден, у вас не обязательно будет окончательный ответ. Тем не менее, вы теперь ограничены окончательным набором очков для проверки. Самая дальняя точка для проверки будет на расстоянии, равном сумме расстояний первого найденного треугольника. Дальше, чем это, и сумма расстояний гарантированно превысит первый найденный треугольник.
  5. Увеличьте диапазон точек, чтобы включить последнюю точку, расстояние которой <= сумма расстояний первого найденного треугольника. </li>
  6. Теперь проверьте все комбинации, и ответ - треугольник, найденный из этого набора с минимальной суммой расстояний.
1 голос
/ 20 ноября 2010

второй выстрел

подстановка: (основы аналитической геометрии, пропустите, если вы знакомы с этим), нахождение точки противоположной полуплоскости

Пример: Давайте получимдве точки: A = [a, b] = [2,3] и B = [c, d] = [4,1].Найти вектор u = AB = (2-4,3-1) = (-2,2).Этот вектор параллелен линии AB , как и вектор (-1,1).Уравнение для этой линии определяется вектором u и точкой в ​​ AB (т.е. A ):

X = 2 -1*t
Y = 3 +1*t

Где t - любое действительное число.Избавьтесь от t :

t = 2 - X
Y = 3 + t = 3 + (2 - X) = 5 - X
X + Y - 5 = 0

Любая точка, которая вписывается в это уравнение, находится на линии.

Теперь давайте создадим другую точку для определения полуплоскости,то есть C = [1,1], мы получаем:

X + Y - 5 = 1 + 1 - 5 < 0

Любая точка с противоположным знаком неравенства находится в другой полуплоскости, а именно эти точки:

X + Y - 5 > 0

решение: найти минимальный треугольник, который соответствует точке S

  1. Найти ближайшую точку P какмин (sqrt (( Xp - Xs ) ^ 2 + ( Yp - Ys ) ^ 2))
  2. Найти перпендикулярный вектор к SP как u = (-Yp + Ys, Xp-Xs)
  3. Найти две ближайшие точки A , B от противоположной полуплоскости до сигма = pP где p = Su (см. Подкатегорию), напримерпоскольку A находится на другом сайте строки q = SP (см. заключительную часть подстановки)
  4. Теперь у нас есть треугольник ABP, охватывающий S : вычислить сумму расстояний | SP | + | SA | + | SB |
  5. Найдите вторую ближайшую точку к S и продолжайте от 1. Если сумма расстояний меньше, чем в предыдущих шагах, запомните ее.Остановитесь, если | SP | больше, чем наименьшая сумма расстояний или больше нет доступных точек.

Надеюсь, эта диаграмма прояснит ситуацию.alt text

0 голосов
/ 20 ноября 2010

Это мой первый выстрел:

  1. разбить пространство на квадранты с выбранной точкой в ​​[0,0] координатах
  2. найти ближайшую точку из каждого квадранта (так что вы4 очка)
  3. любой треугольник из этих точек должен быть достаточно маленьким (но не обязательно самым маленьким)
0 голосов
/ 20 ноября 2010

Возьмите ближайшие N = 3 балла.Проверьте, подходит ли треугольник.Если нет, увеличьте N на единицу и попробуйте все комбинации.Делайте это, пока что-то не подходит или ничего не подходит.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...