184
правки
Изменения
→Псевдокод
MakeMonotone(P)
Construct(<tex>D</tex>); Construct(<tex>Q</tex>); // функция Construct создаёт объекты <tex>D</tex> и <tex>Q</tex> , описанные выше. bst <tex>T</tex> = new bst(); while Q <tex> Q \neq \varnothing </tex> Remove <tex>v_{max}</tex> from <tex>Q</tex> // удаление вершины с наивысшим приоритетом из <tex>Q</tex>
switch (Type_of_vertex(<tex>v_{max}</tex>)): //определение типа вершины
case 'start':
HandleStartVertex(<tex>v_{i}</tex>)
Insert <tex>e_{i}</tex> in <tex>T</tex>
<tex>helper(e_{i}) \leftarrow v_i</tex>
HandleSplitVertex(<tex>v_{i}</tex>)
edge <tex>e_j</tex> = <tex>l \cap P</tex>
Search <tex>e_j</tex> in <tex>T</tex> Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i})</tex>) in <tex>D</tex>
<tex>helper(e_{j}) \leftarrow v_i</tex>
Insert <tex>e_{i}</tex> in <tex>T</tex> <tex>helper(e_{i}) \leftarrow v_i</tex>v
В последующих трех функциях обработки вершины <tex>v_i</tex> происходит обращение к смежному ребру <tex>e_{i-1}</tex>. Это сделано для вершин, относительно которых внутренняя область <tex>P</tex> лежит справа от них самих (вершина <tex>v_6</tex>), либо для двух подряд идущих merge вершин, таких как <tex>v_2</tex> и <tex>v_8</tex>.
HandleEndVertex(<tex>v_{i}</tex>)
if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in <tex>D</tex> Delete <tex>e_{i-1}</tex> from <tex>T</tex>
HandleMergeVertex(<tex>v_{i}</tex>)
if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in <tex>D</tex> Delete <tex>e_{i-1}</tex> from <tex>T</tex>
edge <tex>e_j</tex> = <tex>l \cap P</tex>
Search <tex>e_j</tex> in <tex>T</tex>
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in <tex>D</tex>
<tex>helper(e_{j}) \leftarrow v_i</tex>
then
if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in <tex>D</tex> Delete <tex>e_{i-1}</tex> from <tex>T</tex> Insert <tex>e_{i}</tex> in <tex>T</tex>
<tex>helper(e_{i}) \leftarrow v_i</tex>
else
edge <tex>e_j</tex> = <tex>l \cap P</tex>
Search <tex>e_j</tex> in <tex>T</tex>
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in <tex>D</tex>
<tex>helper(e_{j}) \leftarrow v_i</tex>
