HGA* в сложных доменах

Ослабим предположение о том, что все препятствия на МТ-графе имеют прямоугольную форму. Опишем неформально процедуру выделения опорных клеток в этом случае.

Как и раньше будем полагать, что клетка s лежит на правее клетки g, а нуль-траеткория tr(s, g) пересекает препятствие Obs в клетке X. Будем двигаться вдоль границы препятствия по часовой стрелке до тех пор, пока не совершим движение в горизонтальном направлении слева направо. Таким образом, мы выделим опорную клетку A (см. рис. 2а), первую из серии опорных клеток, расположенных выше препятствия, которые войдут в искомый частичный путь. Для отыскания первой клетки, расположенной ниже, выполним аналогичные действия — будем двигаться вдоль границы препятствия, но против часовой стрелки, пока не совершим движение в горизонтальном направлении слева направо.

После выделения опорных клеток A и B, разбиение секции s, g может быть осуществлено стандартным образом на {s, A, g} и {s, B, g}. Однако при таком подходе, возникает следующая проблема. Если, после нескольких итераций алгоритма, A и g становятся локальными начальной и целевой клетками, то при разбиении секции A, g клетка B будет обнаружена снова. И после разбиения A, g множество PPC будет содержать взаимно противоречивые элементы: PP₁={…, s, A, С, g, …}, PP₂={…, s, A, B, g, …}, PP₃={…, s, B, g…} (см. рис. 2).

Для поддержания целостности множества PPC необходимо следовать следующему простому правилу: если некоторая секция s, g разбивается с помощью некоторой клетки A, лежащей выше препятствия Obs, секция A, g не должна разбиваться с помощью клетки, лежащей ниже Obs. Соблюдение данного правило может быть реализовано с помощью приписывания клетке A не только указателя на клетку s, но и на клетку X (клетку, в которой tr(s, g) пересекает Obs). Впоследствии, если клетка X будет обнаружена при «скольжении» вдоль контура препятствия по (против) часовой стрелки, во время разбиения A, g, необходимо остановить процедуру поиска опорной клетки и продолжить скольжение лишь в противоположную сторону.