Поиск геометрической формы на декартовой плоскости по координатам

Question

У меня есть алгоритмическая проблема на картезианской плоскости. Мне нужно эффективно искать геометрические фигуры, которые пересекаются с данной точкой. Существует несколько форм (прямоугольник, круг, треугольник и многоугольник), но это не важно, потому что определение фактического включения точки не является проблемой здесь, я буду реализовывать их самостоятельно. Проблема заключается в определении того, какие формы необходимо проверить для включения с данной точкой. Итерация через все мои фигуры на плоскости и запуск метода включения точек на каждом из них неэффективна, так как количество экземпляров форм будет довольно большим. Моя первая идея состояла в том, чтобы разделить плоскость на сегменты (плоскость конечна, но слишком велика для любого 3D-массива), и при добавлении формы в базу данных я бы определил, с какими сегментами она будет пересекаться, и сохранить их в объекте форма. Затем, когда дается точка для проверки включения, мне нужно будет только определить сегмент, в котором находится точка, а затем проверить включение только с объектами, которые пересекаются с этим сегментом.

Это путь? Я не знаю, оптимален ли метод, который я описал, или если я чего-то не упускаю. Любая помощь будет оценена ..

Заранее спасибо

P.S .: Я буду писать это в C++. Это не очень актуально, так как это скорее алгоритмическая проблема, но я хотел бы выразить это, если кому-то было любопытно ...

Answer 1

Здесь можно использовать подход гридинга.

Посмотрите на плоскость как растровое изображение, где вы рисуете все свои фигуры с помощью алгоритма преобразования сканирования, чтобы все пиксели, даже частично покрытые, были заполнены. Для каждого пикселя изображения сохраните список фигур, которые его заполнили.

Запрос затем прост: найти пиксель, где точка запроса падает во время O(1) и проверять каждую форму в списке, во время O(K), где K является длиной списка, примерно равно числа пересекающихся фигур.

Если изображение состоит из пикселей N² и у вас есть M объектов, имеющих среднюю площадь A пикселей, вам нужно будет хранить N²+M.A список элементов (идентификатор формы + ссылку на следующий). Вы выберете размер пикселя для достижения хорошего компромисса между точностью и стоимостью хранения. В любом случае вы должны ограничить себя N²<Q.M, где Q - общее количество запросов, в противном случае стоимость просто инициализации изображения может превышать общее время запроса.

Если ваша сцена очень разреженная (больше пустот, чем фигуры), вы можете использовать сжатое представление изображения, используя quadtree.