2

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

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

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

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

Язык: Java/Kotlin

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

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

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

Ваш ответ

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

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