Помогите, пожалуйста, с тригонометрическим алгоритмом.

Вот графическое изображение проблемы: http://i.imgur.com/aBG3p.jpg

Имея начальную точку (x1,y1) и конечную точку (x2,y2), я должен определить, открыт ли путь между двумя точками или, если он не открыт, по какой координате происходит столкновение.

Это была бы тривиальная проблема, если бы не специальные правила:

  1. Линия может пересекать точку, называть ее (i,j) в малой и разной степени, не вызывая столкновения. Если (i,j) непосредственно примыкает к (x1,y1), мы можем безопасно срезать примерно 0,4 по его углам, не вызывая столкновения. Однако мы не можем срезать 0,4, если проходим прямо через него, только по углам. Это число сужается примерно до 0,2 по мере удаления от (x, y). К сожалению, я просто пытаюсь реконструировать то, что видел однажды, поэтому не знаю точных значений, я лишь приблизительно их оцениваю.

  2. Предостережение к 1: если пространство непосредственно рядом с (i,j) в плоскости, которую мы пересекаем, на той стороне, которую мы пересекаем, также занято, столкновение произойдет несмотря ни на что. Столкновение произойдет (i,j), если мы перехватим его слишком сильно, иначе в соответствующем соседнем тайле.

Я предпринял несколько попыток решить эту проблему, но всегда заканчивал ложными отрицательными результатами и/или столкновением, возникающим на неправильной плитке. Я пытался сделать это без учета угла, просто глядя на десятичные точки x и y, когда мы движемся по линии. Я не уверен, возможно ли это сделать, или я должен каким-то образом использовать угол, или может ли использование угла каким-то образом облегчить мою жизнь.

Пожалуйста, помоги, если можешь!


trigonometry algorithm math
person user1012037    schedule 28.10.2011    source источник
comment
Прямоугольники имеют размер 1x1 и все выровнены по сетке.   -  person user1012037    schedule 28.10.2011
comment
что именно вы подразумеваете под сокращением на 0,4? 0,4 дробь? если да, то часть чего? Можете ли вы объяснить 1 немного по-другому, возможно?   -  person vlsd    schedule 28.10.2011
comment
Прямоугольники имеют размер 1x1, но мне нужно иметь возможность безопасно обрезать углы, не вызывая столкновения. Я не совсем уверен, как это назвать. Вероятно, площадь разрезанного треугольника и длины двух его сторон будут важны для предотвращения ложных срабатываний/отрицательных результатов.   -  person user1012037    schedule 28.10.2011

Ответы (1)


arrow_upward
2
arrow_downward

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

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

person AShelly    schedule 28.10.2011
comment
Очень интересная идея. Попытка вычислить площадь области, которая пересекается прямо сейчас, и это довольно сложно. Я уже могу довольно легко проверить соседние координаты, поэтому мне даже не нужно использовать единичные окружности (я думаю, что они были бы слишком ограничивающими). - person user1012037; 28.10.2011