Алгоритм для максимальной и минимальной диагонали выпуклого многоугольника?

Question

Есть ли способ лучше, чем сравнение методом грубой силы, получить максимальную и минимальную длину диагонали многоугольника? Чтобы быть более конкретным, я хотел бы найти соотношение, чтобы я мог сортировать полигоны по их "худости".

Полигоны не слишком велики (обычно 4-8 граней на полигон), но их много. Я подумал, что просто уточню у SO, есть ли лучший способ сделать это.

Заранее спасибо

Answer 1

Многоугольники не слишком большие (обычно 4-8 граней на многоугольник), но их много.

Я не знаю, есть ли более быстрое решение, чемO (n ^ 2), но для n <= 8 это не будет иметь значения.Если n = 8, вам просто нужно проверить 20 диагоналей (8 * 5 / 2).Это не такой уж большой множитель, и любой сложный алгоритм, вероятно, будет иметь большие вычислительные затраты (структуры данных, сложные циклы и проверки).

Одна вещь, которую вы можете сделать, чтобы ускорить его, - этовыбросить квадратный корень в формулу расстояния между двумя точками.Сначала найдите мин / макс (xi-xj)*(xi-xj) + (yi-yj)*(yi-yj), затем примените квадратный корень.Это довольно дорогая операция, и выполнение ее 2 раза вместо 20 может иметь значение.