У меня есть сетка, которая показывает мир и его береговые линии. Отрывок из области вокруг Великобритании показан здесь 
Необходима консультация по алгоритму raytracing
Из произвольной точки происхождения в любом месте в океане, я хочу, чтобы найти те точки береговой линии, которые находятся в прямой видимости происхождения без необходимости пересекать другую точку береговой линии , Например, если происхождение находится на западной стороне Великобритании, я бы ожидал получить множество точек побережья Западной Ирландии и западной Великобритании, но не из Дании, поскольку «покрывается» Великобританией.
Мне нужен совет по быстрому алгоритму, который может «стрелять» лучами и обнаруживать, где эти лучи пересекают первую береговую линию (карта береговой линии доступна в двоичном формате).
В качестве альтернативы, я мог бы представить, чтобы двигаться по всем пикселям побережья, построить соединительную линию между началом и точкой береговой линии и проверить, нет ли другой точки береговой линии на соединительной линии. Находит ли какой-нибудь алгоритм, который мог бы эффективно выполнить эту проверку береговой линии?
Я понимаю, что этот вопрос - это выстрел в синем, но, возможно, есть кто-то умный, у которого есть знания в этой области. Буду признателен за любую оказанную помощь.
Возможно, вам стоит оставить свой вопрос на https://cs.stackexchange.com/ –
Если вы возьмете [этот ответ] (http://stackoverflow.com/questions/14307158/how-do-you-check-for -intersection-between-a-line-segment-and-line-ray-emanatin) и эффективно сохранять все ребра (например, делить карту на сетку и для каждого окна хранить края в (перекрестном)), , вы можете проверить, в какие поля входит луч, и какой из сегментов в этом поле он пересекает. Если вы начинаете с начала луча, вы можете просто проверить по порядку эти поля (вам может потребоваться проверить, какой сегмент близок к началу луча, если в одном поле есть несколько пересечений). –
Когда вы говорите, что береговая линия хранится как «двоичный формат», вы имеете в виду, что она хранится как растровое изображение? (т. е. двухмерный массив пикселей). Чаще всего для хранения береговых линий в качестве векторных изображений (списки сегментов линий). В зависимости от ответа алгоритм будет несколько отличаться (и его точность). – Gretchen