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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
nick07x
2 / 2 / 0
Регистрация: 21.03.2011
Сообщений: 55
11.05.2011, 20:54     Определить находится ли точка в площади треугольника #1
В одномерном массиве с четным количеством элементов находятся координаты N точек плоскости. Они располагаются в следующем порядке: x1 y1, x2 y2, x3 y3 и.т.д. Определить 3 точки являющиеся вершинами треугольника, для которого разность точек вне его и внутри является минимальной.

Совершенно не могу понять как должна реализоваться эта задача. Как проверить принадлежит ли точка площади треугольника?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.05.2011, 20:54     Определить находится ли точка в площади треугольника
Посмотрите здесь:

C++ Определить процедуру вычисления площади треугольника по координатам его вершин
C++ По заданным координатам определить, где находится точка.
C++ Определить, находится ли точка в треугольнике
C++ Определить и напечатать, находится ли точка в треугольнике
Определить, находится ли точка с координатами (x,y,z) внутри шара C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mimicria
return (true);
 Аватар для mimicria
1956 / 1093 / 91
Регистрация: 19.04.2011
Сообщений: 2,344
11.05.2011, 20:59     Определить находится ли точка в площади треугольника #2
Цитата Сообщение от nick07x Посмотреть сообщение
Как проверить принадлежит ли точка площади треугольника?
Навскидку могу предложить такой вариант:
- вычислить площадь треугольника ABC
- вычислить сумму площадей трёх треугольников ABn, BCn, ACn (n-точка)
- сравнить, если равны, точка внутри
nick07x
2 / 2 / 0
Регистрация: 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();
}
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
24.05.2011, 08:11     Определить находится ли точка в площади треугольника #4
Цитата Сообщение от nick07x Посмотреть сообщение
Определить находится ли точка в площади треугольника
Площадь - это число, в нём ни какие точки находиться не могут.
yekka
384 / 148 / 8
Регистрация: 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;
}
Lothlorien
0 / 0 / 0
Регистрация: 20.12.2011
Сообщений: 4
25.12.2011, 10:53     Определить находится ли точка в площади треугольника #6
Поясните, как работает эта программа. Какой алгоритм она использует?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.12.2011, 11:03     Определить находится ли точка в площади треугольника
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
25.12.2011, 11:03     Определить находится ли точка в площади треугольника #7
читай комментарии
Yandex
Объявления
25.12.2011, 11:03     Определить находится ли точка в площади треугольника
Ответ Создать тему
Опции темы

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