Перетин

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

begin

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

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

s1 НАД(s, T);

s2 ПІД(s, T);

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

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

end;

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

begin

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

s1 НАД(s, T);

s2 ПІД(s, T);

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

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

end;

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

begin

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

s3 НАД(s1, T);

s4 ПІД(s2, T);

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

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

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