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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
nick07x
2 / 2 / 0
Регистрация: 21.03.2011
Сообщений: 55
#1

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

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

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

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

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

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

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

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

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

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

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

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

По заданным координатам определить, где находится точка. - C++
Т.к. я полный 0 в С++, прошу помощи у профи) Завтра зачет. По заданным координатам точки определить, где находится точка: 1) внутри...

Определить, находится ли точка с координатами (x,y,z) внутри шара - C++
Определить, находится ли точка с координатами (x,y,z) внутри шара с центром в точке (x_0,y_0,z_0 )и радиусом R.

Определить, находится ли точка с пространственными координатами внутри параллелепипеда - C++
Реализовать программу, определяющую находится ли точка с пространственными координатами (х, у, z) внутри параллелепипеда с заданными...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
25.12.2011, 11:03
Ответ Создать тему
Опции темы

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