#javascript #java #c# #algorithm #geometry
#javascript #java #c# #алгоритм #геометрия
Вопрос:
Предположим, что есть исходная точка s = (x, y) и два угла a и b. Углы создают луч, световой конус из точки p. Я хотел бы получить список точек, которые находятся в пределах этой области и находятся на одинаковом расстоянии друг от друга по вертикали и горизонтали. Максимальное расстояние теоретически бесконечно (но ограничено чем-то другим, не рассматриваемым в этом алгоритме).
Я пробовал рекурсивный метод, и он работал для более широких углов. Для острых углов количество соседних квадратов должно было увеличиться, чтобы не получилось. Я попытался следовать одной из линий, описанных углами, и подсчитывать все точки внутри углов, расположенных вертикально. Это не удалось из-за вертикальных линий и стало очень беспорядочным из-за разных квадрантов и т.д. Я попытался применить двойную for-петлю грубой силы, но это заканчивается из-за избытка глупых точек, когда я увеличил степень детализации.
Мне нужна помощь, чтобы переформулировать проблему таким образом, чтобы она была более доступной. Я кодирую решение на C #, но, очевидно, проблема не зависит от технологии, поэтому подойдет что угодно.
Комментарии:
1. Обрабатывайте каждый квадрант отдельно; объединяйте точки, если лучи находятся в разных квадрантах. Когда оба луча находятся в одном и том же квадранте, либо (i) они оба <= 45 градусов, (ii) оба > 45 градусов, либо (iii) один ниже, а другой выше 45 градусов. Для (i) переместите алгоритм Брезенхэма вправо вдоль оси x, чтобы найти для каждого x самую нижнюю и самую верхнюю точки y между двумя лучами. Для (ii) сделайте то же самое, но продолжайте вверх по оси y. Для (iii) нарисуйте третий луч c ровно под углом 45 градусов, решите подзадачи для пар лучей (a, c) и (b, c) и сформируйте объединение. (Могут быть более быстрые способы.)
Ответ №1:
Для углов A и B в диапазоне -Pi/2..Pi/2 и B>A рассмотрим следующий подход: пусть начальной точкой луча будет (x0, y0) .
Тогда вертикальная линия сетки с координатами x1 будет содержать точки сетки внутри сектора, которые имеют координаты y в диапазоне
Ceil(y0 (x1-x0) * tg(A)) .. Floor(y0 (x1-x0) * tg(B))
Ceil округляется вверх, Floor округляется вниз (этот Y-диапазон может быть пустым)
Этот подход работает для углов в диапазоне Pi/2..3Pi/2 , если мы поменяемся углами. И для углов в разных полуплоскостях, если мы разделим сектор на x0 по вертикали на 2 части.
Другой способ — использовать горизонтальные линии развертки вместо вертикальных для некоторых ориентаций.
Комментарии:
1. Как насчет случаев, когда конус идет вертикально? Или если он попадает в два квадранта (скажем, между строками -1,1 и 1,1)? Довольно быстро все становится очень запутанным. Я чувствую, что должно быть простое решение, если я подхожу к проблеме под другим углом (угол, понял, хе-хе)…
2. Как я уже сказал, разделите такой конус вертикальной осью. (1,1)- (-1,1) должно дать (1,1)- (0,1) и (0,1)-(-1,1). Вы можете рассмотреть также горизонтальные линии развертки вместо вертикальных для такой ориентации конуса. Примечание — это довольно простое решение, оно дает целые диапазоны координат.
3. Теперь я понимаю, что вы имеете в виду. Довольно быстро все становится таким сомнительным, хе-хе. И, конечно, поскольку я имею дело с удвоениями, мне нужно будет это учитывать (вместо настила мне придется округлить его до определенного кратного чему-то). Я думаю, это просто неприятная проблема, поэтому потребуется неприятное решение. Спасибо, друг!
Ответ №2:
Идея состояла бы в том, чтобы сформулировать конус как линии, определяемые уравнениями:
строка 1: A1x B1y C1= 0
строка 2: A2x B2y C2= 0
Это означает, что любая точка, принадлежащая линии, удовлетворяет ее уравнению. И точки, расположенные выше, дают положительный результат, а расположенные ниже — отрицательный.
Точка, которую вы ищете, скажем, ниже line1 и выше line2… и на некоторой сетке.
Комментарии:
1. Что вы имеете в виду? Единственное дополнительное требование, чтобы линии не были параллельными для создания конуса. С этими двумя линиями вы фактически получили 4 конуса. Чтобы выбрать один из них, вы должны добавить ограничение для требуемого знака формулы линии.