Как определить плоскости на которых лежит окружность?

Question

[Aklaim]

Не знаю как правильно сформулировать вопрос, поэтому изображение должно помочь понять суть вопроса.

Опишу функционал который я хочу реализовать.
Дана прямоугольная карта размерами M на N. Поделенная на прямоугольные области. Об этих прямоугольниках известно все. Координаты точек, центр и т.д.
Так же дана окружность. Известен ее центр и радиус.
Необходимо рассчитать исходя из этих данных на какие области карты попадает окружность.

В результате расчетов исходя из рисунка должно получатся следующее.
Локальное событие затронет области 1, 2, 6, 7.
Глобальное событие затронет все области кроме 1 и 6.

Зачем это нужно.
Как можно понять из рисунка речь идет о событие которое должны узнать все объекты находящиеся в радиусе его действия. При этом объекты могут находится в разных областях и чтобы не проверять все подряд нужно сократить количество объектов узнав хотя бы области которые нужно проверять.

P.S. Посоветуйте толковые книги о математике необходимой для 2D игр.

Answer 1

[bobrovskyserg]

Прямоугольники пересекать умеете?
Тогда рассмотрите описанный вокруг круга квадрат, как первое приближение.
В толковых книгах пишут, что ошибка составит менее 1/3 от площади круга :)

Answer 2

[Андрей]

Я предложил бы проверять на попадание внутрь окружности 4 вершин прямоугольника.
Все, у которых попадает хотя бы одна вершина - затрагиваются.
Если ни одна из вершин не попала внутрь, то событие МОЖЕТ затрагивать максимум 5 прямоугольников - тот, в котором расположен ее центр + 4 прилегающие к нему (сверху, снизу, справа, слева) - просто проверить.

Comments

[Mrrl]

Даже если какие-то вершины внутрь попали, событие всё равно может затрагивать прямоугольники, у которых ни одна вершина не лежит внутри окружности. Так что некоторые отрезки проверять придётся.

[Андрей]

Да, согласен. Был не прав.

Answer 3

[Даниил Басманов]

Можете воспользоваться алгоритмами растеризации, там решаются похожие задачи.
en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
en.wikipedia.org/wiki/Midpoint_circle_algorithm
stackoverflow.com/questions/10878209/midpoint-circ...