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

Шаг 1

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

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

Шаг 2

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

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

Шаг 3

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

Шаг 4

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

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

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

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

Шаг 2: Для любой точки (x, y), для которой необходимо вычислить «глубину» для вычисления общего числа витков. Это можно сделать несколькими способами; самый быстрый на практике - вычислить ПОДПИСАННОЕ количество пересечений между горизонтальным (или вертикальным) лучом, берущим начало в (x, y).

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

В вашем примере вы изображаете невыпуклый многоугольник, поэтому подход rtree, предложенный другими, не будет эффективен сам по себе. Но вы можете объединить это с дополнительной проверкой, чтобы увидеть, находится ли одна из вершин многоугольника внутри другой, когда вы найдете совпадение с подходом rtree. Это уменьшит количество проверок "точка в многоугольнике".

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

1. Изначально каждый многоугольник является корневым узлом и отдельным деревом.
2. Вы должны перебрать свой набор корневых узлов и проверить, находится ли он внутри другого корневого узла, используя тест «точка в многоугольнике».
3. Когда вы найдете совпадение, удалите меньший многоугольник из набора корневых узлов и добавьте его в качестве дочернего узла к большему многоугольнику. Вы начали строить осмысленную древовидную структуру, и вы также уменьшаете размер контейнера, который вы повторяете (корневые узлы), поэтому будущие итерации будут быстрее.
4. Продолжайте так, пока количество корневых узлов не перестанет меняться.
5. Помните, что в основном вложенном цикле вы сравниваете, только если один корневой узел находится внутри другого. Когда вы найдете совпадение (маленький узел внутри большого узла), вы можете пропустить поддерево меньшего узла. Но вам нужно пройти поддерево большего узла и выполнить проверки, чтобы найти правильное место для меньшего узла в иерархии. Но все же вы избегаете множества проверок по сравнению с простым вложенным циклом с квадратичной сложностью.