C++ Входит ли точка в прямоугольник

247

13 марта 2018, 03:05

Не могу решить задачу на C++.

Нам даны координаты точки: x и y.

И даны координаты прямоугольника: x1, y1, x2, y2, x3, y3, x4, y4.

Надо проверить попадает ли точка в прямоугольник. Я сделал так, но как я понял проблема в том, что моя программа не считает некоторые случаи когда на оси координат прямоугольник расположен под углом.

Вввод:

6 6 3 6 6 9 8 7 5 4

13 5 9 2 9 8 12 8 12 2

3 2 2 1 2 3 6 3 6 1

Вывод:

Vhodit

Ne Vhodit

Vhodit

#include <iostream>
using namespace std;
int main()
{
int x,y,x1,y1,x2,y2,x3,y3,x4,y4,rez=0,xcheck=0,ycheck=0,xmax=-50000,ymax=-50000,xmin=50000,ymin=50000,erch=0;
xmax=-50000; ymax=-50000;xmin=50000;ymin=50000;xcheck=0;ycheck=0;erch=0;
x=0;y=0;x1=0;y1=0;x2=0;y2=0;x3=0;y3=0;x4=0;y4=0;
        cin>>x>>y>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
        if(x==0 && y==0 && x1==0 && y1==0 && x2==0 && y2==0 && x3==0 && y3==0 && x4==0 && y4==0){erch+=1;}
        if(x1>xmax){xmax=x1;}
        if(y1>ymax){ymax=y1;}
        if(x2>xmax){xmax=x2;}
        if(y2>ymax){ymax=y2;}
        if(x3>xmax){xmax=x3;}
        if(y3>ymax){ymax=y3;}
        if(x4>xmax){xmax=x4;}
        if(y4>ymax){ymax=y4;}
        if(x1<xmin){xmin=x1;}
        if(y1<ymin){ymin=y1;}
        if(x2<xmin){xmin=x2;}
        if(y2<ymin){ymin=y2;}
        if(x3<xmin){xmin=x3;}
        if(y3<ymin){ymin=y3;}
        if(x4<xmin){xmin=x4;}
        if(y4<ymin){ymin=y4;}
        if(x>=xmin && x<=xmax ){xcheck+=1;}
        if(y>=ymin && y<=ymax){ycheck+=1;}
        if(ycheck==1 && xcheck==1 && erch==0){cout<<"Vhodit"<<endl;return 0;}
cout<<"Ne Vhodit"<<endl;
return 0;
}

Answer 1

Задача уже изначально бессмысленно поставлена.

Произвольный прямоугольник на плоскости однозначно задается координатами трех своих вершин. (И даже это уже избыточно.) В условии же вдруг ни с того ни с сего дано четыре вершины. К чему дана четвертая вершина? А что если заданные точки не образуют прямоугольника вообще? Что тогда делать? Выдавать сообщение об ошибке?

"Лишняя" вершина может быть дана в случаях, когда координаты области являются целочисленными значениями и подвержены ошибкам округления. Тогда, вследствие этих ошибок, рассматриваемая область может оказаться не прямоугольником вообще, а параллелограммом или вообще произвольным четырехугольником. То есть слово "прямоугольник" в такой ситуации из условия задачи выкидываем сразу - это никакой не прямоугольник. И вам и следует решать задачу определения попадания точки в произвольный (выпуклый?) четырехугольник.

Но при этом еще не ясно, в каком порядке перечислены точки. В каком-то направлении обхода? Или вообще вразнобой?

Если гарантируется, что четырехугольник выпукл и точки перечислены в каком-то порядке обхода, то задача решается элементарным образом, путем сравнения знаков произведений

(Bx - Ax) * (Py - Ay) - (By - Ay) * (Px - Ax)

где (Px, Py) - наша точка, а (Ax, Ay)-(Bx, By) - очередная сторона многоугольника, в каком-то фиксированном направлении обхода (например, против часовой стрелки). Если знаки совпадают, то точка лежит внутри. При обходе против часовой стрелки все такие произведения будут положительными, если точка лежит строго внутри. При обходе по часовой стрелке - отрицательными.

Например, для строгого вхождения

#include <iostream>
int product(int Px, int Py, int Ax, int Ay, int Bx, int By)
{
  return (Bx - Ax) * (Py - Ay) - (By - Ay) * (Px - Ax);
}
int main()
{
  int x, y, x1, y1, x2, y2, x3, y3, x4, y4;
  std::cin >> x >> y >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
  int 
    p1 = product(x, y, x1, y1, x2, y2),
    p2 = product(x, y, x2, y2, x3, y3),
    p3 = product(x, y, x3, y3, x4, y4),
    p4 = product(x, y, x4, y4, x1, y1);
  if ((p1 < 0 && p2 < 0 && p3 < 0 && p4 < 0) ||
      (p1 > 0 && p2 > 0 && p3 > 0 && p4 > 0))
    std::cout << "Vhodit" << std::endl;
  else
    std::cout << "Ne vhodit" << std::endl;
}

Но если не гарантируется упорядоченное перечисление точек, то сначала вам самостоятельно придется их упорядочить.

Answer 2

Предлагаю два решения:
1. Повернуть прямоугольник смежными сторонами параллельно осям координат и на соответствующий угол повернуть в координатном пространстве заданную точку. После чего применить простое сравнение диагональных координат с координатами заданной точки (x1 <= x <= x3)&&(y1 <= y <= y3)
2. "Разбить" прямоугольник на два треугольника с общим основанием и проверить вхождение заданной точки в каждый из треугольников. Точка будет принадлежать треугольнику, если будет принадлежать одновременно трем полуплоскостям, пересечение которых и есть треугольник.

(x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0)
(x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0)
(x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0)

Если результаты одинакового знака, то точка внутри треугольника, если что-то из этого - ноль, то точка лежит на стороне, иначе точка вне треугольника.