Точка в многоугольнике для большого количества точек

Мне интересно, какой способ может быть наиболее эффективным для определения того, большое количество точек (O (1 миллион) находятся внутри или вне набора (O (10)) многоугольников? Последние не обязательно являются выпуклыми, но в них нет отверстий. На данный момент я сокращаю количество точек, сравнивая их положение с ограничивающими прямоугольниками, затем использую этот метод числа пересечений для оставшихся точек. Но есть ли более быстрый метод?

6
задан Mogget 13 May 2011 в 22:55
поделиться