У меня есть непрерывная плоскость (2-D), содержащая многоугольные препятствия. Я равномерно выбираю плоскость в дискретных позициях, чтобы создать равномерную сетку точек. Сетка не имеет точек, где лежат препятствия (то есть отверстия, где когда-либо было препятствие), как показано на рисунке ниже.
(Пожалуйста, просмотрите изображение на http://i48.tinypic.com/2efnblg.png, чтобы получить четкое представление о том, чего я пытаюсь достичь. Я не смог встроить его)
Может ли кто-нибудь указать мне несколько хороших реализаций с оптимальной сложностью времени в худшем случае?