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

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

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

C++ Принадлежность точки к отрезку.
принадлежность точки к кольцу C++
принадлежность точки прямоугольнику C++
принадлежность точки C++
C++ определить принадлежность точки к окружности
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
11.07.2011, 02:11     Принадлежность точки N-угольнику. #2
ограничения по времени есть?

Добавлено через 32 минуты
+ задачу можно решать с разной степенью точности...
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
11.07.2011, 02:13     Принадлежность точки N-угольнику. #3
c или с++?
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
11.07.2011, 03:35     Принадлежность точки N-угольнику. #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  [ТС]     Принадлежность точки N-угольнику. #5
До завтра. С++
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
11.07.2011, 22:43     Принадлежность точки N-угольнику. #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  [ТС]     Принадлежность точки N-угольнику. #7
СЕВЕР, мне это еще защищать. Как-нибудь проще она не решается?
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
13.07.2011, 04:11     Принадлежность точки N-угольнику. #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     Принадлежность точки N-угольнику. #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  [ТС]     Принадлежность точки N-угольнику. #10
Текна, твоя программа прокатила. Всем спасибо за помощь.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.07.2011, 23:45     Принадлежность точки N-угольнику.
Еще ссылки по теме:

Принадлежность точки отрезку C++
C++ Принадлежность точки к фигуре
Принадлежность точки рисунку C++

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

Или воспользуйтесь поиском по форуму:
CEBEP
105 / 105 / 9
Регистрация: 21.03.2010
Сообщений: 437
14.07.2011, 23:45     Принадлежность точки N-угольнику. #11
а говорили что язык с++)))
Yandex
Объявления
14.07.2011, 23:45     Принадлежность точки N-угольнику.
Ответ Создать тему
Опции темы

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