Растеризация формы стадиона

Question

Я хочу работать с этой цифрой, которая называется стадионом:

Может быть определена с тремя параметрами как набориз всех точек, чье расстояние с отрезком линии [AB] меньше или равно r.

Учитывая выровненный по оси растр квадратных ячеек, где каждый квадрат определяется с помощью целочисленных координат, чтосамый эффективный способ вычислить совокупность всех ячеек, полностью или частично перекрывающих стадион?(Мне здесь не нужно никакого сглаживания)

Проблемы:

• Мне не удается найти алгоритм тестирования перекрытия стадиона
• Даже если бы у меня был один, мне пришлось бы перебирать весь мой растр (который практически бесконечен, но на котором я мог бы определить конечную зону поиска) и проверять каждую ячейку, перекрывает ли она стадион.Это была бы сложная вычислительная операция, и в моем проекте (игре) мне нужна относительно быстрая операция.

Answer 1

Вы можете использовать алгоритмы растеризации круга Брезенхэма (а также другие, такие как алгоритм средней точки).

Ключевой момент - симметрия.Пусть стадион (также имеет название «капсула») центрируется в начале координат и имеет параметры: радиус R и расстояние между полукругами D

Начало от правой точки дуги Брезенхэма (в координатах (R, 0))).Сгенерируйте точки (x,y), чтобы сформировать четверть круга, и сделайте отраженные и смещенные точки для создания горизонтальных линий развертки

(x + D/2 , y) connect to (-x - D/2, y)
(x + D/2, -y) connect to (-x - D/2, -y)

Для произвольной ориентации стоит отсортировать точки соединения по Y и составить до 5 областей - линий сканированиядуги-дуги, дуги-линии, линии-линии, линии-дуги, дуги-дуги.Затем вычислите координаты X-конца для каждой координаты Y