Я пытаюсь уменьшить набор n вершин до m количества прямоугольников (точки не находятся на сетке и определяются пользователем).
Самый простой случай - проверить 4 узла и подтвердить, что существует менее 3 уникальных расстояний, что приведет к получению 1 формы прямоугольника. Однако я надеялся уменьшить количество n вершин в несколько прямоугольников, учитывая, что каждое подмножество вершин формирует прямоугольник. Я рад, что прямоугольники будут диагональными, и не возражаю, если это всего лишь приближение к прямоугольнику (например, он нависает над вершиной, образуя прямоугольник). Я также рад, что формы перекрываются.
Текущий ввод определяется пользователем:
- Пользователь нажимает, чтобы разместить «узел», узлы могут быть соединены для создания «ребер» (макс. 2 узла на край, но несколько ребер на узел).
- Каждое «ребро» узла имеет начальную и конечную позицию (два узла, которые его создают)
- Пользовательские щелчки могут быть без сетки или на сетке (размер сетки определяется пользователем, поэтому, к сожалению, нет алгоритмов заливки)
Я определил разумное решение sh:
- Выбрать случайную кромку в наборе узлов
- Использовать алгоритм Звездочка на всех кромках, при этом выбранная кромка начальное и конечное положение, но не позволяйте алгоритму пересекать этот край в первом экземпляре
- Если есть обратный путь к краю, мы нашли замкнутую форму
- Вытягивание строки результирующий путь (т.е. упрощение пути, удаление узлов / ребер, находящихся на одной линии, чтобы уменьшить количество путей)
- Выполнять проверки для прямоугольника, например, не более 3 уникальных расстояний
- Повторить процесс для любых узлов, которые не были включены в этот путь
К сожалению, это будет довольно вычислительно дорого для моего приложения, и я надеялся сделать это во время выполнения. Есть ли у кого-нибудь предложения по улучшению вышеуказанного метода или знает ли другой метод, который был бы лучше для этого?