Найти наименьший неправильный многоугольник из комбинации вершин (Performance Critical)

Question

Мне нужно найти неправильный многоугольник с наименьшей площадью поверхности из нескольких вершин на плоскости 2D.

Нет, это не домашняя работа. Хотя я бы хотел вернуться в школу прямо сейчас.

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

Получение площади поверхности неправильного многоугольника достаточно просто . В основном меня беспокоит производительность эффективного сканирования всех возможных комбинаций .

См. Изображение ниже для примера. Все три типа используются для создания многоугольников, однако один кружок имеет наименьшую площадь поверхности и является моей целью.

Этот сценарий упрощен по сравнению с тем, что я пытаюсь прототипировать. Полигоны будут построены из десятков, если не сотен вершин, и сетка будет намного больше. Также этот процесс будет запущен 24/7.

Я думал, что, возможно, мне следует организовать вершины по типу и разбить их на отдельные массивы. Затем просто итерируйте массивы по уровням, чтобы вычислить площадь поверхности всех комбинаций. Однако такой подход кажется расточительным.

Answer 1

Вот версия, основанная на ветвях и связях, с некоторыми расцветами.

1) Разбейте сетку на дерево квадрантов, с аннотациями в узлах, необходимыми для остальных.

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

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

3a) Угадайте вершину наименее общего типа.

3b) Используя относительное расположение точек в четырехугольном дереве, чтобы упорядочить свои догадки, угадать вершину следующего наименее распространенного типа, чтобы угадать их в порядке возрастания расстояния от исходной точки ...

3z) у вас есть полный набор вершин.

На каждом шаге 3? у вас есть частичный набор вершин, который, как я полагаю, дает вам нижнюю границу для области любого полного решения, включая эти вершины (это область внутри выпуклой оболочки вершин?). Вы можете отказаться от любых частичных решений, которые уже по крайней мере столь же велики, как самые крупные решения на данный момент. Если вы можете согласиться с неправильным ответом на X%, вы можете отказаться от любых частичных решений, которые находятся в пределах X% от самого большого решения на данный момент. Надеемся, что это удалит дерево вариантов, по которым вы перемещаетесь (3), достаточно далеко, чтобы сделать его доступным.

Answer 2

Если мы уже нашли область A, мы можем сузить поиск.

Площадь треугольника равна B*h (базовое значение высоты).

Если вы найдете две точки, то B - это расстояние между ними.

Затем мы можем найти точку, которая находится на расстоянии не более A/B (B*h < A => h < A/B) от этой линии. Это то же самое, что поиск между двумя прямыми, параллельными двум уже имеющимся точкам, которые смещены A/B и -A/B.

Это должно дать сложность O(n^2*k), где k - ширина или высота вашей сетки.

Если вы не извлекаете координаты, вам нужно выполнить поиск O(k^5), который по крайней мере лучше, чем O(k^6), который вы должны были сделать ранее.

Еще немного анализа: если p - вероятность того, что ячейка содержит вершину, то сложность: O(k^2p(k^2p(kp))) = O(k^5p^3). Если p=n/k^2, где n - количество узлов, то мы получим O(n^3/k).

Answer 3

Вот как найти наименьший треугольник за время O (n ² log n).Возможно, это будет вам полезно.

Идея высокого уровня - использовать вращающуюся линию развертки.Мы всегда поддерживаем порядок синих точек вдоль оси, перпендикулярной линии развертки, в бинарном дереве поиска.Когда линия развертки параллельна линии, проходящей через красно-зеленую пару, мы используем BST, чтобы найти синюю точку, ближайшую к красно-зеленой линии.

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

Answer 4

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