Точка строго внутри четырехугольника

278

30 июля 2017, 09:33

Дан вектор длины 4 точек выпуклого четырехугольника в произвольном порядке, а также произвольная точка P. Необходимо определить, лежит ли эта точка строго внутри четырехугольника. Все найденные мной алгоритмы предполагают, что точки расположены в каком-то порядке и/или могут находится на границе.

struct Point {
   int x, y;
};
bool is_strictly_inside(const Point& P, const std::vector<Point>& points) {
  //
}

Answer 1

Упорядочивание вершин v, чтобы получить выпуклый четырехугольник:

вычисляем 3 z-компоненты векторных произведений i=0..2 [ v[3]-v[i], v[(i+1)%3]-v[i] ] две из них одного знака, одна другого;

выберем индекс той, что отличается, допустим j;

тогда правильный порядок вершин таков: 3,(j+1)%3,(j+2)%3,j.

Составляем новый вектор вершин s. Проверяем 4 z-компоненты векторных произведений i=0..3 [ s[i]-P, s[(i+1)%4]-s[i] ], если они все одного знака или 0, то точка находится внутри или на одной из линий, иначе точка вне четырехугольника

Answer 2

Вот, нашел :)
Лет 25 назад пробегала мимо меня уже древняя к тому времени книжечка типа "Математические алгоритмы на Алгол-68" или что-то типа того, точнее не помню... Некоторые из них я себе на C переписал. Сейчас - "раскопай своих подвалов и шкафов перетряси" (с) - я таки нашел эту реализацию, вдруг пригодится.

int PointInPoly(double x, double y, int n, double* x_poly, double* y_poly)
{
    int b=1,i;
    for(i=0; i<n-1; i++) {
        if ((y<=y_poly[i]) == (y>y_poly[i+1])) {
            if ((x-x_poly[i]) < 
                (y-y_poly[i])*(x_poly[i+1]-x_poly[i])/(y_poly[i+1]-y_poly[i])) b=!b;
        };
    };
    if ((y<=y_poly[n-1]) == (y>y_poly[0])) {
        if ((x-x_poly[n-1]) <
            (y-y_poly[n-1])*(x_poly[0]-x_poly[n-1])/(y_poly[0]-y_poly[n-1])) b=!b;
    };
    return !b;
};