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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.92
kosmosnsk
0 / 0 / 0
Регистрация: 21.05.2010
Сообщений: 10
#1

Выпуклые многоугольники - C++

21.05.2010, 16:21. Просмотров 3360. Ответов 18
Метки нет (Все метки)

Два выпуклых многоугольника заданы на плоскости перечислением координат вершин в порядке обхода границы. Проверить лежит ли один из них строго внутри другого и определить площади многоугольников.

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

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

Наследование: точки, линии, многоугольники - C++
Доброго вечера! Имеется следующие задание: Создать класс Point (точка). На его основе создать классы ColoredPoint и Line (линия). На...

Создать класс, строящий правильные многоугольники - C++
Здравствуйте. Cоздать класс, строящий правильные многоугольники. struct Regular_polygon : Closed_polyline //...

Выпуклые четырехугольники - Pascal ABC
Построить множество всех различных выпуклых четырехугольников с вершинами в заданном множестве точек на плоскости. Добавлено через 15...

Выпуклые кнопки на ToolBar. - Delphi
Есть ли возможность на тулбаре сделать выпуклые кнопки? Ибо они по умолчанию не имеют границ, и если не поставить картинку на кнопку, то их...

Выпуклые кнопки в Delphi - Delphi
Хочу сделать такие же выпуклые кнопки, как на картинке, а еще при наведении курсора они становятся светлей. Помогите сотворить такие...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
21.05.2010, 18:09 #2
Что первое пришло в голову - так это искать точки пересечения сторон, т.е. берём первую сторону одного многоугольника и ищем её пересечения со всеми сторонами второго. Не нашли пересечений - берём вторую сторону первого многоугольника и опять ищем пересечения со всеми сторонами второго. Если проверили все стороны первого многоугольника, а пересечений не нашли - второй лежит строго внутри первого. Если во время поисков нашли пересечение - сразу выходим. Повторюсь, это сразу в голову пришло, насколько я могу судить, алгоритм относительно долгий, думаю, должен быть быстрее. Но можно пока попробовать так...
kosmosnsk
0 / 0 / 0
Регистрация: 21.05.2010
Сообщений: 10
21.05.2010, 19:09  [ТС] #3
Цитата Сообщение от silent_1991 Посмотреть сообщение
искать точки пересечения сторон, т.е. берём первую сторону одного многоугольника и ищем её пересечения со всеми сторонами второго
алгоритм я понял! только в Си я толком ниче не знаю, можно подробнее объяснить как это будет выглядить? как вообще найти пересечение?
Roma_F
331 / 246 / 5
Регистрация: 13.12.2009
Сообщений: 589
21.05.2010, 19:17 #4
Цитата Сообщение от silent_1991 Посмотреть сообщение
Если проверили все стороны первого многоугольника, а пересечений не нашли - второй лежит строго внутри первого.
или они лежат рядом

предлагаю проверить лежат ли все точки одного многоугольника в другом
алгоритм точки в многоугольнике
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
21.05.2010, 19:48 #5
Roma_F,
Да, это будет разумнее. Просто мне кажется, что алгоритм проверки пересечения двух прямых проще... А для исключения случая, когда они лежат рядом, нужно ввести дополнительное условие сравнения координат.
kosmosnsk
0 / 0 / 0
Регистрация: 21.05.2010
Сообщений: 10
21.05.2010, 19:52  [ТС] #6
Цитата Сообщение от Roma_F Посмотреть сообщение
предлагаю проверить лежат ли все точки одного многоугольника в другом
т.е. тот код послать в цикл по условию начиная с первой вершины одного многоугольника и до (n-1)? и если флаги все будут положительными, то вывести ответ что лежит строго внутри... правильно мысль твою понял?


