Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
3 / 3 / 3
Регистрация: 21.03.2011
Сообщений: 55
1

Определить находится ли точка в площади треугольника

11.05.2011, 20:54. Просмотров 2381. Ответов 6
Метки нет (Все метки)

В одномерном массиве с четным количеством элементов находятся координаты N точек плоскости. Они располагаются в следующем порядке: x1 y1, x2 y2, x3 y3 и.т.д. Определить 3 точки являющиеся вершинами треугольника, для которого разность точек вне его и внутри является минимальной.

Совершенно не могу понять как должна реализоваться эта задача. Как проверить принадлежит ли точка площади треугольника?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.05.2011, 20:54
Ответы с готовыми решениями:

С++ использование функций. Определить, находится ли точка М(х,у) внутренней области треугольника
Здравствуйте. помогите написать программу на языке С++. Определить, находится ли точка М(х,у)...

Проверить, находится ли точка внутри, на границе, или за пределами треугольника
Дан треугольник и K точек. Для каждой точки нужно определить, где она находится – внутри, на...

Определить находится ли точка в окружности
Дана окружность с центром С(х0,у0) и радиусом R. Пользователь вводит координаты точки А(х,у)....

Определить, находится ли точка в треугольнике
заданы прямоугольные координаты Х1,У1,Х2,У2,Х3,У3 вершин треугольника и координаты Х и У точки....

6
return (true);
1973 / 1110 / 219
Регистрация: 19.04.2011
Сообщений: 2,345
11.05.2011, 20:59 2
Цитата Сообщение от nick07x Посмотреть сообщение
Как проверить принадлежит ли точка площади треугольника?
Навскидку могу предложить такой вариант:
- вычислить площадь треугольника ABC
- вычислить сумму площадей трёх треугольников ABn, BCn, ACn (n-точка)
- сравнить, если равны, точка внутри
0
3 / 3 / 3
Регистрация: 21.03.2011
Сообщений: 55
24.05.2011, 07:47  [ТС] 3
для 5 точек
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include "stdafx.h"
#include <windows.h>
#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <math.h>
#include <cstdlib>
#include <iostream>
using namespace std;
 
typedef struct tagPoint
{
 double x;
 double y;
}Point, *pPoint;
 
#define LeftOriented  0
#define RightOriented 1
 
 
BOOL CheckOrientation(Point *first, Point *second)
{
 return (first->x*second->y - first->y*second->x)>0; 
}
 
BOOL CheckCollinear(Point *first, Point *second)
{
 return first->x*second->y == first->y*second->x;
}
 
void VectorSubstruct(Point *from, Point *to, Point *res)
{
 res->x = to->x - from->x;
 res->y = to->y - from->y;
}
 
int Check(Point *A, Point *B, Point *C, Point *X)
{
 Point AB, AX; 
 VectorSubstruct(A,B,&AB);
 VectorSubstruct(A,X,&AX);
 if (CheckCollinear(&AB,&AX))
  return 0;
 int orientAB_X = CheckOrientation(&AB,&AX);
  
 Point BC, BX;
 VectorSubstruct(B,C,&BC);
 VectorSubstruct(B,X,&BX);
 if (CheckCollinear(&BC,&BX))
  return 0;
 int orientBC_X = CheckOrientation(&BC,&BX);
  
 Point CA, CX;
 VectorSubstruct(C,A,&CA);
 VectorSubstruct(C,X,&CX);
 
 if (CheckCollinear(&CA,&CX))
  return 0;
 int orientCA_X = CheckOrientation(&CA,&CX);
 
 if (orientAB_X == orientBC_X && orientAB_X == orientCA_X)
  return 1;
 else
  return -1;
}
 
 
BOOL isTriangle(Point *P1, Point *P2, Point *P3)
{
 Point P12, P23; 
 
 if (P1->x == P2->x && P1->y == P2->y ||
   P2->x == P3->x && P2->y == P3->y ||
   P1->x == P3->x && P1->y == P3->y)
   return FALSE; 
 
 VectorSubstruct(P1,P2,&P12);
 VectorSubstruct(P2,P3,&P23);
 return (!CheckCollinear(&P12,&P23)); 
}
 
