Определите, какие точки максимизируют площадь многоугольника, если выбраны как вершины.

Question

У меня есть многоугольник, вершины которого являются центрами других 4-х многоугольников. Для этих четырех многоугольников у меня также есть координаты их вершин. Я хотел бы определить для каждого «углового многоугольника» вершину, которая, если бы она выбрана как вершина большего многоугольника, максимизирует ее площадь. Многоугольник представляет собой прямоугольник, к которому применено преобразование перспективы, поэтому я думал, что это трапеция.

Я попытался расчетом шероховатую центра пути суммирования (х, у) с углами и погружений на 4. Затем я выбрал каждую вершину на основе тот, которая имела достаточное расстояние от этой центральной точки среди его сверстников. (что-то вроде distance = (Xc - X)^2 + (Yc - Y)^2, я избегал квадратного укоренения результата для достижения целей).

Это, к сожалению, не дает ожидаемых результатов. Обычно только одна вершина заменяется внешней самой вершиной «углового многоугольника», а остальные заменяются одной из двух других «угловых многоугольников», исключая ближайшую вершину.

Что может быть способом создания лучшего алгоритма?

Answer 1

Первый подход - это просто грубой силой: сравнить площади 4^4 = 256 полигонов, полученных комбинациями.

Чуть лучше, я думаю, что вершины должны принадлежать выпуклой оболочке точечного множества (необходимо подтвердить). Затем отбросьте внутренние точки и скопируйте остаточные. Поскольку между одной и тремя вершинами угловых четырехугольников находятся на выпуклой оболочке, в худшем есть 3^4 = 81 комбинации (и в лучшем случае - один, в данном примере - четыре, а 2^4 = 16).

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

Answer 2

Метод, который я опубликовал, действительно работает, поскольку @MBo предположил, что ошибки реализации. Чтобы указать для будущих читателей, этот алгоритм, вероятно, работает только потому, что многоугольник выпуклый и/или трапециевидный, хотя это остается чистой спекуляцией, основанной на том, что мой алгоритм был создан эвристически.