Как пересечь график, основанный на угле между двумя краями

Question

Я застреваю в проблеме обхода графика на основе угла между двумя краями. Я хотел бы суммировать проблему следующим образом, учитывая 5 вершин a,b,c,d,e и краями (a, b), (b, c), (c, d), (d, e).

Если я хочу пересечь график, основанный на вычислении угла между двумя ребрами, например, angle((a, b), (b, c)). Если мой угол больше 10 градусов, я должен остановиться на b и снова начать процесс.

Какие шаги необходимо предпринять для решения этой проблемы с конкретными структурами программирования.

Answer 1

Если я правильно понял, когда angle((a,b),(b,c)) возвращает значение над некоторым порогом (10 в вашем примере), вы должны прекратить перемещение графика.

Это означает, что этот узел (b) не помогает, соединяя два края ((a,b) и (b,c)). Это может быть полезно для некоторых других наборов ребер, но это конкретное соединение недоступно.

Что я предлагаю, это замена роли ребер и узлов. Каждое ребро в G становится узлом в G', и каждый узел в G становится и ребер в G'только, если значение angle() возвращает значение, меньшее вашего порогового значения.

G' Теперь вы можете запускать BFS, DFS или любой другой алгоритм по своему вкусу. Когда вы закончите, используйте обратное преобразование, чтобы «перевести» свой ответ обратно в исходный граф, о котором идет речь.