Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
no swear
1 / 1 / 0
Регистрация: 01.07.2016
Сообщений: 76
Завершенные тесты: 1
22.07.2016, 10:57     Нахождение точки внутри прямоугольника #1
Дано: Прямоугольник, заданный 4 точками. Точка заданная координатами. Нужно написать функцию, возращающую Труе\Фалсе на нахождение точки внутри прямоугольника. Я знаю есть формула математическая но я хочу узнать как её вывели
HTML5
1
2
3
4
5
6
7
8
9
10
11
12
dx = x2 - x1
dy = y2 - y1
d1# = ((y1 - Py) * Dx + (Px - x1) * Dy) / (Dy * Dy + Dx * Dx)
dx = x3 - x2
dy = y3 - y2
d2# = ((y2 - Py) * Dx + (Px - x2) * Dy ) / (Dy * Dy + Dx * Dx)
dx = x4 - x3
dy = y4 - y3
d3# = ((y3 - Py) * Dx + (Px - x3) * Dy ) / (Dy * Dy + Dx * Dx)
dx = x1 - x4
dy = y1 - y4
d4# = ((y4 - Py) * Dx + (Px - x4) * Dy ) / (Dy * Dy + Dx * Dx)
Где x1, y1, x2, y2, x3, y3, x4, y4 - координаты точек, образующих четырехугольник, Px, Py - координаты проверяемой точки
если d1, d2, d3, d4 отрицательны - точка внутри четырехугольника
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.07.2016, 10:57     Нахождение точки внутри прямоугольника
Посмотрите здесь:

C++ Классы. Нахождение периметра и площади прямоугольника.
C++ Даны числа x, y, x1, y1, x2, y2. Проверить истинность высказывания: «Точка с координатами (x, y) лежит внутри прямоугольника, левая верхняя вершина ко
Затабулировать функцию внутри прямоугольника и области существования данной функции C++
Определить точки пересечения круга и прямоугольника C++
C++ Даны положительные действительные числа a,b,c,d. Выяснить, можно ли один из прямоугольников целиком поместить внутри другого прямоугольника
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
jurok_85
226 / 209 / 70
Регистрация: 21.02.2013
Сообщений: 494
22.07.2016, 12:06     Нахождение точки внутри прямоугольника #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <stdlib.h>
using namespace std;
 
bool inside(const int&px  , const int&py, const int&ax  , const int&ay, const int&bx  , const int&dy){
    if((px < bx)&&(px > ax)&&(py < dy)&&(py > ay)){
        return true;
    }
    return false;
 
}
int main()
{
    int px  , py;
    cout << "Koordinati tochki x i y: ";
    cin >> px>>py;
 
    int ax, ay, bx, by, cx, cy, dx, dy;
    /*
        D--------------------C
        |                    |
        |                    |
        |                    |
        |                    |
        A--------------------B
    */
 
    cout << "Koordinati prjamougoljnika ax i ay: ";
    cin >> ax>>ay;
    cout << "Koordinati prjamougoljnika bx i by: ";
    cin >> bx>>by;
    cout << "Koordinati prjamougoljnika cx i cy: ";
    cin >> cx>>cy;
    cout << "Koordinati prjamougoljnika dx i dy: ";
    cin >> dx>>dy;
    //(x1-x3)*(y2-y3)-(x2-x3)*(y1-y3);
    if(inside(px,py,ax,ay,bx,dy))
        cout << "Tochka prinadlezit!!!";
 
}
zss
Модератор
Эксперт С++
 Аватар для zss
