Изменения

Перейти к: навигация, поиск

Пересечение многоугольников (PSLG overlaying)

2 байта добавлено, 19:23, 17 мая 2015
Время работы
|}
==== Время работы ====
Большинство шагов алгоритма требуют работают константное время. Определение соседних полуребер с <tex>e'</tex> и <tex>e''</tex> происходит за линейное время от степени вершины. Следовательно, обновление РСДС не увеличивает время работы алгоритма пересечения отрезков, поэтому сведения о вершинах и полуребрах для итогового РСДС могут быть вычислены за время <tex>O(n \log{n} + k \log{n})</tex>, где <tex>n</tex> — сумма сложности <tex>S_1</tex> и <tex>S_2</tex>, <tex>k</tex> — сложность пересечения.
=== Грани ===
113
правок

Навигация