Методы пересечения линий

Это - общий подход к проблеме, когда данные состоят из геометрических объектов, и мы имеем непрерывный тип местности. То есть все объекты - абсолютные препятствия в смысле, что через них нельзя пройти, а вся местность, не занятая объектом, рассматривается свободной, без изменения в скорости транспортного средства или других параметров.

Эти методы к сожалению не подходят для нашей проблемы, и из-за их непрерывной природы и из-за их неспособности обработывать растровые данные. Конечно, мы могли бы всегда преобразовать каждый растровый пиксел к многоугольнику, т.е. определенному числу 'линий', которые получаются, простым чередованием. Есть так же способы с не непрерывной местностью, но они ту же проблему быстро увеличивающегося размера графа, особенно для более сложной местности.

3.2