E089. Проверка точки на принадлежность выпуклому многоугольнику

e-maxx algorithm original: C/C++ #algorithm #emaxx #geometry #math

선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.

Static

Источник: e-maxx.ru/algo, страница PDF 254.

Дан выпуклый многоугольник с N vertexми, координаты всех вершин целочисленны (хотя это не меняет суть решения); вершины заgiven в порядке обхода против часовой стрелки (в противном случае нужно просто отсортировать их). Поступают запросы - точки, и it is required для каждой точки определить, лежит она внутри этого многоугольника или нет (границы многоугольника включаются). На каждый запрос будем отвечать в режиме on-line за O (log N). Предварительная обработка многоугольника будет выполняться за O (N).

알고리즘

Решать будем бинарным поиском по углу. Один из вариантов решения таков. Выберем точку с наименьшей координатой X (если таких несколько, то выбираем самую нижнюю, т.е. с наименьшим Y). Относительно этой точки, обозначим её Zero, все остальные вершины многоугольника лежат в правой полуплоскости. Далее, заметим, что все вершины многоугольника уже упорядочены по углу относительно точки Zero (это вытекает из того, что многоугольник выпуклый, и уже упорядочен против часовой стрелки), причём все углы находятся в промежутке (-π/2 ; π/2]. Пусть поступает очередной запрос - некоторая точка P. Рассмотрим её полярный угол относительно точки Zero. Найдём бинарным поиском две такие соседние вершины L и R многоугольника, что полярный угол P лежит между полярными углами L и R. Тем самым мы нашли тот сектор многоугольника, в котором лежит точка P, и нам остаётся только проверить, лежит ли точка P в треугольнике (Zero,L,R). Это можно сделать, на예제, с помощью Ориентированной площади треугольника и Предиката "По часовой стрелке", достаточно посмотреть, по часовой стрелке или против находится тройка вершин (R,L,P). Таким образом, мы за O (log N) находим сектор многоугольника, а затем за O (1) проверяем принадлежность точки треугольнику, и, следовательно, требуемая Asymptotic complexity достигнута. Предварительная обработка многоугольника заключается только в том, чтобы предпосчитать полярные углы для всех точек, хотя, эти вычисления тоже можно перенести на этап бинарного поиска.

Замечания по реализации

Чтобы определять полярный угол, можно воспользоваться стандартной функцией atan2. Тем самым мы получим очень короткое и простое 해법, однако взамен могут возникнуть проблемы с точностью. given, что изначально все координаты являются целочисленными, можно получить 해법, вообще не использующее дробной арифметики. Заметим, что полярный угол точки (X,Y) относительно начала координат однозначно определяется дробью Y/X, при условии, что точка находится в правой полуплоскости. Более того, если у одной точки полярный угол меньше, чем у другой, то и дробь Y1/X1 будет меньше Y2/X2, и обратно. Таким образом, для сравнения полярных углов двух точек нам достаточно сравнить дроби Y1/X1 и Y2/X2, что уже можно выполнить в целочисленной арифметике.

구현

Эта 구현 предполагает, что в данном многоугольнике нет повторяющихся вершин, и площадь многоугольника ненулевая.

struct pt {

int x, y;

};

struct ang {

int a, b;

};

bool operator < (const ang & p, const ang & q) {

if (p.b == 0 && q.b == 0)

return p.a < q.a;

return p.a * 1ll * q.b < p.b * 1ll * q.a;

}

long long sq (pt & a, pt & b, pt & c) {

return a.x*1ll*(b.y-c.y) + b.x*1ll*(c.y-a.y) + c.x*1ll*(a.y-b.y);

}

