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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
Программист++
1 / 1 / 0
Регистрация: 11.07.2011
Сообщений: 7
#1

Принадлежность точки N-угольнику. - C++

11.07.2011, 00:40. Просмотров 1365. Ответов 10
Метки нет (Все метки)

Ребята, помогите, ПОЖАЛУЙСТА.
На плоскости задается выпуклый N - угольник целочисленными координатами своих вершин в порядке обхода по контуру. Вводятся координаты точки (Х,У). Определить: а) является ли он вершиной N-угольника;б)принадлежит ли она N - угольнику.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2011, 00:40
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Принадлежность точки N-угольнику. (C++):

принадлежность точки - C++
Нужно проверить принадлежность точки заштрихованной области. Не пойму как задавать, точнее что писать в ифе. Кто бы помог мне или...

принадлежность точки прямоугольнику - C++
Задача: определить,принадлежит ли точка прямоугольнику. Заданы координаты точки и вершин прямоугольника. Прямоугольник может располагаться...

Принадлежность точки фигуре - C++
Понять не могу почему не работает так как требуется. Хотя на код смотрю вроде всё верно. Может просто не вижу ошибку. Суть задания:...

Принадлежность точки к фигуре - C++
Добрый вечер. Задача: написать программу, создающую 4 рандомных координаты(x,y) и проверяющую принадлежность точки к фигуре(точки фигуры...

Принадлежность точки рисунку - C++
Разработать алгоритм и написать программу вычисления принадлежности точки с заданными координатами (x, y) заштрихованной об-ласти....

Принадлежность точки прямоугольнику - C++
написать функцию для проверки принадлежности точки с координатами (x,y) прямоугольнику x

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
11.07.2011, 02:11 #2
ограничения по времени есть?

Добавлено через 32 минуты
+ задачу можно решать с разной степенью точности...
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
11.07.2011, 02:13 #3
c или с++?
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
11.07.2011, 03:35 #4
и вообще, задачку можно расписать на курчач и решить круто а можно за 8 минут решить но хреново

Добавлено через 1 час 19 минут
короче, я что-то написал, потом надоело...
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
#include <iostream>
#include <vector>
 
class Point
{
    double x, y;
 
public:
    Point(): x(0.), y(0.) {   }
    Point(double X, double Y): x(X), y(Y) {   }
    Point(const Point& p): x(p.x), y(p.y) {   }
 
    double X () const {return x;}
    double Y () const {return y;}
 
    bool operator == (const Point& p) const { return p.x == x && p.y == y; }
    void operator = (const Point& p) { x = p.x; y = p.y; }
};
 
class Polyline
{
    std::vector<Point> vertex;
    void swap(Point segment[2])
    {
        if(segment[0].X() > segment[1].X())
        {
            Point p = segment[0];
            segment[0] = segment[1];
            segment[1] = p;
        }
    }
public:
    Polyline() {   }
    void addVertex(const Point& p) { vertex.push_back(p); }
 
    bool isVertex(const Point& p)
    {
        for(std::vector<Point>::const_iterator it = vertex.begin(), end = vertex.end(); it != end; ++it)
            if(*it == p)
                return true;
        return false;
    }
 
 
    bool onPlant(const Point& p)
    {
        /*Идея такая, если в полиноме найдутся два ребра, одно из которых выше точки, а другое ниже - точка наша!*/
        Point segment[2];
        segment[0] = *vertex.begin();
        segment[1] = *(vertex.end() - 1);
        swap(segment);
        bool under = false,
             on = false;
        if(segment[0].X() > p.X() || segment[1].X() < p.X() && segment[1].X() != segment[0].X() )
        {
            under = p.Y() + p.Y() < ( segment[0].X() - p.X() ) * ( segment[1].Y() - segment[0].Y() ) / ( segment[1].X() - segment[0].X() );
            on    = p.Y() + p.Y() > ( segment[0].X() - p.X() ) * ( segment[1].Y() - segment[0].Y() ) / ( segment[1].X() - segment[0].X() );
        }
 
        for(std::vector<Point>::const_iterator it = vertex.begin(), end = vertex.end() - 1; it != end; ++it)
        {
            segment[0] = *it;
            segment[1] = *(it + 1);
            swap(segment);
            if(segment[0].X() > p.X() || segment[1].X() < p.X() && segment[1].X() != segment[0].X() )
            {
                if(!under)
                    under = p.Y() < p.Y() + ( p.X() - segment[0].X() ) * ( segment[1].Y() - segment[0].Y() ) / ( segment[1].X() - segment[0].X() );
                if(!on)
                    on    = p.Y() > p.Y() + ( p.X() - segment[0].X() ) * ( segment[1].Y() - segment[0].Y() ) / ( segment[1].X() - segment[0].X() );
            }
        }
        return under && on;
    }
};
std::istream& operator >> (std::istream& cin, Point p)
{
    double m[2];
    cin >> m[0] >> m[1];
    p = Point(m[0],m[1]);
    return cin;
}
 
int main()
{
    setlocale( LC_ALL, "Russian" );
    Polyline polyline;
    Point p;
    std::cout << "Введите количество вершин: ";
    unsigned size;
    std::cin >> size;
    for(unsigned i = 0; i != size; ++i)
    {
        std::cout << i + 1 << ": ";
        std::cin >> p;
        polyline.addVertex(p);
    }
    std::cout << "Введите координаты проверяемой точки: ";
    std::cin >> p;
    std::cout << polyline.isVertex(p) ? "Это вершина многоугольника.\n" : "";
    std::cout << polyline.onPlant(p) ? "Точка лежит внутри многоугольника" : "Точка лежит вне многоугольника.";
}
Программист++
1 / 1 / 0
Регистрация: 11.07.2011
Сообщений: 7
11.07.2011, 22:25  [ТС] #5
До завтра. С++
Somebody
2788 / 1602 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 1
11.07.2011, 22:43 #6
Если
http://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
\left(x_1-x_0\right)\cdot\left(y_2-y_1\right)-\left(x_2-x_1\right)\cdot\left(y_1-y_0\right)\\<br />
...<br />
\left(x_{n-1}-x_0\right)\cdot\left(y_n-y_{n-1}\right)-\left(x_n-x_{n-1}\right)\cdot\left(y_{n-1}-y_0\right)\\<br />
\left(x_n-x_0\right)\cdot\left(y_1-y_n\right)-\left(x_1-x_n\right)\cdot\left(y_n-y_0\right)<br />
все одного знака, то внутри. Если есть ноль - на границе, разных - снаружи.
Программист++
1 / 1 / 0
Регистрация: 11.07.2011
Сообщений: 7
13.07.2011, 02:38  [ТС] #7
СЕВЕР, мне это еще защищать. Как-нибудь проще она не решается?
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
13.07.2011, 04:11 #8
ну если писать на с++ то это пожалуй я максимально упростил но в решении многое для стиля... можно перевести это всё в форму "ввод - анализ - вывод"... но это будет то на что преподы любят ругаться и гнать что это не с++

Добавлено через 19 минут
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
#include <iostream>
#include <vector>
/*
Структура программы:
Определён класс точки (Point), для него определены все основные понятия, позволяющие работать с ним как с обычной переменной,
std::istream& operator >> (std::istream& cin, Point& p)
и
std::ostream& operator << (std::ostream& cout, const Point& p)
определены чтобы std::cout и std::cin работали с определённым классом. Далее более простой и урезаный класс многоугольника (Polyline),
можно придраться к названию, но это уже издевательство. В нём определён только сам вектор, конструктор по умолчанию, который ничего не делает,
метод добавления вершин в многоугольник, приватная функция swap используемая методом onPlant, и собственно методы isVertex, проверяющие,
евляется ли аргумет вершиной многоугольника и onPlant, определяющий, лежит ли точка внутри многоугольника.
 
Сильно упростило бы программу неиспользование, сажем, векторов, но какой это тогда с++?
 
Кроме того, я сохранил в виде коментариев отладочную печать... если потратить полчаса, уверен, можно разобраться в том что делает программа.
*/
class Point
{
    double x, y;
 
public:
    Point(): x(0.), y(0.) {   }
    Point(double X, double Y): x(X), y(Y) {   }
    Point(const Point& p): x(p.x), y(p.y) {   }
 
    double X () const {return x;}
    double Y () const {return y;}
 
    bool operator == (const Point& p) const { return p.x == x && p.y == y; }
    void operator = (const Point& p) { x = p.x; y = p.y; }
};
std::istream& operator >> (std::istream& cin, Point& p)
{
    double m[2];
    cin >> m[0] >> m[1];
    p = Point(m[0],m[1]);
    return cin;
}
std::ostream& operator << (std::ostream& cout, const Point& p)
{
    cout << '(' << p.X() << ',' << p.Y() << ')';
    return cout;
}
 
class Polyline
{
    std::vector<Point> vertex;
    void swap(Point segment[2])
    {
        if(segment[0].X() > segment[1].X())
        {
            Point p = segment[0];
            segment[0] = segment[1];
            segment[1] = p;
        }
    }
 
public:
    Polyline() {   }
    void addVertex(const Point& p) { vertex.push_back(p); }
 
    bool isVertex(const Point& p)
    {
        for(std::vector<Point>::const_iterator it = vertex.begin(), end = vertex.end(); it != end; ++it)
            if(*it == p)
                return true;
        return false;
    }
 
 
    bool onPlant(const Point& p)
    {
        /*Идея такая, если в полиноме найдутся два ребра, одно из которых выше точки, а другое ниже - точка наша!*/
        Point segment[2];
        segment[0] = *vertex.begin();
        segment[1] = *(vertex.end() - 1);
        swap(segment);
        bool under = false,
             on = false;
        if(segment[0].X() <= p.X() && segment[1].X() >= p.X() && segment[1].X() != segment[0].X() )
        {
            under = p.Y() <= p.Y() + ( segment[0].X() - p.X() ) * ( segment[1].Y() - segment[0].Y() ) / ( segment[1].X() - segment[0].X() );
            on    = p.Y() >  p.Y() + ( segment[0].X() - p.X() ) * ( segment[1].Y() - segment[0].Y() ) / ( segment[1].X() - segment[0].X() );
            //std::cout << "Отрезок " << segment[0] << " - " << segment[1] << " определил " << on << ' ' << under << std::endl;
        }
        //else
            //std::cout << "Отрезок " << segment[0] << " - " << segment[1] << " не принят." << std::endl;
 
        for(std::vector<Point>::const_iterator it = vertex.begin(), end = vertex.end() - 1; it != end; ++it)
        {
            segment[0] = *it;
            segment[1] = *(it + 1);
            swap(segment);
            if(segment[0].X() <= p.X() && segment[1].X() >= p.X() && segment[1].X() != segment[0].X() )
            {
                if(!under)
                    under = p.Y() <= p.Y() + ( segment[0].X() - p.X() ) * ( segment[1].Y() - segment[0].Y() ) / ( segment[1].X() - segment[0].X() );
                if(!on)
                    on    = p.Y() >  p.Y() + ( segment[0].X() - p.X() ) * ( segment[1].Y() - segment[0].Y() ) / ( segment[1].X() - segment[0].X() );
                //std::cout << "Отрезок " << segment[0] << " - " << segment[1] << " определил " << on << ' ' << under << std::endl;
            }
            //else
                //std::cout << "Отрезок " << segment[0] << " - " << segment[1] << " не принят." << std::endl;
        }
        return under && on;
    }
};
 
int main()
{
    setlocale( LC_ALL, "Russian" );
    Polyline polyline;
    Point p;
    std::cout << "Введите количество вершин: ";
    unsigned size;
    std::cin >> size;
    for(unsigned i = 0; i != size; ++i)
    {
        std::cout << i + 1 << ": ";
        std::cin >> p;
        polyline.addVertex(p);
    }
    std::cout << std::boolalpha;
    std::cout << "Введите координаты проверяемой точки: ";
    std::cin >> p;
    if(polyline.isVertex(p))
        std::cout << "Это вершина многоугольника.\n";
    else if(polyline.onPlant(p))
        std::cout << "Точка лежит внутри многоугольника.\n";
    else
        std::cout << "Точка лежит вне многоугольника.\n";
}
вот тот же код только доведённый до ума,в начале присутствует комментарий, призванный помочь вам на защите.
Текна
3 / 3 / 1
Регистрация: 15.02.2011
Сообщений: 5
13.07.2011, 16:48 #9
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
#include <iostream.h>
#include <conio.h>
#include <math.h>
void main()
{clrscr();
int a[50];
int b[50];
int n,i,j,x,y,max1,max2,p,k,r;
cout <<"Vvedite kol-vo uglov: "; cin >>n;
cout <<"Vvedite koordinati vershin. Snachala x, potom y";
for(i=0;i<n;i++) cin>>a[i];
for(i=0;i<n;i++) cin>>b[i];
cout <<"Vvedite koordinati tocki(x,y): ";
cin>>x>>y;
for (i=0; i<n;i++) if (a[i]==x && b[i]==y) cout <<"Zadannaya tochka yavlyaetsya vershinoi "<<n<<"-ugolnika";
max1=a[0];
for (i=1;i<n;i++)  if (a[i]>max1) max1=a[i];
max2=a[0];
for (i=1;i<n;i++)  if (a[i]>max1 && a[i]!=max2) max2=a[i];
k=0;
for (i=x;x<max1;i++)
{for (j=0;j<n;j++)
if (j==n-1) {p=(a[1]-i)/(a[1]-a[j]);r=p*b[j]+(1-p)*b[1];}
else {p=(a[j+1]-i)/(a[j+1]-a[j]);r=p*b[j]+(1-p)*b[j+1];}
if(r==y) k++;}
if (k==1 ) cout <<"Zadannaya tochka prinadlejit "<<n<<"-ugolniku";
else cout <<"Zadannaya tochka prinadlejit "<<n<<"-ugolniku";
}

Я сделала так, только виснет. Не пойму почему.

 Комментарий модератора 
Используйте теги форматирования кода!
Программист++
1 / 1 / 0
Регистрация: 11.07.2011
Сообщений: 7
14.07.2011, 23:43  [ТС] #10
Текна, твоя программа прокатила. Всем спасибо за помощь.
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
14.07.2011, 23:45 #11
а говорили что язык с++)))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.07.2011, 23:45
Привет! Вот еще темы с ответами:

принадлежность точки к кольцу - C++
#include &lt;iostream&gt; #include &lt;math.h&gt; using namespace std; void main() { // Объявление переменных int x0, y0, r1, r2, x, y;...

Принадлежность точки к отрезку. - C++
УВАЖАЕМЫЕ ЭКСПЕРТЫ ПОМОГИТЕ УЛУЧшИТЬ АЛГОРИТМ ДЛЯ ДАННОЙ ЗАДАЧИ.... Точки и отрезки (Время: 2 сек) Дано N отрезков на числовой прямой...

Принадлежность точки фигуре - C++
Программа для проверки, принадлежит ли точка с координатами (x, y) в заданной области Объясните, пожалуйста алгоритм. Заранее...

Принадлежность точки отрезку - C++
Добрый день, уважаемые форумчане. Помогите пожалуйста с задачей. В первой строке задано два целых числа n и m (1≤n≤50000, 1≤m≤50000) —...


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

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

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