Вопрос по algorithm, svg – Площадь самопересекающегося многоугольника

13

Расчет площади простой нерегулярный полигон тривиально. Однако рассмотрим самопересекающийся многоугольник ABCDEF, показанный слева внизу:

                   

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

Однако если мы рассортируйте точки радиально вокруг центра и рассчитав площадь, мы получим неправильную площадь многоугольника ABEDCF справа вверху.

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

Этот вопрос возник при рассмотрении крайних случаев для моего решенияэтот вопро.

Определение района

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

Ваш Ответ

3   ответа
7

Bentley-Ottmann со следующим псевдокодом отэта страниц

Алгоритм Бентли-Оттмана

Вход для алгоритма Бентли-Оттмана представляет собой набор OMEGA = {Li} отрезков линии Li, а его выходом будет набор LAMBDA = {Ij} точек пересечения. Этот алгоритм упоминается как «алгоритм строчной линии», потому что его работа может быть визуализирована как наличие другой линии, «строчной линии» SL, проходящей по сбору OMEGA и собирающей информацию, когда она проходит по отдельным сегментам Li. Информация, собранная для каждой позиции SL, в основном представляет собой упорядоченный список всех сегментов в OMEGA, которые в настоящее время пересекаются SL. Структура данных, поддерживающая эту информацию, часто также называется «линией развертки». Эта структура классов также обнаруживает и выводит пересечения по мере их обнаружения. Процесс, с помощью которого он обнаруживает пересечения, является основой алгоритма и его эффективности.

Чтобы реализовать логику развертки, мы должны сначала линейно упорядочить сегменты OMEGA, чтобы определить последовательность, в которой SL встречает их. То есть нам нужно упорядочить конечные точки {Ei0, Ei1} i = 1, n всех сегментов Li, чтобы мы могли определить, когда SL запускается и останавливается, пересекая каждый сегмент OMEGA. Традиционно конечные точки упорядочиваются путем увеличения сначала x, а затем увеличения значений координаты y, но подойдет любой линейный порядок (некоторые авторы предпочитают сначала уменьшать y, а затем увеличивать x). При традиционном упорядочении линия развертки является вертикальной и перемещается слева направо, когда встречается с каждым сегментом, как показано на схеме:

Pic-sweepline

В любой точке алгоритма линия развертки SL пересекает только те сегменты, у которых одна конечная точка находится слева от нее (или включена), а другая - справа от нее. Структура данных SL поддерживает динамический список этих сегментов путем: (1) добавления сегмента, когда встречается его крайняя левая конечная точка, и (2) удаления сегмента, когда встречается его крайняя правая конечная точка. Кроме того, SL упорядочивает список сегментов с отношением «выше-ниже». Таким образом, чтобы добавить или удалить сегмент, его позиция в списке должна быть определена, что может быть выполнено O (log-n) двоичным поиском в худшем случае текущих сегментов в списке. Кроме того, помимо добавления или удаления сегментов, существует другое событие, которое меняет структуру списка; а именно, когда два сегмента пересекаются, их позиции в упорядоченном списке должны поменяться местами. Учитывая два сегмента, которые должны быть соседями в списке, этот обмен является операцией O (log-n).

