Методы пересечения линий
Это - общий подход к проблеме, когда данные состоят из геометрических объектов, и мы имеем непрерывный тип местности. То есть все объекты - абсолютные препятствия в смысле, что через них нельзя пройти, а вся местность, не занятая объектом, рассматривается свободной, без изменения в скорости транспортного средства или других параметров.
В этом случае, Евклидово расстояние самый короткий путь - также самый быстрый путь. Основная идея в следующем: сначала создайте выпуклую оболочку из всех объектов. Углы всех многоугольников оболочки определяют набор вершин. Соедините все вершины гранями. Затем сделайте некоторую более или менее разумную фильтрацию этих граней, и в заключение найдите самый короткий допустимый путь между источником и адресатом по ряду граней, используя стандартные алгоритмы графа. Основное различие между методами в этом классе алгоритмов поиска пути - как сделать фильтрацию. Цель фильтрации удаление линий, которые возможно не принадлежат самому короткому пути и поэтому резко уменьшают число путей которые необходимо исследовать. На первом шаге надо обычно удалить грани, которые (геометрически) пересекают любую другую оболочку, то есть те грани, которые прошли бы через препятствие. Затем различные правила основанные на 'норме расстояния' применяются, чтобы удалить слишком далеко идущие пути. В заключение, много алгоритмов используют некоторую эвристику, чтобы удалить дополнительные маловероятные грани, часто игнорируя требование о нахождении точных решений в каждом случае и получении взамен большого уменьшения в числе граней. Некоторые реализации методов пересечения линий могут быть найдены в [ELGR92], [MONT87] и [HOLM92].Эти методы к сожалению не подходят для нашей проблемы, и из-за их непрерывной природы и из-за их неспособности обработывать растровые данные. Конечно, мы могли бы всегда преобразовать каждый растровый пиксел к многоугольнику, т.е. определенному числу 'линий', которые получаются, простым чередованием. Есть так же способы с не непрерывной местностью, но они ту же проблему быстро увеличивающегося размера графа, особенно для более сложной местности.
3.2