Может кто-нибудь объяснить, пожалуйста, алгоритм наведения лучей для точки в многоугольнике, т.е. проверки на содержание?

Question

Рассмотрим многоугольник с двумя петлями, т.е. с внешней и внутренней петлями, как показано на изображениях, прикрепленных к этому вопросу. Может кто-нибудь объяснить, как именно алгоритм Ray-Casting будет работать в таких случаях? Если возможно, пожалуйста, поместите несколько изображений / рисунков в ответ, для лучшей визуализации и понимания.

Answer 1

Представьте себе точку, перемещающуюся от бесконечности к целевой точке по прямой линии (также будет работать с кривой).

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

Алгоритмически, вы подсчитываете пересечения сегментов, которые определяют форму с половиной линии к цели.