Интернет магазин китайских планшетных компьютеров

Компьютеры - Задача о принадлежности точки многоугольнику - Алгоритмы c предобработкой

Выпуклые и звёздные многоугольники

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

Произвольный многоугольник

Задачу об принадлежности точки произвольному простому многоугольнику можно рассматривать как частный случай задачи о локализации точки в планарном подразбиении. Для N-угольника эта задача может быть решена за время O с использованием O памяти и O времени на предобработку.