Да страницу потянуло
Уже не могу редактить сообщение, видимо поставили срок на редактирование?
ЗЫ, это уже задача оптимизации. Из той картинки что ты выдал, найдёт, главное это научить работать с вершинами имеющими общие линии.
Я делал тест, с неоптимизированным алгоритмом, (никаких SSE, да и сам код был первым наброском), из 100 сложных линий (без вершин с отрезками больше 1 на вершину), насвозь проходит за 1-2 мс. При этом находя уже оптимизированный кротчайший путь. Правдо и есть баги, к примеру 2 отрезка пересечены - это раз, что нельзя делать. Второе это расстояние между отрезком и пдосторонней вершиной или отрезком слишком узкое - тоже нельзя. В общем тут много очень ограничений и минусов.