void main()
{
    setlocale(LC_ALL,"");
 const int N = 5;    
 int   i, j, k, m;   
 int   cOut, cIn;   
 Point   P1, P2, P3, P;  
 int   min, i1, i2, i3; 
int x1,x2,x3,x4,x5,y1,y2,y3,y4,y5;
cout<<"Введите координаты точек"<<endl;
cout<<"x1 = ";
cin>>x1;
cout<<"y1 = ";
cin>>y1;
cout<<"1 точка = "<<"("<<x1<<";"<<y1<<")"<<endl;
cout<<"x2 = ";
cin>>x2;
cout<<"y2 = ";
cin>>y2;
cout<<"2 точка = "<<"("<<x2<<";"<<y2<<")"<<endl;
cout<<"x3 = ";
cin>>x3;
cout<<"y3 = ";
cin>>y3;
cout<<"3 точка = "<<"("<<x3<<";"<<y3<<")"<<endl;
cout<<"x4 = ";
cin>>x4;
cout<<"y4 = ";
cin>>y4;
cout<<"4 точка = "<<"("<<x4<<";"<<y4<<")"<<endl;
cout<<"x5 = ";
cin>>x5;
cout<<"y5 = ";
cin>>y5;
cout<<"5 точка = "<<"("<<x5<<";"<<y5<<")"<<endl;
cout<<endl;
double array[2*N]={x1,y1,x2,y2,x3,y3,x4,y4,x5,y5};
 
 min = N;        
 for (i=0; i<N-2; i++)   
 {
  P1.x = array[i*2]; 
  P1.y = array[i*2+1];   
  for (j=i+1; j<N-1; j++)  
  {
   P2.x = array[j*2]; 
   P2.y = array[j*2+1];  
   for (k=j+1; k<N; k++) 
   {
    P3.x = array[k*2]; 
    P3.y = array[k*2+1];
    if (isTriangle(&P1, &P2, &P3)) 
    {
     cOut = cIn = 0; 
     for (m=0; m<N; m++) 
     {
      if (m!=i && m!=j && m!= k) 
      {
       P.x = array[m*2];
       P.y = array[m*2+1];  
       switch (Check(&P1, &P2, &P3, &P)) 
       {
        case -1:  
         cOut++;
         break;
        case 1:  
         cIn++;
       }    
      }
     }
     if (abs(cOut-cIn) < min) 
     {
      min = abs(cOut-cIn);  
      i1 = i;      
      i2 = j;
      i3 = k;
     }
    }
   }
  }
 }
 
 printf ("минимальная разность  = %d для точек %d, %d, %d", min, i1+1, i2+1, i3+1);
_getch();
}
0
4196 / 1789 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
24.05.2011, 08:11 4
Цитата Сообщение от nick07x Посмотреть сообщение
Определить находится ли точка в площади треугольника
Площадь - это число, в нём ни какие точки находиться не могут.
0
386 / 150 / 16
Регистрация: 12.05.2011
Сообщений: 450
24.05.2011, 10:42 5
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
 
const int n = 3; //Число вершин в треугольнике
 
struct point {  //Точка и координаты.
  double x;
  double y;
};
 
class line {  //Прямая, заданная уравнением F(x,y)=ax+by+c
  double a;
  double b;
  double c;
public:
  line(void) {};
  line(const point &, const point &);
  double F(point A) const;  //Подставляет координаты точки А в уравнение 
                            //и возвращает результат
};
 
line::line(const point & A, const point & B) {
  a = B.y - A.y;
  b = A.x - B.x;
  c = -(a*A.x + b*A.y);
}
 
double line::F(point A) const {
  return (a*A.x + b*A.y + c);
}
 
int main(void) {
  using std::cin;
  using std::cout;
 
  point points[n]; //Массив из точек-вершин треугольника
  cout << "Введите координаты точек:\n";
  for (int i = 0; i < n; ++i) {
    cin >> points[i].x >> points[i].y;
  }
  
  line lines[n]; //Массив прямых-ребер треугольника
  //Ребра создаются по соседним точкам.
  //Но последнее ребро должно создаваться по первой и последней точкам
  for (int i = 0; i < (n-1); ++i) {
    lines[i] = line(points[i], points[i+1]);
  }
  lines[n-1] = line(points[n-1], points[0]);
 
  //Проверяем, не лежат ли точки на одной прямой.
  if (lines[0].F(points[n-1]) == 0) {
    cout << "Точки лежат на одной прямой\n";
    return 0;
  }
  
  cout << "Введите координаты точки:\n";
  point D; //Точка, чью принадлежность треугольнику будем проверять
  while (cin >> D.x && cin >> D.y) {
    bool flag = false; //true - точка лежит вне треугольника и false - если нет
 
    //Проверяем, лежат ли точки C и D по одну сторону от прямой AB
    //В этом случае произведение должно быть положительным
    //или 0 - если D лежит на прямой AB
    if (lines[0].F(D)*lines[0].F(points[n-1]) < 0) {
      flag = true;
    }
    for (int i = 1; i < n; ++i) {
      if (lines[i].F(D)*lines[i].F(points[i-1]) < 0) 
        flag = true;
    }
 
    if (flag) {
      cout << "Точка лежит за пределами треугольника\n";
    } else {
      cout << "Точка лежит внутри треугольника\n";
    }
    
    cout << "Введите координаты точки:\n";
  }
 
  return 0;
}
0
0 / 0 / 0
Регистрация: 20.12.2011
Сообщений: 4
25.12.2011, 10:53 6
Поясните, как работает эта программа. Какой алгоритм она использует?
0
386 / 150 / 16
Регистрация: 12.05.2011
Сообщений: 450
25.12.2011, 11:03 7
читай комментарии
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.12.2011, 11:03

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Определить находится ли точка в закрашенной области
Для заданной области составить такую программу,которая печатает true,если точка с координатами...

Определить и напечатать, находится ли точка в треугольнике
добрый вечер. помогите пожалуйста решить задачи срочно нужно( 1. Треугольник и точка. Заданы...

Определить процедуру вычисления площади треугольника по координатам его вершин
Даны натуральное число n, действительные числа x1, y1, x2, y2,..., xn, yn. Найти площадь n...

Определить процедуру вычисления площади треугольника по координатам его вершин
Даны натуральное число n, действительные числа x1, y1, x2, y2,…, xn,yn. Найти площадь...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.