Как проверить принадлежность точки выпуклому многоугольнику за O(log n)?
Многоугольник выпуклый, задан против часовой стрелки, вершин много (до 1e5), а запросов «точка внутри?» ещё больше. Линейный ray casting за O(n) на запрос не проходит по времени. Как сделать каждый запрос за O(log n) через бинпоиск по углу?
2 ответа
Идея: зафиксируем вершину p[0] как опорную и из неё лучами в остальные вершины разобьём многоугольник на n−2 треугольника-сектора. Запрос-точка попадает ровно в один сектор; его границу (по полярному углу относительно p[0]) находим бинпоиском, а потом одной проверкой orient определяем, внутри ли точки сектора.
// poly — выпуклый, CCW, poly[0] — опорная
bool pointInConvex(const vector<P>& poly, const P& q) {
int n = poly.size();
// q должна быть в угловом диапазоне сторон [poly[1]] .. [poly[n-1]] от poly[0]
if (orient(poly[0], poly[1], q) < 0) return false;
if (orient(poly[0], poly[n-1], q) > 0) return false;
int lo = 1, hi = n - 1;
while (hi - lo > 1) { // ищем сектор бинпоиском по углу
int mid = (lo + hi) / 2;
if (orient(poly[0], poly[mid], q) >= 0) lo = mid;
else hi = mid;
}
// q между лучами на poly[lo] и poly[hi]; проверяем ребро
return orient(poly[lo], poly[hi], q) >= 0;
}
Бинпоиск выбирает сектор за O(log n), затем единственная проверка orient по «дальнему» ребру сектора говорит, внутри ли точка. Всё на orient — целочисленно, без углов и atan2. Каждый запрос O(log n), предобработки нет (если многоугольник уже выпуклый и CCW).
Грабли. Первое — ориентация: алгоритм требует строго CCW обход и poly[0] как опорную; если многоугольник по часовой, сначала разверни (makeCCW). Знаки orient для CW будут зеркальными, и проверки сломаются.
Второе — граница: я использую >= 0, то есть точки на рёбрах считаются «внутри». Если по условию граница не входит, замени на строгие > 0 в финальной проверке и аккуратнее с краевыми лучами.
Третье — отсев по углу: первые две проверки (poly[1] и poly[n-1]) отбрасывают точки вне углового веера ещё до бинпоиска. Без них бинпоиск может вернуть мусор для точек «позади» опорной вершины. И стандартное: orient на __int128 при больших координатах. Для одиночного запроса проще ray casting O(n), а O(log n) выигрывает именно при множестве запросов.