#algorithm #line #path-finding
#алгоритм #строка #поиск пути
Вопрос:
Представьте себе систему навигации GPS с линиями, соединяющими разные местоположения. Эти линии находятся на дорогах (всегда прямых, никогда не изогнутых), проходящих через несколько точек. Простое представление показано ниже.
Теперь возможно, что строки перекрываются. Строки, которые перекрываются, должны располагаться рядом с существующими строками. Как я могу добиться этого эффекта?
Как я могу построить систему, чтобы линии оставались рядом с перекрывающимися строками и никогда не пересекались друг с другом?
Предназначенный-
Не предназначено-
Комментарии:
1. То, что вы просите, может быть не всегда возможно.
2. Как насчет наилучшего решения или обходного пути для отображения перекрывающихся строк?
3. Это может быть слишком просто, но в некоторых случаях вы можете использовать одно из двух: настроить непрозрачность, чтобы линии были полупрозрачными (например, альфа = .5), или использовать линии разной ширины. Если у вас разная ширина, нарисуйте более широкую раньше. Оба варианта во многих случаях приведут к визуально понятной иллюстрации. (И оба плохи, если у вас более двух или трех перекрывающихся строк.)
Ответ №1:
Пока красная линия не пересекается сама с собой, определите «левую» часть линии относительно ее направления, вы можете использовать нормаль к линии и выбрать сторону. Затем добавьте коэффициент этой нормали к каждой конечной точке вашей исходной строки, и у вас будут конечные точки синей линии.
Комментарии:
1. Возможно, это то, что вы имели в виду, но с добавлением еще нескольких слов. Потребуется немало времени для вычисления пересечений, поскольку маршрут может даже описывать полный круг, поэтому простого добавления одного и того же вектора к каждому пересечению недостаточно. Но основная идея заключается в том, чтобы смещать каждый сегмент «влево» (сегменты должны иметь направление) на определенную величину. Затем вычислите пересечение для каждой пары последовательных строк. Смещение пересечения можно вычислить напрямую, используя направления пересекающихся сегментов, требуется немного векторной арифметики.