Алгоритм - поиск треугольника с максимальным периметром - PullRequest
Новая
       38

Алгоритм - поиск треугольника с максимальным периметром

0 голосов
/ 03 сентября 2018

Мне дан набор из N точек в 2D плоскости, представленных в виде (x, y) координатных пар. Что такое быстрый алгоритм выбора трех точек, чтобы треугольник, образованный этими точками, имел максимальный периметр?

Ответы [ 2 ]

0 голосов
/ 04 сентября 2018

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

enter image description here

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

0 голосов
/ 04 сентября 2018

Это превентивный характер

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

Проверить, можно ли сделать треугольник? если нет, проверьте другую наивысшую точку на другой оси

...