Чтобы организовать все это, алгоритм поддерживает упорядоченный эквалайзер «очередь событий», элементы которого вызывают изменение в списке сегментов SL. Первоначально, EQ устанавливается в упорядоченный список всех конечных точек сегмента. Но поскольку обнаружены пересечения между сегментами, они также добавляются в EQ в том же порядке развертки, что и для конечных точек. Однако необходимо проверить, чтобы избежать вставки дублированных пересечений в очередь событий. Пример на диаграмме выше показывает, как это может произойти. В событии 2 сегменты S1 и S2 приводят к тому, что пересечение I12 вычисляется и помещается в очередь. Затем, в событии 3, сегмент S3 находится между и разделяет S1 и S2. Затем, в событии 4, S1 и S3 меняются местами на линии развертки, и S1 снова переводится рядом с S2, вызывая повторное вычисление I12. Но для каждого пересечения может быть только одно событие, и I12 нельзя поставить в очередь дважды. Таким образом, когда пересечение помещается в очередь, мы должны найти его потенциальное отсортированное по x расположение в очереди и проверить, что его там еще нет. Поскольку для любых двух сегментов существует не более одной точки пересечения, маркировки пересечения идентификаторами для сегментов достаточно для однозначной идентификации. В результате всего этого максимальный размер очереди событий = 2n + k.le.2n + n2 и любая вставка или удаление могут быть выполнены с O (log (2n + n2)) = O (log-n бинарный поиск.

Но как все это связано с эффективным поиском полного набора пересечений сегментов? Итак, поскольку сегменты последовательно добавляются в список сегментов SL, определяются их возможные пересечения с другими приемлемыми сегментами. Когда найдено правильное пересечение, оно вставляется в очередь событий. Кроме того, когда событие пересечения в EQ обрабатывается во время развертки, тогда оно вызывает переупорядочение списка SL, и пересечение также добавляется в список вывода LAMBDA. В конце концов, когда все события будут обработаны, LAMBDA будет содержать полный упорядоченный набор всех пересечений.

Однако есть одна критическая деталь, сердце алгоритма, которую нам еще нужно описать; а именно, как вычислить правильное пересечение? Ясно, что два сегмента могут пересекаться только в том случае, если они одновременно происходят на линии развертки. Но этого недостаточно, чтобы сделать алгоритм эффективным. Важное наблюдение заключается в том, что два пересекающихся сегмента должны находиться непосредственно над соседями на линии разметки. Таким образом, есть только несколько ограниченных случаев, для которых необходимо вычислить возможные пересечения:

Когда сегмент добавлен в список SL, определите, пересекается ли он с его соседями сверху и снизу.

Когда сегмент удаляется из списка SL, его предыдущие соседи сверху и снизу объединяются как новые соседи. Таким образом, их возможное пересечение должно быть определено.

При событии пересечения два сегмента переключают позиции в списке SL, и их пересечение с их новыми соседями (по одному для каждого) должно быть определено. Это означает, что для обработки какого-либо одного события (конечной точки или пересечения) EQ необходимо сделать не более двух определений пересечения.

Остается одна деталь, а именно время, необходимое для добавления, поиска, замены и удаления сегментов из структуры SL. Для этого SL может быть реализован в виде сбалансированного двоичного дерева (такого как AVL, 2-3 или красно-черного дерева), которое гарантирует, что эти операции займут самое большее O (log-n) время, так как n максимальный размер списка SL. Таким образом, каждое из (2n + k) событий имеет в худшем случае обработку O (log-n). Суммируя начальную сортировку и обработку событий, эффективность алгоритма: O (nlog-n) + O ((2n + k) log-n) = O ((n + k) log-n).

Псевдокод: алгоритм Бентли-Оттмана

Собрав все это вместе, логика верхнего уровня для реализации алгоритма Бентли-Оттмана задается следующим псевдокодом:

    Initialize event queue EQ = all segment endpoints;
    Sort EQ by increasing x and y;
    Initialize sweep line SL to be empty;
    Initialize output intersection list IL to be empty;

    While (EQ is nonempty) {
        Let E = the next event from EQ;
        If (E is a left endpoint) {
            Let segE = E's segment;
            Add segE to SL;
            Let segA = the segment Above segE in SL;
            Let segB = the segment Below segE in SL;
            If (I = Intersect( segE with segA) exists) 
                Insert I into EQ;
            If (I = Intersect( segE with segB) exists) 
                Insert I into EQ;
        }
        Else If (E is a right endpoint) {
            Let segE = E's segment;
            Let segA = the segment Above segE in SL;
            Let segB = the segment Below segE in SL;
            Delete segE from SL;
            If (I = Intersect( segA with segB) exists) 
                If (I is not in EQ already) 
                    Insert I into EQ;
        }
        Else {  // E is an intersection event
            Add E’s intersect point to the output list IL;
            Let segE1 above segE2 be E's intersecting segments in SL;
            Swap their positions so that segE2 is now above segE1;
            Let segA = the segment above segE2 in SL;
            Let segB = the segment below segE1 in SL;
            If (I = Intersect(segE2 with segA) exists)
                If (I is not in EQ already) 
                    Insert I into EQ;
            If (I = Intersect(segE1 with segB) exists)
                If (I is not in EQ already) 
                    Insert I into EQ;
        }
        remove E from EQ;
    }
    return IL;
}

