Объединение многоугольников в один

07 сентября 2021, 22:00

Есть два многоугольника заданных массивами с координатами. Нужно как-то объединить их в один многоугольник и получить на выходе новый массив с координатами его точек. Многоугольники выпуклые и всегда правильной формы. Без самопересечений. При этом между собой всегда соприкасаются. Никогда один в другом не будет находиться.

Поиски в Гугле ничего толкового не дали. Большая часть алгоритмов или не работает, или не подходит.

Пока смог реализовать нахождение точек пересечения многоугольников, но что делать дальше не совсем понимаю. Точнее понимаю, что нужно пройтись по всем вершинам и откинуть не нужные точки, а потом все соединить, но не до конца понимаю как.

Может подскажете или дадите ссылку на библиотеку подходящую?

Язык: Java/Kotlin

Можно пример и на C#, перепишу под Java или Kotlin сам, но желательно сразу пример или библиотека под Java/Kotlin.

Answer 1

Объединение многоугольников оказалась довольно сложной задачей. Однако, свою задачу я смог решить с помощью этой библиотеки: JTS Topology Suite

Довольно удобная, простая и относительно многофункциональная библиотека. Плюс документация есть, причем нормальная на фоне других библиотек, которые я находил.

fun main() {
    /*
     * (0, 1)   (1, 1)
     *   +--------+
     *   |        |
     *   |        |
     *   |        |
     *   +--------+
     * (0, 0)   (1, 0)
     * 
     * Последняя точка должна быть равной первой, чтоб замкнуть контур
     */
   val shapeACoordinates = arrayOf(
        Coordinate(0, 0), Coordinate(0, 1), Coordinate(1, 1), Coordinate(1, 0), Coordinate(0, 0)
   )
   /*   (0.5, 1.5)  (1.5, 1.5)
    *        +---------+
    * (0, 1) |   (1, 1)|
    *   +----|-----+   |
    *   |    |     |   |
    *   |    +-----|---+
    *   |(0.5, 0.5)| (1.5, 0.5)
    *   +----------+
    * (0, 0)   (1, 0)
    * 
    *
    */
   val shapeBCoordinates = arrayOf(
        Coordinate(0.5, 0.5), Coordinate(0.5, 1.5), Coordinate(1.5, 1.5), Coordinate(1.5, 0.5), Coordinate(0.5, 0.5)
   )
   val factory = GeometryFactory()
   val shapeA = factory.createPolygon(shapeACoordinates)
   val shapeB = factory.createPolygon(shapeBCoordinates)
   /*
    * shapeC = shapeA + shapeB
    * 
    *        +---------+
    *        |         |
    *   +----+         |
    *   |              |
    *   |          +---+
    *   |          |
    *   +----------+
    */
   val shapeC = shapeA.union(shapeB)
   //Получаем массив точек
   val shapeCCoordinates = shapeC.coordinates
}

Спасибо Stranger in the Q!

Answer 2

Задачу можно легко свести к нахождению минимальной выпуклой оболочки. Если найти пересечение многоугольников(что вы научились делать), останется лишь найти минимальную выпуклую оболочку среди всех точек многоугольников и их пересечений. Эту задачу можно решать множеством алгоритмов(Грехем, Джарвис и т.д). Про них легко можно прочитать в интернете.