int main() {

int n;

cin >> n;

vector<pt> p (n);

int zero_id = 0;

for (int i=0; i<n; ++i) {

scanf ("%d%d", &p[i].x, &p[i].y);

if (p[i].x < p[zero_id].x || p[i].x == p[zero_id].x && p[i].y

< p[zero_id].y)

zero_id = i;

}

pt zero = p[zero_id];

rotate (p.begin(), p.begin()+zero_id, p.end());

p.erase (p.begin());

--n;

vector<ang> a (n);

for (int i=0; i<n; ++i) {

a[i].a = p[i].y - zero.y;

a[i].b = p[i].x - zero.x;

if (a[i].a == 0)

a[i].b = a[i].b < 0 ? -1 : 1;

}

for (;;) {

pt q; // очередной запрос

bool in = false;

if (q.x >= zero.x)

if (q.x == zero.x && q.y == zero.y)

in = true;

else {

ang my = { q.y-zero.y, q.x-zero.x };

if (my.a == 0)

my.b = my.b < 0 ? -1 : 1;

vector<ang>::iterator it = upper_bound (a.

begin(), a.end(), my);

if (it == a.end() && my.a == a[n-1].a && my.

b == a[n-1].b)

it = a.end()-1;

if (it != a.end() && it != a.begin()) {

int p1 = int (it - a.begin());

if (sq (p[p1], p[p1-1], q) <= 0)

in = true;

} }

puts (in ? "INSIDE" : "OUTSIDE");

} }

C# 해법

자동 초안, 제출 전 검토

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    struct pt {
            int x, y;
    };
    struct ang {
            int a, b;
    };
    bool operator < (const ang & p, const ang & q) {
            if (p.b == 0 && q.b == 0)
                    return p.a < q.a;
            return p.a * 1ll * q.b < p.b * 1ll * q.a;
    }
    long sq (pt & a, pt & b, pt & c) {
            return a.x*1ll*(b.y-c.y) + b.x*1ll*(c.y-a.y) + c.x*1ll*(a.y-b.y);
    }
    int main() {
            int n;
            cin >> n;
            vector<pt> p (n);
            int zero_id = 0;
            for (int i=0; i<n; ++i) {
                    scanf ("%d%d", &p[i].x, &p[i].y);
                    if (p[i].x < p[zero_id].x || p[i].x == p[zero_id].x && p[i].y
    < p[zero_id].y)
                            zero_id = i;
            }
            pt zero = p[zero_id];
            rotate (p.begin(), p.begin()+zero_id, p.end());
            p.erase (p.begin());
            --n;
            vector<ang> a (n);
            for (int i=0; i<n; ++i) {
                    a[i].a = p[i].y - zero.y;
                    a[i].b = p[i].x - zero.x;
                    if (a[i].a == 0)
                            a[i].b = a[i].b < 0 ? -1 : 1;
            }
            for (;;) {
                    pt q; // очередной запрос
                    bool in = false;
                    if (q.x >= zero.x)
                            if (q.x == zero.x && q.y == zero.y)
                                    in = true;
                            else {
                                    ang my = { q.y-zero.y, q.x-zero.x };
                                    if (my.a == 0)
                                            my.b = my.b < 0 ? -1 : 1;
                                    vector<ang>::iterator it = upper_bound (a.
    begin(), a.end(), my);
                                    if (it == a.end() && my.a == a[n-1].a && my.
    b == a[n-1].b)
                                            it = a.end()-1;
                                    if (it != a.end() && it != a.begin()) {
                                            int p1 = int (it - a.begin());
                                            if (sq (p[p1], p[p1-1], q) <= 0)
                                                    in = true;
                                    }
                            }
                    puts (in ? "INSIDE" : "OUTSIDE");
            }
    }
}

C++ 해법

매칭됨/원본

