пути отражения между точками in2d - PullRequest
3 голосов
/ 20 апреля 2010

Просто интересно, был ли хороший (уже реализованный / задокументированный) алгоритм для выполнения следующего
бух! http://img697.imageshack.us/img697/7444/sdfhbsf.jpg
Для любой фигуры (без пересечения ребер) и двух точек внутри этой фигуры вычислите все пути между двумя точками так, чтобы все отражения были идеальными отражениями. Длина пути должна быть ограничена определенной длиной, в противном случае существуют бесконечные решения. Я не заинтересован в том, чтобы просто снимать лучи, чтобы попытаться угадать, насколько близко я могу подойти, меня интересуют алгоритмы, которые могут сделать это отлично Поиски, а не догадки / улучшения.

Ответы [ 4 ]

3 голосов
/ 20 апреля 2010

Я думаю, вы можете добиться большего успеха, чем любители компьютерных технологий. Назовите свои баллы A и B. Вы хотите найти пути отражений от A до B.

Начните с отражения A в ребре и назовите отражение A1. Можете ли вы нарисовать линию от A1 до B, которая поражает только этот край? Если да, это означает, что у вас есть путь от A до B, который отражается по краю. Сделайте это для всех ребер, и вы получите все существующие пути одиночного отражения. Должно быть легко построить эти пути, используя свойства отражений. Попутно вам нужно проверить, что пути допустимы, то есть они не пересекают другие ребра.

Вы можете продолжить поиск путей, состоящих из двух отражений, отразив все отражения первого поколения A по всем краям и проверив, можно ли провести линию из этих точек через отражающий край до B , Продолжайте этот поиск, пока расстояние отраженных точек от B не превысит пороговое значение.

Надеюсь, это имеет смысл. Это должно быть проще, чем гоняться за фанатами и разбираться с их расставаниями, даже если вам все еще придется поработать.

Кстати, это уголок хорошо изученного поля для бильярда на столах различной геометрии. Конечно, бильярдный шар отскакивает от края стола так же, как свет отражается от зеркала, так что это просто еще один способ думать об отражениях. Вы можете вникнуть в это с помощью поисковых терминов, таких как polygonal billiards unfolding illumination, хотя математики, как правило, зацикливаются на поиске случаев, когда между двумя точками на многоугольном столе нет выстрелов пула, в отличие от непосредственного решения поставленной задачи.

2 голосов
/ 20 апреля 2010

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

Возможно, вы захотите взглянуть на методы радиации, которые, вероятно, похожи на те, что я только что описал, но обычно делаются в 3d.

0 голосов
/ 21 апреля 2010

В ответ на брейнджем
Вам все еще нужны клинья ...
альтернативный текст http://img72.imageshack.us/img72/6959/ssdgk.jpg
В этой ситуации, как вы узнали бы не делать второе отражение? Откуда вы знаете, над какими стенами имеет смысл задуматься?

0 голосов
/ 20 апреля 2010

Я не знаю ни одного существующего решения такой проблемы. Удачи вам, если вы найдете один, но если вы не сделаете первый шаг к полному, но экспоненциальный (в отношении количества строк) будет разбить его на две части:

  1. Учитывая упорядоченное подмножество стен A, B, C и точек P1, P2, рассчитайте, возможен ли маршрут (либо нет решений, либо одно уникальное решение).

  2. Затем генерируйте перестановки своих стен, пока не превысите предел, который вы имели в виду.

Первая часть может быть решена с помощью простого набора уравнений, чтобы найти необходимые углы для каждого отскока луча. Затем проверка каждой строки на наличие существующих строк на наличие коллизий покажет вам, возможен ли путь.

Параметры системы уравнений будут

angle_1 = normal of line A with P1
angle_2 = normal of line B with intersection of line A
angle_3 = normal of line C with ...
angle_n = normal of line N-1 with P2

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...