Перетин, Детальна інформація

if (s3 перетинає s2) then A \xF0AC\xF020(s3, s2);

if (s1 перетинає s4) then A \xF0AC\xF020(s1, s4);

поміняти місцями s1 та s2 в T;

end;

/* обробити знайдені точки перетину */

while (A \xF0B9\xF020\xF0C6) do

begin

(s, s’) \xF0AC\xF020A;

x \xF0AC\xF020спільна абсциса s та s’;

if ( ЧЛЕН(x, E) = FALSE) then

begin

print (s, s’);

ВСТАВИТИ(x, E);

end;

end;

end;

end.

Теорема. На множині з N відрізків можна знайти K перетинів за час O((N + K) log N).

Впорядкування ребер планарного графу

Планарний граф G будемо розглядати як орієнтований граф, в якому ребра направлені зліва направо. За графом G визначимо двоїстий граф G* : кожній обмеженій грані f відповідає вершина f*. G* містить ще дві додаткові вершини s* та t*, які знаходяться в необмеженій області. Кожному ребру e \xF0CE\xF020G, суміжному з гранями f1 та f2 (грань f1 знаходиться під гранню f2) поставимо у відповідність ребро e* = (f1*, f2*) в G*. Якщо грань f1 (відповідно f2) є необмеженою, тоді відповідним ребром в G* буде (s*, f2*) (відповідно (f1*, t*) ).

Граф G Двоїстий граф G*

Від ребра e до ребра e’ з G існує шлях тоді і тільки тоді, коли існує шлях з e* до e’* у G*.

P2

P3

P4

P1

P2

P3

P4

P1