struct pt {
        int x, y;
};
struct ang {
        int a, b;
};
bool operator < (const ang & p, const ang & q) {
        if (p.b == 0 && q.b == 0)
                return p.a < q.a;
        return p.a * 1ll * q.b < p.b * 1ll * q.a;
}
long long sq (pt & a, pt & b, pt & c) {
        return a.x*1ll*(b.y-c.y) + b.x*1ll*(c.y-a.y) + c.x*1ll*(a.y-b.y);
}
int main() {
        int n;
        cin >> n;
        vector<pt> p (n);
        int zero_id = 0;
        for (int i=0; i<n; ++i) {
                scanf ("%d%d", &p[i].x, &p[i].y);
                if (p[i].x < p[zero_id].x || p[i].x == p[zero_id].x && p[i].y
< p[zero_id].y)
                        zero_id = i;
        }
        pt zero = p[zero_id];
        rotate (p.begin(), p.begin()+zero_id, p.end());
        p.erase (p.begin());
        --n;
        vector<ang> a (n);
        for (int i=0; i<n; ++i) {
                a[i].a = p[i].y - zero.y;
                a[i].b = p[i].x - zero.x;
                if (a[i].a == 0)
                        a[i].b = a[i].b < 0 ? -1 : 1;
        }
        for (;;) {
                pt q; // очередной запрос
                bool in = false;
                if (q.x >= zero.x)
                        if (q.x == zero.x && q.y == zero.y)
                                in = true;
                        else {
                                ang my = { q.y-zero.y, q.x-zero.x };
                                if (my.a == 0)
                                        my.b = my.b < 0 ? -1 : 1;
                                vector<ang>::iterator it = upper_bound (a.
begin(), a.end(), my);
                                if (it == a.end() && my.a == a[n-1].a && my.
b == a[n-1].b)
                                        it = a.end()-1;
                                if (it != a.end() && it != a.begin()) {
                                        int p1 = int (it - a.begin());
                                        if (sq (p[p1], p[p1-1], q) <= 0)
                                                in = true;
                                }
                        }
                puts (in ? "INSIDE" : "OUTSIDE");
        }
}

Java 해법

자동 초안, 제출 전 검토

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    struct pt {
            int x, y;
    };
    struct ang {
            int a, b;
    };
    boolean operator < (const ang & p, const ang & q) {
            if (p.b == 0 && q.b == 0)
                    return p.a < q.a;
            return p.a * 1ll * q.b < p.b * 1ll * q.a;
    }
    long sq (pt & a, pt & b, pt & c) {
            return a.x*1ll*(b.y-c.y) + b.x*1ll*(c.y-a.y) + c.x*1ll*(a.y-b.y);
    }
    int main() {
            int n;
            cin >> n;
            vector<pt> p (n);
            int zero_id = 0;
            for (int i=0; i<n; ++i) {
                    scanf ("%d%d", &p[i].x, &p[i].y);
                    if (p[i].x < p[zero_id].x || p[i].x == p[zero_id].x && p[i].y
    < p[zero_id].y)
                            zero_id = i;
            }
            pt zero = p[zero_id];
            rotate (p.begin(), p.begin()+zero_id, p.end());
            p.erase (p.begin());
            --n;
            vector<ang> a (n);
            for (int i=0; i<n; ++i) {
                    a[i].a = p[i].y - zero.y;
                    a[i].b = p[i].x - zero.x;
                    if (a[i].a == 0)
                            a[i].b = a[i].b < 0 ? -1 : 1;
            }
            for (;;) {
                    pt q; // очередной запрос
                    boolean in = false;
                    if (q.x >= zero.x)
                            if (q.x == zero.x && q.y == zero.y)
                                    in = true;
                            else {
                                    ang my = { q.y-zero.y, q.x-zero.x };
                                    if (my.a == 0)
                                            my.b = my.b < 0 ? -1 : 1;
                                    vector<ang>::iterator it = upper_bound (a.
    begin(), a.end(), my);
                                    if (it == a.end() && my.a == a[n-1].a && my.
    b == a[n-1].b)
                                            it = a.end()-1;
                                    if (it != a.end() && it != a.begin()) {
                                            int p1 = int (it - a.begin());
                                            if (sq (p[p1], p[p1-1], q) <= 0)
                                                    in = true;
                                    }
                            }
                    puts (in ? "INSIDE" : "OUTSIDE");
            }
    }
}

Материал разбит как 알고리즘ическая 문제: изучить постановку, понять асимптотику и реализовать 알고리즘 на выбранном языке.

Vacancies for this task

활성 채용 with overlapping task tags are 표시됨.

전체 채용

아직 활성 채용이 없습니다.