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

Как проверить выпуклость N-угольника? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 33, средняя оценка - 4.94
Qwer_ne_ne_ne
2 / 2 / 0
Регистрация: 06.01.2010
Сообщений: 44
28.05.2010, 04:57     Как проверить выпуклость N-угольника? #1
Доброе время суток
Выпуклый многоугольник задан последовательностью координат своих вершин .Вершины упорядочены Определить, находиться ли точка А внутри многоугольника.

Как проверить и реализовать проверку на выпуклость N-угольника?

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
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <windows.h>
#include "cstdlib"
// Предопределенные функции:
// Длина стороны треуголника
double lenth(double x1, double y1,
         double x2, double y2);
// Площадь треугольника
double sqware(double x1, double y1,
          double x2, double y2,
          double x3, double y3);
// Квадрат числа
double sqr(double x);
 
 
void main(void)
 
{
 
::SetConsoleCP(::GetACP()); //Подключение русского языка
::SetConsoleOutputCP(::GetACP());
 
 int N;
 double epsilon=0.001; // наибольшая погрешность вычисления разности
 puts("\nВведите количество вершин (сторон) многоугольника");
 do {
      scanf("%d", &N);
      if(N>=3) break;
      puts("многоугольник содержит 3 и более сторон!!!");
    } while(1);
 
 double *X=new double[N];
 double *Y=new double[N];
 
 puts("Введите координаты вершин многоугольника");
 for(int i=0; i<N; i++)
 {
  printf("x[%d]=", i); scanf("%lf", &X[i]);
  printf("y[%d]=", i); scanf("%lf", &Y[i]);
 }
 
 double Xa, Ya;
 puts("Введите координаты точки A");
 printf("x_a="); scanf("%lf", &Xa);
 printf("y_a="); scanf("%lf", &Ya);
 
 // Вывод введенных данных
system("cls");
 
 puts("\nЧисло вершин многоугольника:");
 printf("N=%d\n", N);
 puts("Координаты вершин многоугольника:");
 for(i=0; i<N; i++)
 {
  printf("x[%d]=%lf x[%d]=%lf\n", i, X[i], i, Y[i]);
 }
 printf("Точка А(%lf; %lf)\n", Xa, Ya);
 
 int flag=0;
 // Перебор вершин многоугольника
 for(i=1; i<N-1; i++)
 {
   // Находим площадь большого треугольника
   double sbig=sqware(X[0], Y[0], X[i], Y[i], X[i+1], Y[i+1]);
 
   // Находим сумму площадей малых треугольников
   double s=sqware(Xa, Ya, X[0], Y[0], X[i], Y[i])+
        sqware(Xa, Ya, X[0], Y[0], X[i+1], Y[i+1])+
        sqware(Xa, Ya, X[i], Y[i], X[i+1], Y[i+1]);
 
   // Сравниваем площади
   if(fabsl(sbig-s)<=epsilon) {flag=1; break;}
 }
 
 // Вывод результата
 if(flag)
  puts("Точка А лежит ВНУТРИ многоульника");
 else
  puts("Точка А лежит ВНЕ многоугольника");
 
 delete[] X, Y;
 getch();
}
 
// Квадрат числа
double sqr(double x)
{
 return(x*x);
}
 
// Длина отрезка
double lenth(double x1, double y1, double x2, double y2)
{
 return(sqrt(sqr(x1-x2)+sqr(y1-y2)));
}
 
// площадь треугольника по координатам его вершин
double sqware(double x1, double y1, double x2, double y2, double x3, double y3)
{
 double a=lenth(x1, y1, x2, y2),
    b=lenth(x1, y1, x3, y3),
    c=lenth(x2, y2, x3, y3);
 double p=(a+b+c)/2;
 return(sqrt(p*(p-a)*(p-b)*(p-c)));
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.05.2010, 04:57     Как проверить выпуклость N-угольника?
Посмотрите здесь:

C++ площадь n-угольника
C++ Найти площадь 5-угольника, заданного координатами вершин
C++ Даны координаты вершин много угольника
Вычислить длину стороны правильного 48-угольника C++
Написать функцию, которая находит площадь N угольника по его сторонам C++
C++ Найти площадь вписанного в окружность радиуса R неправильного 10-угольника
C++ Найти площадь вписанного в окружность радиуса R неправильного 10-угольника
Координаты n-угольника C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Roma_F
331 / 246 / 5
Регистрация: 13.12.2009
Сообщений: 589
28.05.2010, 10:36     Как проверить выпуклость N-угольника? #2
пройтись по точкам и проверить каждый внутринний угол - < 180 (по 3-м точкам)
определение угла есть здесь
Yandex
Объявления
28.05.2010, 10:36     Как проверить выпуклость N-угольника?
Ответ Создать тему
Опции темы

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