2

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

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

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

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

Язык: Java/Kotlin

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

введите сюда описание изображения

7
  • В общем виде это довольно сложная задача. Вы нарисовали простой пример, но в такой постановке, как вы описали, многоугольники могут иметь сколь угодно сложную форму, в том числе содержать самопересечения. Но даже если это простые многоугольники (без самопересечений), они могут быть невыпуклыми, в результате чего два многоугольника могут пересекаться очень сложным образом, порождая пустоты. Ещё может быть один находится целиком в другом. Я в своё время решал именно такую задачу: абсолютно произвольные многоугольники были с самопересечениями. Была жесть и повторять её здесь.. ну как-то не очень.
    – Zealint
    Commented 12 окт. 2019 в 14:53
  • Немного дополню: По сути моя задача сводится к тому, что нужно объединять как на картинке. Самопересечений не будет. Плюс никаких внутренних контуров. Просто произвольного диаметра окружности, которые так соприкасаются нужно объединять.
    – Tolikol
    Commented 12 окт. 2019 в 15:01
  • если нужно просто решение - можно взять JTS (locationtech.github.io/jts/javadoc/org/locationtech/jts/…) Commented 12 окт. 2019 в 15:16
  • Чтобы откинуть все ненужные точки, нужно бежать по всем граням и поворачивать всегда только направо или налево, пока не вернешься в начальную точку. Все точки, что не были пройдены - находятся внутри контура Commented 12 окт. 2019 в 15:44
  • У вас в примере нарисованы выпуклые (более того, правильные) многоугольники. В тексте вопроса ни слова ни о выпуклости, ни о правильности не сказано. Почему приведен такой странный непоказательный пример? Может выпуклость гарантирована условием задачи? Или нет? Это сильно влияет на сложность решения. Commented 12 окт. 2019 в 17:55

1 ответ 1

4

Объединение многоугольников оказалась довольно сложной задачей. Однако, свою задачу я смог решить с помощью этой библиотеки: 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!

1
  • 1
    Рад помочь, добавьте пример кода в ответ, чтобы он был больше похож на ответ... в целом JTS очень хорошая библиотека по работе с геометрией, кстати у нее есть и js вариант bjornharrtell.github.io/jsts Commented 12 окт. 2019 в 17:19

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.