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

3. ЧЛЕН(x, E). Чи є абсциса x членом E.

Перетин відрізків

begin

сортуємо 2*N кінців відрізків лексикографічно по x і y та розташовуємо їх у приоритетну чергу E.

A \xF0AC\xF020\xF0C6; /* робочий параметр процедури, стек */

while (E \xF0B9\xF020\xF0C6) do

begin

p \xF0AC\xF020MIN(E);

if (p – лівий кінець) then

begin

s \xF0AC\xF020відрізок, кінцем якого є p;

ВСТАВИТИ(s, T);

s1 \xF0AC\xF020НАД(s, T);

s2 \xF0AC\xF020ПІД(s, T);

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

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

end;

else if (p – лівий кінець) then

begin

s \xF0AC\xF020відрізок, кінцем якого є p;

s1 \xF0AC\xF020НАД(s, T);

s2 \xF0AC\xF020ПІД(s, T);

if (s1 перетинає s2 справа від p) then A \xF0AC\xF020(s1, s2);

ВИДАЛИТИ(s, T);

end;

else /* p – точка перетину */

begin

(s1, s2) \xF0AC\xF020відрізки, що перетинаються в p; /* причому s1 = НАД(s2) справа від p */

s3 \xF0AC\xF020НАД(s1, T);

s4 \xF0AC\xF020ПІД(s2, T);