Ответ 1

Поместите ваши полигоны в структуру пространственного поиска, например R-tree на основе минимальных ограничивающих прямоугольников для многоугольников. Затем вы должны иметь возможность вычислить отношение сдерживания, которое вы используете в O (n log n). (Если вы не в патологическом случае, когда многие из минимальных ограничивающих прямоугольников для ваших полигонов перекрываются, что кажется маловероятным на основе вашего описания.)

Отредактировано для добавления: конечно, вы не полагаетесь на R-дерево, чтобы сказать вам, есть ли один полигон внутри другого (он основан на минимальных ограничивающих прямоугольниках, чтобы он мог только приблизиться). Вы используете R-дерево для дешевой идентификации кандидатов, которые вы затем проверяете дорогим способом (проверяя, что точка в одном полигоне находится внутри другого).

Ответ 2

(Этот подход следует аналогичной идее для @GarethRees: во-первых, дешево обнаруживайте, какие пары полигонов вам не нужно проверять на включение. Как только количество пар, все еще необходимое для проверки, допустимо, сделайте точное ( дорогая) геометрическая проверка.)

Легко вычислить для каждого многоугольника p ограничивающий прямоугольник, т.е. левый, правый, верхний и нижний, поэтому сделаем это первым. Например. для left: p.L = min { x : (x,y) is a vertex of p } Время линейно в количестве точек.

Чтобы избежать сопоставления каждого многоугольника друг с другом, вы можете разделить область на сетку 2x2. Предположим, что ширина и высота области соответственно заданы Dx и Dy, тогда вы можете создать девять наборов top,bottom,left,right,topright,topleft,bottomright,bottomleft,rest и сделать следующее:

for p in polygons:
    in_top    = p.B > Dy/2
    in_bottom = p.T < Dy/2
    in_left   = p.R < Dx/2
    in_right  = p.L > Dx/2 
    if in_top:
        if in_left:
            add p to topleft
        elsif in_right:
            add p to topright
        else:
            add p to top
    elsif in_bottom:
        if in_left:
            add p to bottomleft
        elsif in_right:
            add p to bottomright
        else:
            add p to bottom

    if in_right and not (in_top or in_bottom):
        add p to right
    elsif in_left and not (in_top or in_bottom):
        add p to left

    if not (in_top or in_bottom or in_left or in_right):
        add p to rest

Это снова линейное время. Каждый многоугольник был привязан к самому "плотно" сектору. Что вы получили от этого? Ну, вы знаете, например, что для любого полигона p в left не может быть никакого отношения включения к набору right, поэтому вам не нужно их сравнивать. Точно так же между bottomleft и right, bottomleft и topleft и т.д. Вот как это было бы на вашем примере:

                      Dx/2
+----------------------|---------------------+
|                      |                     |
|   +----------------+ |        +--------+   |
|   |                | |       /         |   |
|   |   +--------+   | |      /          |   |
|___|___|________|___|_|____ /__+===d(2)=+___|_ Dy/2
|   |   |        |   | |    /   |            |
|   |   +---b(3)-+   | |   /    |   +---+    |
|   |                | |  +-----+   |   |    |
|   +-----------c(2)-+ |            e(2)+    |
|                      |                     |
+----------------------|----------------a(1)-+

So rest = {a}, top = {}, bottom = {}, left = {b,c}, right = {d}

topleft = {}, topright = {}, bottomleft = {}, bottomright = {e}

Итак, в настоящее время вам нужно сравнить (с дорогой точной проверкой) не более b до c, d до e и a ко всем остальным - на самом деле, если вы заказываете проверок умным способом, вам не нужно сравнивать a со всеми остальными, поскольку включение транзитивно, поэтому, если вы заметили, что c включает b, а a включает c, тогда вы не нужно проверять, включает ли a b.

Еще один момент заключается в том, что вы можете применить приведенные выше рассуждения рекурсивно. Скажем, например, набор topright слишком велик для вашего вкуса; вы можете применить такую ​​же методику, разделив эту субрегион (просто нужно получить право на ведение бухгалтерского учета).

Ответ 3

Мне кажется, вам удастся сортировать полигоны, используя проверку того, находится ли внутри внутри оператора сравнения.

Шаг 1

Предположим, что мы определяем соотношение '<' между многоугольниками: A < B, если A находится внутри B. Так получилось, что если A < B и B < C, то A < C (т.е. Если многоугольник A находится внутри B и B внутри C, то A должно быть внутри C). Теперь мы имеем строгое слабое упорядочение между произвольными многоугольниками.

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

Шаг 2

Сортируйте полигоны в соответствии с этим сравнением, используя ваш любимый алгоритм сортировки на основе сравнения. Например, сортировка слияния имеет худшую временную сложность сравнений O (nlogn), где n - количество полигонов.

[Edit: Это важный шаг, потому что он избавляется от квадратичной сложности.]

Шаг 3

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

Шаг 4

Теперь самым крупным (то есть самым внешним) многоугольником должен быть первый элемент.

[Edit: Фактически, полигоны были отсортированы в соответствии с их глубиной. Однако два многоугольника, которые имеют одинаковую глубину, могут отображаться в разных порядках в зависимости от того, была ли эта сортировка устойчивой. Это не имеет значения для нас; нас интересует изменение по глубине.]

Теперь мы будем задавать глубину для каждого многоугольника следующим образом. Во-первых, инициализируйте глубину каждого из них до 0 ([Edit: initialize to 1, в соответствии с примером]). Затем перебираем отсортированный список, но на этот раз сравниваем каждый элемент p только с следующим элементом p + 1. Если (p + 1 < p) истинно, то увеличивайте глубину p + 1. Else, установите глубину p + 1 равной глубине p.

Ответ 4

Шаг 1: Ориентируйте свои полигоны в одном направлении, скажем, против часовой стрелки.

Шаг 2: для любой точки (x, y), для которой вам нужно вычислить "глубину" для вычисления общего числа обмотки. Это можно сделать несколькими способами; наиболее быстрым на практике является вычисление ЗНАЧЕННОГО числа пересечений между горизонтальным (или вертикальным) лучом, исходящим из (x, y).

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