Эта процедура выводит полный упорядоченный список всех точек пересечения.

Это выглядит очень полезным, но не полностью отвечает на вопрос. В частности, представьте, что я могу найти пересечение X для сегментов BC и FE выше. Что мне тогда делать? Мне нужно пройти в порядке ABXEDCXF, но как правильно отсортировать два вхождения X в соответствующие два местоположения? Phrogz
Нет, ты должен разделить свой многоугольник. Я имею в виду, когда вы видите пересечение, вы должны создать дочерний многоугольник и продолжить, как если бы у вашего исходного многоугольника больше не было этого потомка. После очистки всего домена у вас будет список дочерних многоугольников, которые образуют ваш исходный многоугольник при сложении вместе. Таким образом, исходная область будет суммированием областей этих дочерних многоугольников. Вы также можете увидеть эту ценную книгу о вычислительная геометрия Semih Ozmen
Пока эта ссылка может ответить на вопрос, лучше включить сюда основные части ответа и предоставить ссылку для справки. Ответы, содержащие только ссылки, могут стать недействительными при изменении связанной страницы. SOFe
Приведенный выше комментарий является правильным. Правильный способ - разделить многоугольник так, как г-н Озмен описывает выше. Javascript Clipper Sourceforge.net / проекты / jsclipper делает именно это. В самом ближайшем будущем он также введет рекурсивное адаптивное подразделение Безье, чтобы преобразовать их в многоугольники, чтобы можно было также рассчитывать изогнутые формы с минимальными затратами времени на вычисления. Nik Kyriakides
Ответы должны быть автономными, потому что гиперссылки в будущем могут прекратиться. mbomb007
3

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

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

После этого найдите все пересечения вашего многоугольника.

Вы должны вычесть из выпуклой оболочки лишние многоугольники, которые не принадлежат исходному многоугольнику, чтобы найти область многоугольника, назовите их Badpoly. Badpolys всегда иметь хотя бы одну границу на выпуклой оболочке, так что эта граница не принадлежит вашему исходному многоугольнику, назовите их Badborder, перебирая выпуклый корпус, вы можете найти все Badborders, но для поиска других границ Badpoly, следующая связанная граница с данной Badborder который имеет наименьший угол относительно Badborder является одной из границ вашего Badpoly, вы можете продолжить, чтобы найти все границы вашего Badpoly, а затем рассчитать его площадь, также, повторяя таким образом, вы можете рассчитать площадь всех Badpolys.

Кажется, это тоже сработает, но из-за всех вычислений счетчиков и вычислений площади вычисления будут расти. Я буду помнить об этом для подобных случаев, спасибо, хороший способ мышления Semih Ozmen
-2

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

haha, я решил проблему вычисления самопересекающегося многоугольника, преобразовав самопересекающийся многоугольник в многоугольники.

вот мой код.

https: //github.com/zslzz/intersection_polygo

