Как создать замкнутые области (выпуклые многоугольники) из множества отрезков?

Question

Следующая проблема в 2D, поэтому при предложении ответов могут быть сделаны некоторые упрощения.

Мне нужно создать замкнутые области (определяемые либо отрезками линий, либо просто набором точек - выпуклым многоугольником) из набора точек / отрезков.

В основном я использовал Вороного для создания "дорог". Затем я изменил некоторые данные. Теперь мне нужен способ перебрать эти данные (которые все еще являются отрезками, но больше не соответствуют Вороному) и генерировать «окрестности», граничащие с «дорогами».

Я посмотрел на некоторые графовые диаграммы и теории кратчайших путей, но не смог понять это.

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

Я пытался реализовать это, но это ни к чему не привело, так как я не мог найти способ написать код на C ++, который мог бы это сделать. Проблема заключалась в выборе линии против часовой стрелки из доступных линий из определенной точки. Вся математика, основанная на углах, я давала неправильные ответы, потому что способ sin / cos реализован в c ++.

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

РЕДАКТИРОВАТЬ: Добавлено изображение, чтобы проиллюстрировать, что я хочу сделать.

Проверьте изображение здесь - (нужно 10 репутаций, прежде чем я смогу опубликовать его здесь: P)

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

Спасибо за помощь!

Answer 1

Основано на ваших разъяснениях:

Возможно, вы можете попробовать это:

Возможно, у вас уже есть список «соседних» точек для любой заданной фиолетовой синей точки из-за Вороного. Теперь, имея фиолетовую точку P с соседом Q, вы можете рассмотреть дорогу, которая пересекает отрезок линии PQ. Все такие дороги (т. Е. Различаются Q среди соседей P), вероятно, будут образовывать замкнутую область вокруг P.

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

Это не может быть оптимальным, но, вероятно, работает, хотя я не пытался доказать это.

---

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

Если вы хотите множество непересекающихся «областей», вы можете попробовать найти разделительную линию и запустить выпуклый корпус отдельно.

Answer 2

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

Вместо этого у вас должно быть два флага для каждого сегмента, для того, построили ли вы многоугольник для сегмента «влево» и «вправо». Если у вас есть ограниченная область, у сегментов границы должен быть установлен флаг внешней стороны, так как вы не хотите использовать эту сторону в многоугольнике. Затем найдите сегменты с неустановленным флагом и используйте ответ Нильса, чтобы обойти полигон. Некоторые сегменты будут «обратными»; если вы идете по часовой стрелке, вы хотите установить флаг «влево» на «передних» сегментах и ​​флаг «вправо» на «обратных», и наоборот. (Вы можете построить все полигоны в одном порядке, просто неважно, какой вы выберете.) Обратите внимание, что первый сегмент можно интерпретировать как любой из них, в зависимости от того, какой из его флагов вам нужно установить. Когда все сегменты помечены в обоих направлениях, все готово.

Если вы разделяете плоскость, а не ограниченную область, некоторые сегменты будут лучами; вам также понадобится специальный код для соединения соседних лучей при сортировке по наклону в фальшивые «полигоны».

Псевдокод для ограниченного случая:

foreach seg in boundary segments {
    if left of seg is outside region {
         seg.leftDone = true
    } else {
         seg.rightDone = true
    }
}
while any seg.leftDone or seg.rightDone is false {
    seg = pick a segment with either flag unset
    start = seg
    polygon = new Polygon()
    reversed = not start.rightDone
    do {
        if reversed {
            seg.rightDone = true
            endpoint = seg.start
            polygon.addSegment(seg.reverse())
        } else {
            seg.leftDone = true
            endpoint = seg.end
            polygon.addSegment(seg)
        }

        next = findNextClockwiseSeg(seg, endpoint); // Nils's answer works

        seg = next
        reversed = (seg.end == endpoint)
    } while start != seg;
    result.addPolygon(polygon)
}

Answer 3

Ваша идея, чтобы следовать отрезкам линии по кратчайшему пути (например, следовать по часовой стрелке, если у вас есть несколько вариантов), это хорошо.

И вы можете найти эту строку без каких-либо вызовов sin / cos.

Идея такова:

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

Эти три точки образуют треугольник.Теперь посмотрим, как три точки ориентированы.Если вы следуете точкам от A до B до C, направление будет либо по часовой стрелке, либо против часовой стрелки.Очевидно, что если порядок по часовой стрелке, линия, которая идет от A до C, будет наиболее часовой по часовой стрелке.В противном случае это линия, которая идет от А до Б.

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

Теперь о математике: как узнать порядок наматывания трех точек, не называя sin / cos или даже хуже: atan:

Вы можете сделать этос перекрестным произведением.Сначала создайте два вектора, которые указывают направление от А к В и от А к С:

   u.x = B.x - A.x
   u.y = B.y - A.y

   v.x = C.x - A.x
   v.y = C.y - A.y

Теперь мы можем вычислить площадь со знаком параллелограмма, порожденного этими двумя векторами:

   signed_area = (u.x * v.y) - (u.y * v.x);

Обмотка является признаком местности.например,

  if (signed_area > 0)
  { 
     // order is clockwise. Pick Line B
  }
  else if (signed_area < 0)
  { 
     // order is counter-clockwise. Pick Line A
  }
  else 
  {
    // the lines are colinear.
  }

Примечание: я не привязал код, и решение по знаку могло быть совсем другим.Это деталь математики, которая мне никогда не придет в голову.Я всегда должен пробовать это с известными данными.