Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.95/64: Рейтинг темы: голосов - 64, средняя оценка - 4.95
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
1

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

22.07.2016, 10:57. Показов 12930. Ответов 27
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Дано: Прямоугольник, заданный 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 отрицательны - точка внутри четырехугольника
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.07.2016, 10:57
Ответы с готовыми решениями:

Рассчитать координаты описанного прямоугольника внутри которого оказываются все заданные точки
Дан массив точек на плоскости { (x1,y1),(x2,y2)....(xn,yn) }. Рассчитать координаты описанного...

Определить находится ли круг внутри прямоугольника
Прямоугольник задан координатами его вершин (4-х). Определить, принадлежит ли круг с заданным...

Определить лежит ли точка внутри заданного прямоугольника
Даны стороны прямоугольника a и b, Составить программу, определяющую лежит ли точка с координатами...

Классы. Нахождение периметра и площади прямоугольника.
Написал код, но никак не пойму на что оно материться, компилятор пишет о том что он не может...

27
365 / 321 / 219
Регистрация: 21.02.2013
Сообщений: 756
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!!!";
 
}
1
Модератор
Эксперт С++
13507 / 10757 / 6412
Регистрация: 18.12.2011
Сообщений: 28,712
22.07.2016, 12:08 3
jurok_85, а нигде не сказано, что стороны прямоугольника параллельны осям координат!
1
14 / 14 / 5
Регистрация: 16.01.2016
Сообщений: 81
22.07.2016, 12:20 4
по координатам прямоугольника вывести формулы прямых ограничивающих площадь прямоугольника
затем проверить систему уравнений подставив координаты точки.
частный случай параллельные стороны. добавьте угол
1
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
22.07.2016, 12:24  [ТС] 5
а по подробней можно
0
365 / 321 / 219
Регистрация: 21.02.2013
Сообщений: 756
22.07.2016, 13:11 6
Цитата Сообщение от zss Посмотреть сообщение
jurok_85, а нигде не сказано, что стороны прямоугольника параллельны осям координат!
zss, я не силен в тригонометрии, но по моему тут надо угол наклона тогда вычислять и как то потом связывать данные координаты точки и прямоугольника с углом наклона?
1
4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28
22.07.2016, 14:19 7
Можно вылить воду из чайника и свести к предыдущей задаче тривиально триангулировать прямоугольник на 2 треугольника и использовать известный алгоритм принадлежности точки треугольнику.
2
14 / 14 / 5
Регистрация: 16.01.2016
Сообщений: 81
22.07.2016, 16:52 8
Можно и так. А можно использовать y=kx+b и проверять только по b. Чуть позже представлю.
1
14 / 14 / 5
Регистрация: 16.01.2016
Сообщений: 81
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
Миниатюры
Нахождение точки внутри прямоугольника  
1
Эксперт С++
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
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.
1
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
22.07.2016, 23:32  [ТС] 11
Очень интересно! Столько способов решение этой задачи )) Можете по конкретней разъяснить их (по каким теоремам, аксиомам, формулам и т.д.). Я в геометрии не силён но постараюсь осмыслить то что вы будете писать и самое главное мысль объяснить, а то одно дело выучить формулу или теорему которую забудешь на слейдущий день другое дело понять смысл и она будет держаться у тебя в голове всё время ))

Добавлено через 3 минуты
Цитата Сообщение от _Ivana Посмотреть сообщение
Можно вылить воду из чайника и свести к предыдущей задаче тривиально триангулировать прямоугольник на 2 треугольника и использовать известный алгоритм принадлежности точки треугольнику.
можете объяснить алгоритм пренадлежности точки треугольнику?
0
14 / 14 / 5
Регистрация: 16.01.2016
Сообщений: 81
23.07.2016, 17:54 12
Лучший ответ Сообщение было отмечено no swear как решение

Решение

ну тогда самый простой способ для понимания). условимся что треугольник имеет три стороны( обозначим 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-х ТР-ков
сравнение площадей
вывод на экран результата
1
14 / 14 / 5
Регистрация: 16.01.2016
Сообщений: 81
23.07.2016, 18:25 13
Лучший ответ Сообщение было отмечено no swear как решение

Решение

рисунок
Миниатюры
Нахождение точки внутри прямоугольника  
2
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
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-х ТР-ков
сравнение площадей
вывод на экран результата
СПАСИБО большое!!! Всё оказывается ещё проще чем я думал))
0
14 / 14 / 5
Регистрация: 16.01.2016
Сообщений: 81
23.07.2016, 19:16 15
Цитата Сообщение от no swear Посмотреть сообщение
ещё проще
будете реализовывать- не забудьте выложить на обозрение. я тоже только учусь и будет интересно посмотреть код. Параллельно с Вами попробую написать. Главная проблема сейчас, для меня, как передавать в функцию попарно координаты точек. Или реализовать классы, которые будут получать массив и считать длину сторон 1-го треугольника, или писать кучу строк. Но это вопрос уже к Уважаемым мастерам С++.Слежу за темой. Приятного кода всем)
1
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
23.07.2016, 19:29  [ТС] 16
Цитата Сообщение от Андрей Валерьев Посмотреть сообщение
будете реализовывать- не забудьте выложить на обозрение. я тоже только учусь и будет интересно посмотреть код. Параллельно с Вами попробую написать. Главная проблема сейчас, для меня, как передавать в функцию попарно координаты точек. Или реализовать классы, которые будут получать массив и считать длину сторон 1-го треугольника, или писать кучу строк. Но это вопрос уже к Уважаемым мастерам С++.Слежу за темой. Приятного кода всем)
Завтра попробую реализовать на C++.
1
Заблокирован
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");
2
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
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;
}
Вот по твоему методу. Вроде работает.
0
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
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");
Ваш код вообще запускается.
Миниатюры
Нахождение точки внутри прямоугольника  
0
Заблокирован
25.07.2016, 14:52 20
Цитата Сообщение от no swear Посмотреть сообщение
Ваш код вообще запускается.
ну и хорошо что запускается, хотя с точками компилятору было бы понятнее
1
25.07.2016, 14:52
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.07.2016, 14:52
Помогаю со студенческими работами здесь

Нахождение периметра прямоугольника на оси координат
Даны координаты двух противоположных вершин прямоугольника:*(x1,y1), *(x2,y2). Стороны...

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

Затабулировать функцию внутри прямоугольника и области существования данной функции
Затабулировать функцию Z=f(x,y) с шагами x и y внутри прямоугольника и области существования...

Определить точки пересечения круга и прямоугольника
Помогите, пожалуйста!( Даны вещественные числа x1, y1, r, x2, y2, x3, y3....


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru