#algorithm #math #trigonometry
#алгоритм #математика #тригонометрия
Вопрос:
Вот графическое представление проблемы: http://i.imgur.com/aBG3p.jpg
Учитывая начальную точку (x1, y1) и конечную точку (x2, y2), я должен определить, открыт ли путь между двумя точками или, если он не открыт, в какой координате происходит столкновение.
Это была бы тривиальная проблема, за исключением специальных правил:
- Линия может перехватывать точку, называть ее (i, j) в малой и разной степени, не вызывая столкновения. Если (i, j) непосредственно примыкает к (x1, y1), мы можем безопасно сократить около 0,4 по его углам, не вызывая столкновения. Однако мы не можем сократить 0,4, если пройдем прямо через него, только по углам. Это число уменьшается примерно до 0,2 по мере удаления от (x, y) . К сожалению, я просто пытаюсь восстановить то, что видел однажды, поэтому я не знаю точных значений, я просто приближаю их.
- Предостережение к 1: если пространство непосредственно рядом с (i, j), в плоскости, которую мы пересекаем, на стороне, которую мы пересекаем, также занято, столкновение произойдет, несмотря ни на что. Столкновение произойдет (i, j), если мы перехватим его слишком сильно, в противном случае в соответствующей смежной плитке.
Я предпринял несколько попыток решить эту проблему, всегда заканчиваясь ложными отрицаниями и / или столкновением, возникающим на неправильной плитке. Я пытался сделать это без учета угла, просто посмотрев на десятичные точки x и y по мере продвижения по линии. Я не уверен, возможно ли это сделать, или я должен каким-то образом использовать угол, или если использование угла каким-то образом может облегчить мою жизнь.
Пожалуйста, помогите, если можете!
Комментарии:
1. Прямоугольники имеют размер 1×1, и все они выровнены по квадрату в сетке.
2. что именно вы подразумеваете под «сокращением на 0,4»? 0,4 дробь? если да, то часть чего? можете ли вы объяснить 1 немного по-другому, возможно?
3. Прямоугольники имеют размер 1×1, но мне нужно иметь возможность безопасно срезать углы, не вызывая столкновения. Я не совсем уверен, как это назвать. Вероятно, площадь срезаемого треугольника и длины его 2 сторон будут важны для предотвращения ложных срабатываний / негативов.
Ответ №1:
Похоже, вы могли бы получить результаты, аналогичные тем, которые вы описываете, рассматривая занятые сетки как содержащие единичные круги. Это позволит вам проходить углы, но блокировать любые 2 соседних, поскольку они соприкасаются.
Поэтому я бы попробовал использовать ваш текущий метод collision для быстрой проверки прямоугольников, а затем усовершенствовать его, как только вы обнаружите столкновение, проверив линию, входящую в поле, на окружность с центром в ней.
Комментарии:
1. Очень интересная идея. Пытаюсь вычислить площадь области, которая пересекается прямо сейчас, и это довольно сложно. Я уже могу довольно легко проверить соседнюю координату, поэтому мне даже не нужно использовать единичные круги (я думаю, они были бы слишком ограничительными).