5953 / 5558 / 1787
Регистрация: 18.12.2011
Сообщений: 14,205
Завершенные тесты: 1
22.07.2016, 12:08     Нахождение точки внутри прямоугольника #3
jurok_85, а нигде не сказано, что стороны прямоугольника параллельны осям координат!
Андрей Валерьев
14 / 14 / 4
Регистрация: 16.01.2016
Сообщений: 55
Завершенные тесты: 2
22.07.2016, 12:20     Нахождение точки внутри прямоугольника #4
по координатам прямоугольника вывести формулы прямых ограничивающих площадь прямоугольника
затем проверить систему уравнений подставив координаты точки.
частный случай параллельные стороны. добавьте угол
no swear
1 / 1 / 0
Регистрация: 01.07.2016
Сообщений: 76
Завершенные тесты: 1
22.07.2016, 12:24  [ТС]     Нахождение точки внутри прямоугольника #5
а по подробней можно
jurok_85
226 / 209 / 70
Регистрация: 21.02.2013
Сообщений: 494
22.07.2016, 13:11     Нахождение точки внутри прямоугольника #6
Цитата Сообщение от zss Посмотреть сообщение
jurok_85, а нигде не сказано, что стороны прямоугольника параллельны осям координат!
zss, я не силен в тригонометрии, но по моему тут надо угол наклона тогда вычислять и как то потом связывать данные координаты точки и прямоугольника с углом наклона?
_Ivana
2191 / 1396 / 124
Регистрация: 01.03.2013
Сообщений: 4,154
Записей в блоге: 2
22.07.2016, 14:19     Нахождение точки внутри прямоугольника #7
Можно вылить воду из чайника и свести к предыдущей задаче тривиально триангулировать прямоугольник на 2 треугольника и использовать известный алгоритм принадлежности точки треугольнику.
Андрей Валерьев
14 / 14 / 4
Регистрация: 16.01.2016
Сообщений: 55
Завершенные тесты: 2
22.07.2016, 16:52     Нахождение точки внутри прямоугольника #8
Можно и так. А можно использовать y=kx+b и проверять только по b. Чуть позже представлю.
Андрей Валерьев
14 / 14 / 4
Регистрация: 16.01.2016
Сообщений: 55
Завершенные тесты: 2
22.07.2016, 17:59     Нахождение точки внутри прямоугольника #9
A,B,C,D вершины прямоугольника( x,y координаты точек)
общее уравнение прямой Y=kX+B или K=(y2-y1)/(x2-x1) например для отрезка АВ А(x1,y1) B(x2,y2)
когда будем знать коэф. К то можем для произвольной точки М получить уравнение прямой с коэф К(параллельной сторонам) Y=Kx-K*x1+y1 через точку М. нас интересует свободный член (К*x1+y1)
как видим на рисунке проверяем свободный член, что меньше чем у верхней прямой и больше нижней стороны.
Аналогично для прямых AD и BC
Миниатюры
Нахождение точки внутри прямоугольника  
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,691
22.07.2016, 18:06     Нахождение точки внутри прямоугольника #10
Мне кажется, самое простое - это через косые произведения векторов (на самом деле годится для любого выпуклого многоугольника).
Пусть вершины прямоугольника в порядке обхода против часовой стрелки - это точки A, B, C, D,
и определяем принадлежность к нему точки P.
По очереди находим косые произведения векторов (PA, PB), (PB, PC), (PC, PD), (PD, PA).
Если хотя бы одно из произведений отрицательно - точка вне прямоугольника.
Косое произведение векторов x и y равно x1*y2 - x2*y1.
no swear
1 / 1 / 0
Регистрация: 01.07.2016
Сообщений: 76
Завершенные тесты: 1
22.07.2016, 23:32  [ТС]     Нахождение точки внутри прямоугольника #11
Очень интересно! Столько способов решение этой задачи )) Можете по конкретней разъяснить их (по каким теоремам, аксиомам, формулам и т.д.). Я в геометрии не силён но постараюсь осмыслить то что вы будете писать и самое главное мысль объяснить, а то одно дело выучить формулу или теорему которую забудешь на слейдущий день другое дело понять смысл и она будет держаться у тебя в голове всё время ))