silent_1991 можешь привести пример кода? я что то вообще не понимаю как это выглядить должно((
Roma_F
331 / 246 / 5
Регистрация: 13.12.2009
Сообщений: 589
21.05.2010, 20:42 #7
пересечение отрезков

Цитата Сообщение от kosmosnsk Посмотреть сообщение
правильно мысль твою понял?
правильно
kosmosnsk
0 / 0 / 0
Регистрация: 21.05.2010
Сообщений: 10
23.05.2010, 15:21  [ТС] #8
Цитата Сообщение от Roma_F Посмотреть сообщение
предлагаю проверить лежат ли все точки одного многоугольника в другом
алгоритм точки в многоугольнике
сделал методом "подсчёта количества пересечений луча, исходящего из данной точки в направлении горизонтальной оси" ... но что-то не то((( по какому условию выводить результат то? я сделал как написано там "Если оно чётное, точка не принадлежит многоугольнику"... но получается если многоугольники вообще не рядом находятся, то ответ выводит как будто один внутри другого...
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
23.05.2010, 17:32 #9
Что в вашем понимании означает "Вообще не рядом"?
Суть метода в том, что надо проверить все точки одного многоугольника для другого, и если для каждой точки вы найдёте, что она лежит в многоугольнике - значит и многоугольник, образованный этими точками, лежит в этом многоугольнике (логично, а?) Причём, думаю, стоит проверить принадлежность одного многоугольника второму для каждого из двух данных многоугольников, т.к. если первый не лежит во втором, может быть так, что второй лежит в первом.

Добавлено через 7 минут
А вообще, я бы делал с помощью самой первой функции на той странице, т.е. IsPointInsidePolygon. Мне кажется она нагляднее, да и работать с ней проще.

Добавлено через 17 минут
И дайте ваш код))
kosmosnsk
0 / 0 / 0
Регистрация: 21.05.2010
Сообщений: 10
23.05.2010, 18:47  [ТС] #10
Цитата Сообщение от silent_1991 Посмотреть сообщение
Что в вашем понимании означает "Вообще не рядом"?
ну т.е. один где нибудь слева, а другой где нибдь справа...
суть то я понял...
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
#include <iostream.h>
#include <conio.h>
#include <math.h>
#include <graphics.h>
int x[100];
int y[100];
int u[100];
int s[100];
 
int main()
{
 
// ---------------------------------------
  int gd=DETECT, gm;
  initgraph(&gd, &gm, "C:\Tc\BGI");
 
// ---------------------------------------
 
    clrscr();
    int c, t, i, f, xp, yp, sp, up;
    long s1, s2, res1 = 0, res2 = 0, sq1 = 0, sq2 =0;
 
    cout << "BBeguTe 4ucJIo BepLLIuH nePBoro MHoroyroJIbHuKa:" << endl;
    cin >> n;
 
    cout << "BBeguTe KoopguHaTbI nePBoro MHoroyroJIbHuKa:" << endl;
    for (i = 0; i < n; i++) {
      cin >> x[i]; // координата x
      cin >> y[i]; // координата y
    }
 
cout << "BBeguTe 4ucJIo BepLLIuH BToporo MHoroyroJIbHuKa:" << endl;
    cin >> z;
 
    cout << "BBeguTe KoopguHaTbI BToporo MHoroyroJIbHuKa:" << endl;
    for (i = 0; i < z; i++) {
      cin >> u[i]; // координата x
      cin >> s[i]; // координата y
    }
 
 
    // построение на экране первого многоугольника
 
for (i = 0; i < n; i++) {
      circle (x[i] + 150, y[i] + 150, 2);
      if (i == n - 1) {
         i = 0;
         line (x[i] + 150, y[i] + 150, x[n-1] + 150, y[n-1] + 150);
         break;
      }
      line (x[i] + 150, y[i] + 150, x[i+1] + 150, y[i+1] + 150);
    }
 
 
// построение на экране второго многоугольника
 
    for (i = 0; i < z; i++) {
      circle (u[i] + 150, s[i] + 150, 2);
      if (i == z - 1) {
         i = 0;
         line (u[i] + 150, s[i] + 150, u[z-1] + 150, s[z-1] + 150);
         break;
      }
      line (u[i] + 150, s[i] + 150, u[i+1] + 150, s[i+1] + 150);
    }
 
    // Расчет площади первого многоугольника через сумму площадей трапеций
 
    for (i = 0; i < n; i++) {
      if (i == 0) {
         s1 = x[i]*(y[n-1] - y[i+1]); //если i == 0, то y[i-1] заменяем на y[n-1]
         res1 += s1;
      }
      else
         if (i == n-1) {
     s1 = x[i]*(y[i-1] - y[0]); // если i == n-1, то y[i+1] заменяем на y[0]
     res1 += s1;
         }
      else {
         s1 = x[i]*(y[i-1] - y[i+1]);
         res1 += s1;
      }
    }
 
 // Расчет площади второго многоугольника через сумму площадей трапеций
 
    for (i = 0; i < z; i++) {
      if (i == 0) {
         s2 = u[i]*(s[z-1] - s[i+1]); //если i == 0, то y[i-1] заменяем на y[z-1]
         res2 += s2;
      }
      else
         if (i == z-1) {
     s2 = u[i]*(s[i-1] - s[0]); // если i == z-1, то y[i+1] заменяем на y[0]
     res2 += s2;
         }
      else {
         s2 = u[i]*(s[i-1] - s[i+1]);
         res2 += s2;
      }
    }
 
sq1 = abs(res1/2);
    sq2 = abs(res2/2);
    cout << "-------------" << endl;
    cout << "nJIoLLLagb nepBoro PaBHa: " <<sq1<<endl;
    cout << "-------------" << endl;
    cout << "nJIoLLLagb BToporo PaBHa: " <<sq2<<endl;
    cout<< "c="<<c<<"  t="<<t<<endl;
    getch();
    closegraph();
    return 0;
}
вот мой код... тут немного не убрал лишнего, после того как пытался поставить ту функцию
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
23.05.2010, 18:50 #11
Эээээ... а где, собственно, само определение принадлежности всех точек одного многоугольника другому?
kosmosnsk
0 / 0 / 0
Регистрация: 21.05.2010
Сообщений: 10
23.05.2010, 18:54  [ТС] #12
вставлял вот это...

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int tochka(int xp, int yp, int sp, int up, int c, int t)
 {
    c=0;
    t=0;
    for (int i = 0, j = n - 1; i < n; j = i++)
    {
      if ((((y[i]<=yp) && (yp<y[j])) || ((y[j]<=yp) && (yp<y[i]))) &&
         (xp > (x[j] - x[i]) * (yp - y[i]) / (y[j] - y[i]) + x[i]))
             c++;
    }
 
// ------------------------------
 
 for (int l = 0, v = z - 1; l < z; v = l++)
    {
      if ((((s[l]<=sp) && (sp<s[v])) || ((s[v]<=sp) && (sp<s[l]))) &&
         (up > (u[v] - u[l]) * (sp - s[l]) / (s[v] - s[l]) + u[l]))
             t++;
    }
 
  return 0;
 
 }

и в главную функцию добавлял это...

C
1
2
3
4
 for (int q=0;q<n;q++)
    {
 tochka(xp, yp, sp, up, c, t);
  }
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
23.05.2010, 19:01 #13
И чего вы этим пытаетесь добиться? Вероятно, пытаетесь в функции менять значения c и t? Тогда их нужно передавать в функцию по ссылке или через указатель, иначе вы меняете не сами переменные, а их копии, созданные специально для использования внутри функции tochka и уничтожаемые при выходе из неё.
И ещё, я бы написал функцию проверки для одного многоугольника, а потом вызвал её в основной программе два раза, это и код сэкономит, и нагляднее будет.

Добавлено через 52 секунды
В общем сейчас набросаю, как примерно это должно выглядеть...
kosmosnsk
0 / 0 / 0
Регистрация: 21.05.2010
Сообщений: 10
23.05.2010, 19:15  [ТС] #14
Цитата Сообщение от silent_1991 Посмотреть сообщение
Вероятно, пытаетесь в функции менять значения c и t
этим я пытался посчитать сколько раз луч пересекает сторону... а две переменные делал для того чтобы проверять оба многоугольника по отношению друг к другу... сначала один, потом второй

еще вставлял вот это в конец кода главной функции...
C
1
2
3
4
5
6
7
if (c%2!=0)
    cout<<"MHoroyroJIbHuK JIe}I{uT CTporo BHyTPu gpyroro"<<endl;
    else {
          if (t%2!=0)
          cout<<"MHoroyroJIbHuK JIe}I{uT CTporo BHyTPu gpyroro"<<endl;
             else cout<<"nePeceKa10Tc9"<<endl;
          }
silent_1991
Эксперт С++
4963 / 3039 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
23.05.2010, 19:22 #15
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
167
168
169
170
171
172
173
#include <iostream.h>
#include <conio.h>
#include <math.h>
#include <graphics.h>
 
int x[100];
int y[100];
int u[100];
int s[100];
 
int pnpoly(int npol, int *xp, int *yp, int x, int y)
{
    int c = 0;
 
    for (int i = 0, j = npol - 1; i < npol; j = i++)
    {
        if ((((yp[i] <= y) && (y < yp[j])) || ((yp[j] <= y) && (y < yp[i]))) &&
            (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
            c = !c;
    }
 
    return c;
}
 
int main()
{
 
    // ---------------------------------------
    int gd = DETECT, gm;
    initgraph(&gd, &gm, "C:\Tc\BGI");
 
    // ---------------------------------------
 
    clrscr();
    int c, t, i, f, xp, yp, sp, up, n, z;
    long s1, s2, res1 = 0, res2 = 0, sq1 = 0, sq2 = 0;
 
    cout << "BBeguTe 4ucJIo BepLLIuH nePBoro MHoroyroJIbHuKa:" << endl;
    cin >> n;
 
    cout << "BBeguTe KoopguHaTbI nePBoro MHoroyroJIbHuKa:" << endl;
    for (i = 0; i < n; i++)
    {
        cin >> x[i]; // координата x
        cin >> y[i]; // координата y
    }
 
    cout << "BBeguTe 4ucJIo BepLLIuH BToporo MHoroyroJIbHuKa:" << endl;
    cin >> z;
 
    cout << "BBeguTe KoopguHaTbI BToporo MHoroyroJIbHuKa:" << endl;
    for (i = 0; i < z; i++)
    {
        cin >> u[i]; // координата x
        cin >> s[i]; // координата y
    }
 
    // построение на экране первого многоугольника
 
    for (i = 0; i < n; i++)
    {
        circle(x[i] + 150, y[i] + 150, 2);
        if (i == n - 1)
        {
            i = 0;
            line(x[i] + 150, y[i] + 150, x[n - 1] + 150, y[n - 1] + 150);
            break;
        }
        line(x[i] + 150, y[i] + 150, x[i + 1] + 150, y[i + 1] + 150);
    }
 
    // построение на экране второго многоугольника
 
    for (i = 0; i < z; i++)
    {
        circle(u[i] + 150, s[i] + 150, 2);
        if (i == z - 1)
        {
            i = 0;
            line(u[i] + 150, s[i] + 150, u[z - 1] + 150, s[z - 1] + 150);
            break;
        }
        line(u[i] + 150, s[i] + 150, u[i + 1] + 150, s[i + 1] + 150);
    }
 
    // Расчет площади первого многоугольника через сумму площадей трапеций
 
    for (i = 0; i < n; i++)
    {
        if (i == 0)
        {
            s1 = x[i] * (y[n - 1] - y[i + 1]); // если i == 0, то y[i-1] заменяем на y[n-1]
            res1 += s1;
        }
        else
            if (i == n - 1)
            {
                s1 = x[i] * (y[i - 1] - y[0]); // если i == n-1, то y[i+1] заменяем на y[0]
                res1 += s1;
            }
            else
            {
                s1 = x[i] * (y[i - 1] - y[i + 1]);
                res1 += s1;
            }
    }
 
    // Расчет площади второго многоугольника через сумму площадей трапеций
 
    for (i = 0; i < z; i++)
    {
        if (i == 0)
        {
            s2 = u[i] * (s[z - 1] - s[i + 1]); // если i == 0, то y[i-1] заменяем на y[z-1]
            res2 += s2;
        }
        else
            if (i == z - 1)
            {
                s2 = u[i] * (s[i - 1] - s[0]); // если i == z-1, то y[i+1] заменяем на y[0]
                res2 += s2;
            }
            else
            {
                s2 = u[i] * (s[i - 1] - s[i + 1]);
                res2 += s2;
            }
    }
 
    // Проверка принадлежности каждой точки первого многоугольника второму. В случае, если одна из точек не принадлежит
    // второму многоугольнику - в переменную c записываем -1 и выходим. Далее переменную c будем использовать как ключ
    for (i = 0; i < n; i++)
    {
        c = pnpoly(z, u, s, x[i], y[i]);
 
        if (c % 2 == 0)
        {
            c = -1;
            break;
        }
    }
 
    // Проверка принадлежности каждой точки второго многоугольника первому. В случае, если одна из точек не принадлежит
    // первому многоугольнику - в переменную t записываем -1 и выходим. Далее переменную t будем использовать как ключ
    for (i = 0; i < z; i++)
    {
        t = pnpoly(n, x, y, u[i], s[i]);
 
        if (t % 2 == 0)
        {
            t = -1;
            break;
        }
    }
 
    sq1 = abs(res1 / 2);
    sq2 = abs(res2 / 2);
    cout << "-------------" << endl;
    cout << "nJIoLLLagb nepBoro PaBHa: " << sq1 << endl;
    cout << "-------------" << endl;
    cout << "nJIoLLLagb BToporo PaBHa: " << sq2 << endl;
    cout << "c=" << c << "  t=" << t << endl;
 
    if (c >= 0)
        cout << "Perviy mnogougol'nik polnost'u lejit vo vtorom" << endl;
    else
        if (t >= 0)
            cout << "Vtoroy mnogougol'nik polnost'u lejit v pervom" << endl;
 
    getch();
    closegraph();
    return 0;
}
Где-то так... Провел два теста на двух квадратах - выдало правильный результат. В одном случае - один лежит внутри другого. Во втором случае - ничего не выдал, т.к. они никак не пересекаются.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2010, 19:22
Привет! Вот еще темы с ответами:

QBasic рисует выпуклые четырехугольники - QBasic
Здесь я хочу предложить вам программу, которая рисует несколько (не более пяти) выпуклых четырехугольников. Их вершины заданы...

Выпуклые или объемные надписи - C# WPF
Как сделать объемную надпись? напримет TextBlok или Label сделать объемным или выпуклым.

Как создать выпуклые кнопки в ToolBar - C#
Народ, не могу понять как в ToolBar создавать такие выпуклые квадратные кнопки, как на прикрепленной картинке. В стандартном варианте...

Многоугольники - Delphi
Здравствуйте. Помогите с задачей, пожалуйста! :) Смысл задания - зная длину стороны, нужно построить по ней равнсторонний многоугольник....


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

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

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