Есть ли способ лучше, чем сравнение грубой силы, чтобы получить диагонали максимальной и минимальной длины многоугольника? Чтобы быть более конкретным, я хотел бы найти соотношение, чтобы я мог сортировать полигоны по их «художеству».
Полигоны не слишком большие (обычно 4-8 граней на полигон), но их много. Я подумал, что просто уточню у SO, есть ли лучший способ сделать это.
заранее спасибо
Многоугольники не слишком большие (обычно 4–8 граней на полигон), но их много.
Я не знаю, есть ли более быстрое решение, чем O(n^2), но для n <= 8 это не имеет значения. Если n = 8, вам просто нужно проверить 20 диагоналей (8 * 5 / 2). Сам по себе множитель не такой уж большой, и любой сложный алгоритм, скорее всего, потребует больших вычислительных затрат (структуры данных, сложные циклы и проверки).
Одна вещь, которую вы можете сделать, чтобы ускорить это, это отбросить квадратный корень в формуле расстояния между двумя точками. Сначала найдите минимум/максимум (xi-xj)*(xi-xj) + (yi-yj)*(yi-yj), затем примените квадратный корень. Это довольно дорогая операция, и выполнение ее 2 раза вместо 20 может иметь значение.