Добавлено через 3 минуты
Цитата Сообщение от _Ivana Посмотреть сообщение
Можно вылить воду из чайника и свести к предыдущей задаче тривиально триангулировать прямоугольник на 2 треугольника и использовать известный алгоритм принадлежности точки треугольнику.
можете объяснить алгоритм пренадлежности точки треугольнику?
Андрей Валерьев
14 / 14 / 4
Регистрация: 16.01.2016
Сообщений: 55
Завершенные тесты: 2
23.07.2016, 17:54     Нахождение точки внутри прямоугольника #12
Сообщение было отмечено автором темы, экспертом или модератором как ответ
ну тогда самый простой способ для понимания). условимся что треугольник имеет три стороны( обозначим a,b,c). теперь для нахождения площади найдем длину каждой стороны a,b,c. формулу для длины стороны произвольного треугольника найдешь в сети(по координатам длина будет)
АВ=sqrt((x2-x1)^2+(y2-y1)^2)
Площадь для такого треугольника
S=sqrt( p*(p-a)*(p-b)*(p-c))
где p=(a+b+c)/2
так получим площадь треугольника с вершинами A,B,C и длиной сторон a,b,c!
Всё это, как писали выше, необходимо для разбиения на треугольники.
рисуем квадрат с вершинами A,B,C,D. Ставим исследуемую точку М в (допустим) центр прямоугольника. соедини каждую вершину с точкой М. получишь 4 треугольника.(ABM,BCM,CDM,ADM)/
как выше написано находим площади этих 4-х треугольников.
основная мысль такова- если точка в прямоугольнике то сумма площадей треуголок равна площади прямоугольника. а если точка вне него то сумма площадей ТР. будет больше площади прямоугольника)
Самый простой способ для понимания.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
double Dlina(int x1,int x2,int y1,int y2){  // функция выч длины по координатам двух точек
          double Dlin=sqrt(pow((x2-x1),2)+pow((y2-y1),2); // корень суммы квадратов разницы координат))
          return Dlin;
 
}
 
double PLOCHAD( double a, double b, double c){ // функц вычисления площади по длинам сторон треуг.
        double p, s;
        p=(a+b+c)/2;
s=sqrt(p*(p-a)*(p-b)*(p-c))
   
  return s;
 
}
так наметки)). в основном теле какой то цикл создания массива с координатами. также в цикле для каждой пары точек вызываем функцию вычисления длины. затем площадей. и суммируем площади ТР. думаю площадь прямоугл. Вы напишите.

функция Длины
функция Площади

ввод координат от пользователя
вызов Д (8 раз)
вызов П (4 раза)
вычисление площади ПРям-ка
суммирование площадей 4-х ТР-ков
сравнение площадей
вывод на экран результата
Андрей Валерьев
14 / 14 / 4
Регистрация: 16.01.2016
Сообщений: 55
Завершенные тесты: 2
23.07.2016, 18:25     Нахождение точки внутри прямоугольника #13
Сообщение было отмечено автором темы, экспертом или модератором как ответ
рисунок
Миниатюры
Нахождение точки внутри прямоугольника  
no swear
1 / 1 / 0
Регистрация: 01.07.2016
Сообщений: 76
Завершенные тесты: 1
23.07.2016, 18:57  [ТС]     Нахождение точки внутри прямоугольника #14
Цитата Сообщение от Андрей Валерьев Посмотреть сообщение
ну тогда самый простой способ для понимания). условимся что треугольник имеет три стороны( обозначим a,b,c). теперь для нахождения площади найдем длину каждой стороны a,b,c. формулу для длины стороны произвольного треугольника найдешь в сети(по координатам длина будет)
АВ=sqrt((x2-x1)^2+(y2-y1)^2)
Площадь для такого треугольника
S=sqrt( p*(p-a)*(p-b)*(p-c))
где p=(a+b+c)/2
так получим площадь треугольника с вершинами A,B,C и длиной сторон a,b,c!
Всё это, как писали выше, необходимо для разбиения на треугольники.
рисуем квадрат с вершинами A,B,C,D. Ставим исследуемую точку М в (допустим) центр прямоугольника. соедини каждую вершину с точкой М. получишь 4 треугольника.(ABM,BCM,CDM,ADM)/
как выше написано находим площади этих 4-х треугольников.
основная мысль такова- если точка в прямоугольнике то сумма площадей треуголок равна площади прямоугольника. а если точка вне него то сумма площадей ТР. будет больше площади прямоугольника)
Самый простой способ для понимания.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
double Dlina(int x1,int x2,int y1,int y2){  // функция выч длины по координатам двух точек
          double Dlin=sqrt(pow((x2-x1),2)+pow((y2-y1),2); // корень суммы квадратов разницы координат))
          return Dlin;
 
}
 
double PLOCHAD( double a, double b, double c){ // функц вычисления площади по длинам сторон треуг.
        double p, s;
        p=(a+b+c)/2;
s=sqrt(p*(p-a)*(p-b)*(p-c))
   
  return s;
 
}
так наметки)). в основном теле какой то цикл создания массива с координатами. также в цикле для каждой пары точек вызываем функцию вычисления длины. затем площадей. и суммируем площади ТР. думаю площадь прямоугл. Вы напишите.

