Область самопересекающегося многоугольника

Ответ 1

Вы можете попробовать Bentley-Ottmann со следующим псевдокодом из Эта страница

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

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

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

Pic-sweepline

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

Чтобы организовать все это, алгоритм поддерживает упорядоченную "очередь событий" EQ, элементы которой вызывают изменение в списке сегментов 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 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 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 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;
}

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

Ответ 2

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

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

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

• Вы должны вычесть дополнительные полигоны, которые не принадлежат вашему оригинальному многоугольнику из выпуклого корпуса, чтобы найти область полигона, назовите их badpoly. badpolys всегда имеют по крайней мере одну границу на выпуклой оболочке, так что эта граница не принадлежит вашему оригинальному многоугольнику, назовите их badborder, итерируя над выпуклым корпусом, вы можете найти все badborders, но для нахождения других границ badpoly, следующая связанная граница с данный badborder, который имеет наименьший угол относительно badborder, является одной из границ вашей badpoly, вы можете продолжить это, чтобы найти все границы вашей badpoly, а затем вычислить ее область, а также повторить этот способ, чтобы вы могли рассчитать площадь всех badpolys.

Ответ 3

В этом случае алгоритм Бентли-Оттмана не очень хорош.

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

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

вот мой код.

https://github.com/zslzz/intersection_polygon

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