class SdPolygon(object):

  def __init__(self, points=None):
    points = self.parafloat(points)
    self.points = points
    self.current_points = []
    self.sd_polygons = []
    self.gene_polygon()
    from shapely.ops import cascaded_union
    self.sd_polygon = cascaded_union(self.sd_polygons)

  def parafloat(self, points):
    """
    为保证准确,将所有的浮点数转化为整数
    :return:
    """
    para_point = [(int(x), int(y)) for x, y in points]
    return para_point

  def gene_polygon(self):
    for point in self.points:
        self.add_point_to_current(point)  # 依次将点加入数组
    p0 = Polygon(self.current_points)
    self.sd_polygons.append(p0)

  def add_point_to_current(self, point):
    """
    将该点加入到current_points 中,倒序遍历current_points中的点,如果能围成多边形,则将所围成的点弹出
    :param point:
    :return:
    """
    if len(self.current_points) < 2:
        self.current_points.append(point)
        return
    cross_point_dict = {}  # 记录线段与其他点的相交点,{0:P1,6:P2}
    l0 = Line(Point(point[0], point[1]), Point(self.current_points[-1][0], self.current_points[-1][1]))
    for i in range(0, len(self.current_points) - 1):
        line = Line(Point(self.current_points[i][0], self.current_points[i][1]),
                    Point(self.current_points[i + 1][0], self.current_points[i + 1][1]))
        cross_point = self.get_cross_point(l0, line)  # 获取相交点
        if self.is_in_two_segment(cross_point, l0, line):  # 如果相交点在两个线段上
            cross_point_dict.update({i: cross_point})
    flag_dict = {}  # 保存剪下点的信息
    cross_points_list = sorted(cross_point_dict.items(), key=lambda item: item[0], reverse=True)  # [(3,P),(1,P)]
    for cross_point_info in cross_points_list:
        cross_i, cross_point = cross_point_info[0], cross_point_info[1]
        if flag_dict:  # 对应需要剪下多个多边形的情形,
            points = self.current_points[cross_i + 1:flag_dict['index'] + 1]
            points.append((flag_dict['point'].x, flag_dict['point'].y))
            points.append((cross_point.x, cross_point.y))
            p = Polygon(points)
            self.sd_polygons.append(p)
        else:
            points = self.current_points[cross_i + 1:]
            points.append((cross_point.x, cross_point.y))
            p = Polygon(points)
            self.sd_polygons.append(p)  # 将生成的polygon保存
        flag_dict.update(index=cross_i, point=cross_point)
    if flag_dict:
        point_list = self.current_points[:flag_dict['index'] + 1]  # 还未围成多边形的数组
        point_list.append((flag_dict['point'].x, flag_dict['point'].y))  # 加上交点
        self.current_points = point_list
    self.current_points.append(point)

  def is_in_segment(self, point, point1, point2):
    """
    交点是否在线段上
    :param point:(x,y)
    :param point1:[(x1,y1),(x2,y2)]
    :param point2:
    :return:
    """
    if point1.x > point2.x:
        minx = point2.x
        maxx = point1.x
    else:
        minx = point1.x
        maxx = point2.x
    if point1.y > point2.y:
        miny = point2.y
        maxy = point1.y
    else:
        miny = point1.y
        maxy = point2.y
    if minx <= point.x <= maxx and miny <= point.y <= maxy:
        return True
    return False

  def is_in_two_segment(self, point, l1, l2):
    """
    点 是否在两段 线段中间
    :param point:
    :param l1:
    :param l2:
    :return:
    """

    def is_same_point(p1, p2):
        """
        判断点是否相同
        :param p1:
        :param p2:
        :return:
        """
        if abs(p1.x - p2.x) < 0.1 and abs(p1.y - p2.y) < 0.1:
            return True
        return False

    if self.is_in_segment(point, l1.p1, l1.p2) and self.is_in_segment(point, l2.p1, l2.p2):
        if (is_same_point(point, l1.p1) or is_same_point(point, l1.p2)) and (
                    is_same_point(point, l2.p1) or is_same_point(point, l2.p2)):
            # 判断是否在两条线段的端点上
            return False
        return True
    return False

  def get_line_para(self, line):
    """
    规整line
    :param line:
    :return:
    """
    line.a = line.p1.y - line.p2.y
    line.b = line.p2.x - line.p1.x
    line.c = line.p1.x * line.p2.y - line.p2.x * line.p1.y

  def get_cross_point(self, l1, l2):
    """
    得到交点
    :param l1: 直线Line
    :param l2:
    :return: 交点坐标Point
    """
    self.get_line_para(l1)
    self.get_line_para(l2)
    d = l1.a * l2.b - l2.a * l1.b
    p = Point()
    if d == 0:
        return p
    p.x = ((l1.b * l2.c - l2.b * l1.c) // d)
    p.y = ((l1.c * l2.a - l2.c * l1.a) // d)
    return p

Похожие вопросы