функция Длины
функция Площади

ввод координат от пользователя
вызов Д (8 раз)
вызов П (4 раза)
вычисление площади ПРям-ка
суммирование площадей 4-х ТР-ков
сравнение площадей
вывод на экран результата
СПАСИБО большое!!! Всё оказывается ещё проще чем я думал))
Андрей Валерьев
14 / 14 / 4
Регистрация: 16.01.2016
Сообщений: 55
Завершенные тесты: 2
23.07.2016, 19:16     Нахождение точки внутри прямоугольника #15
Цитата Сообщение от no swear Посмотреть сообщение
ещё проще
будете реализовывать- не забудьте выложить на обозрение. я тоже только учусь и будет интересно посмотреть код. Параллельно с Вами попробую написать. Главная проблема сейчас, для меня, как передавать в функцию попарно координаты точек. Или реализовать классы, которые будут получать массив и считать длину сторон 1-го треугольника, или писать кучу строк. Но это вопрос уже к Уважаемым мастерам С++.Слежу за темой. Приятного кода всем)
no swear
1 / 1 / 0
Регистрация: 01.07.2016
Сообщений: 76
Завершенные тесты: 1
23.07.2016, 19:29  [ТС]     Нахождение точки внутри прямоугольника #16
Цитата Сообщение от Андрей Валерьев Посмотреть сообщение
будете реализовывать- не забудьте выложить на обозрение. я тоже только учусь и будет интересно посмотреть код. Параллельно с Вами попробую написать. Главная проблема сейчас, для меня, как передавать в функцию попарно координаты точек. Или реализовать классы, которые будут получать массив и считать длину сторон 1-го треугольника, или писать кучу строк. Но это вопрос уже к Уважаемым мастерам С++.Слежу за темой. Приятного кода всем)
Завтра попробую реализовать на C++.
MansMI
Нарушитель
1047 / 844 / 205
Регистрация: 08.01.2012
Сообщений: 3,032
24.07.2016, 11:43     Нахождение точки внутри прямоугольника #17
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
...............
#define _USE_MATH_DEFINES
#include <cmath>
...............
struct point{ double x,y,a; };
void main(int argc,char* argv[])
{
    setlocale(LC_ALL,"Rus");
    point ap[]={{4,1,0},{8,8,0},{2,5,0},{10,4,0}};
    double xmin,xmax,ymin,ymax;
    xmin=xmax=ap[0].x;
    ymin=ymax=ap[0].y;
    for(int i=1; i<4; i++)
    {
        if(xmin>ap[i].x)xmin=ap[i].x;
        if(xmax<ap[i].x)xmax=ap[i].x;
        if(ymin>ap[i].y)ymin=ap[i].y;
        if(ymax<ap[i].y)ymax=ap[i].y;
    }
    double x=(xmax+xmin)/2;
    double y=(ymax+ymin)/2;
    for(int i=0; i<4; i++)
    {
        ap[i].a=atan2(ap[i].y-y,ap[i].x-x);
        if(ap[i].a<0)ap[i].a+=2*M_PI;
    }
    for(int i=3; i; i--)
    for(int j=0; j<i; j++)
        if(ap[j].a>ap[i].a)
        {
            point t=ap[j];
            ap[j]=ap[i];
            ap[i]=t;
        }
    //for(int i=0; i<4; i++) cout<<ap[i].x<<" "<<ap[i].y<<endl;
    cout<<"x y через пробел: ";
    cin>>x>>y;
    bool in=true;
    if(ap[0].y==ap[1].y)
    {
        if(x<ap[1].x || x>ap[0].x || y<ap[2].y || y>ap[0].y) in=false;
    }
    else
    {
        //y=a*x+b
        int i;
        for(i=0; i<2; i++)
        {
            double a=(ap[i].y-ap[i+1].y)/(ap[i].x-ap[i+1].x);
            double b0=ap[i].y-a*ap[i].x;
            double b1=ap[i+2].y-a*ap[i+2].x;
            double b=y-a*x;
            if(b<b0 && b<b1 || b>b0 && b>b1) break;
        }
        if(i<2) in=false;
    }
    cout<<(in?"внутри\n":"снаружи\n");
no swear
1 / 1 / 0
Регистрация: 01.07.2016
Сообщений: 76
Завершенные тесты: 1
25.07.2016, 14:35  [ТС]     Нахождение точки внутри прямоугольника #18
Цитата Сообщение от Андрей Валерьев Посмотреть сообщение
будете реализовывать- не забудьте выложить на обозрение. я тоже только учусь и будет интересно посмотреть код. Параллельно с Вами попробую написать. Главная проблема сейчас, для меня, как передавать в функцию попарно координаты точек. Или реализовать классы, которые будут получать массив и считать длину сторон 1-го треугольника, или писать кучу строк. Но это вопрос уже к Уважаемым мастерам С++.Слежу за темой. Приятного кода всем)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cmath>
 
using namespace std;
 
int main()
{
    int x,x1,x2,x3,x4,y,y1,y2,y3,y4;
    double stt,a,b,att,btt,ctt,ptt,sp,att1,btt1,ctt1,ptt1,stt1,att2,btt2,ctt2,ptt2,stt2,att3,btt3,ctt3,ptt3,stt3;
    cin>>x>>y>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
    b=sqrt(pow(x2-x1,2)+pow(y2-y1,2));
    a=sqrt(pow(x3-x2,2)+pow(y3-y2,2));
    sp=a*b;
    //cout<<a<<" "<<b<<" "<<sp<<endl;
    att=sqrt(pow(x2-x,2)+pow(y2-y,2));
    btt=a;
    ctt=sqrt(pow(x3-x,2)+pow(y3-y,2));
    ptt=(att+btt+ctt)/2;
    stt=sqrt(ptt*(ptt-att)*(ptt-btt)*(ptt-ctt));
    //cout<<att<<" "<<btt<<" "<<ctt<<" "<<ptt<<" "<<stt<<endl;
    att1=ctt;
    btt1=b;
    ctt1=sqrt(pow(x4-x,2)+pow(y4-y,2));
    ptt1=(att1+btt1+ctt1)/2;
    stt1=sqrt(ptt1*(ptt1-att1)*(ptt1-btt1)*(ptt1-ctt1));
    //
    att2=ctt1;
    btt2=a;
    ctt2=sqrt(pow(x1-x,2)+pow(y1-y,2));
    ptt2=(att2+btt2+ctt2)/2;
    stt2=sqrt(ptt2*(ptt2-att2)*(ptt2-btt2)*(ptt2-ctt2));
    //
    att3=ctt2;
    btt3=b;
    ctt3=att;
    ptt3=(att3+btt3+ctt3)/2;
    stt3=sqrt(ptt3*(ptt3-att3)*(ptt3-btt3)*(ptt3-ctt3));
    cout<<stt+stt1+stt2+stt3<<" "<<sp;
}
Вот по твоему методу. Вроде работает.
no swear
1 / 1 / 0
Регистрация: 01.07.2016
Сообщений: 76
Завершенные тесты: 1
25.07.2016, 14:42  [ТС]     Нахождение точки внутри прямоугольника #19
Цитата Сообщение от MansMI Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
...............
#define _USE_MATH_DEFINES
#include <cmath>
...............
struct point{ double x,y,a; };
void main(int argc,char* argv[])
{
    setlocale(LC_ALL,"Rus");
    point ap[]={{4,1,0},{8,8,0},{2,5,0},{10,4,0}};
    double xmin,xmax,ymin,ymax;
    xmin=xmax=ap[0].x;
    ymin=ymax=ap[0].y;
    for(int i=1; i<4; i++)
    {
        if(xmin>ap[i].x)xmin=ap[i].x;
        if(xmax<ap[i].x)xmax=ap[i].x;
        if(ymin>ap[i].y)ymin=ap[i].y;
        if(ymax<ap[i].y)ymax=ap[i].y;
    }
    double x=(xmax+xmin)/2;
    double y=(ymax+ymin)/2;
    for(int i=0; i<4; i++)
    {
        ap[i].a=atan2(ap[i].y-y,ap[i].x-x);
        if(ap[i].a<0)ap[i].a+=2*M_PI;
    }
    for(int i=3; i; i--)
    for(int j=0; j<i; j++)
        if(ap[j].a>ap[i].a)
        {
            point t=ap[j];
            ap[j]=ap[i];
            ap[i]=t;
        }
    //for(int i=0; i<4; i++) cout<<ap[i].x<<" "<<ap[i].y<<endl;
    cout<<"x y через пробел: ";
    cin>>x>>y;
    bool in=true;
    if(ap[0].y==ap[1].y)
    {
        if(x<ap[1].x || x>ap[0].x || y<ap[2].y || y>ap[0].y) in=false;
    }
    else
    {
        //y=a*x+b
        int i;
        for(i=0; i<2; i++)
        {
            double a=(ap[i].y-ap[i+1].y)/(ap[i].x-ap[i+1].x);
            double b0=ap[i].y-a*ap[i].x;
            double b1=ap[i+2].y-a*ap[i+2].x;
            double b=y-a*x;
            if(b<b0 && b<b1 || b>b0 && b>b1) break;
        }
        if(i<2) in=false;
    }
    cout<<(in?"внутри\n":"снаружи\n");
Ваш код вообще запускается.
Миниатюры
Нахождение точки внутри прямоугольника  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.07.2016, 14:52     Нахождение точки внутри прямоугольника
Еще ссылки по теме:

Определить лежит ли точка внутри заданного прямоугольника C++
C++ Вывести сумму координат всех точек внутри прямоугольника
Написать булеву функцию, которая проверяет, имеют ли два прямоугольника общие точки C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
MansMI
Нарушитель
1047 / 844 / 205
Регистрация: 08.01.2012
Сообщений: 3,032
25.07.2016, 14:52     Нахождение точки внутри прямоугольника #20
Цитата Сообщение от no swear Посмотреть сообщение
Ваш код вообще запускается.
ну и хорошо что запускается, хотя с точками компилятору было бы понятнее
Yandex
Объявления
25.07.2016, 14:52     Нахождение точки внутри прямоугольника
Ответ Создать тему
Опции темы

Текущее время: 18:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru