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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.92
kosmosnsk
0 / 0 / 0
Регистрация: 21.05.2010
Сообщений: 10
21.05.2010, 16:21     Выпуклые многоугольники #1
Два выпуклых многоугольника заданы на плоскости перечислением координат вершин в порядке обхода границы. Проверить лежит ли один из них строго внутри другого и определить площади многоугольников.

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

Многоугольники Delphi
C# Многоугольники
Выпуклые четырехугольники Pascal ABC
Delphi Выпуклые кнопки на ToolBar.
Выпуклые или объемные надписи C# WPF
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 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
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 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
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 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
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 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
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 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
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 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;
}
Где-то так... Провел два теста на двух квадратах - выдало правильный результат. В одном случае - один лежит внутри другого. Во втором случае - ничего не выдал, т.к. они никак не пересекаются.
kosmosnsk
0 / 0 / 0
Регистрация: 21.05.2010
Сообщений: 10
23.05.2010, 19:41  [ТС]     Выпуклые многоугольники #16
Спасибо тебе ОГРОМНОЕ!!! бывают же добрые люди...

объясни еще пожалуйста что в строке
C
1
int pnpoly(int npol, int *xp, int *yp, int x, int y)
означают звездочки, и вообще xp и yp?... так и не понял я(((

и почему делается вот это, вернее то что в скобках так..
C
1
t = pnpoly(n, x, y, u[i], s[i]);
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
23.05.2010, 19:52     Выпуклые многоугольники #17
Вообще в зависимости от контекста звёздочка может означать разные вещи. В данном случае звёздочка означает, что в функцию мы будем передавать не само значение переменной (в таком случае это значение будет скопировано в локальную для вызываемой функции переменную, и если в функции будут происходить изменения значения, то эти изменения не затронут переменную в вызывающей функции, а будут совершаться над вновь созданной переменной вызываемой функции), а её адрес (если мы передадим адрес, то, применив в вызываемой функции операцию разыменования (взятия значения по адресу), мы сможем изменить значение основной переменной). Вообще, указатели считаются одной из самых трудных для понимания тем, но это очень мощная и полезная штука)))
На счёт второго вопроса. Здесь происходит то же самое, что и несколькими строками ранее, только теперь мы проверяем все точки второго многоугольника на принадлежность первому...

Добавлено через 2 минуты
А, забыл)))
xp и yp - это массивы, содержащие координаты x и y прямоугольника. ну а переменные x и y - координаты точки, которую мы проверяем на принадлежность этому многоугольнику.
kosmosnsk
0 / 0 / 0
Регистрация: 21.05.2010
Сообщений: 10
23.05.2010, 19:55  [ТС]     Выпуклые многоугольники #18
мда... про адреса я что-то читал но толком не понял еще... ладно, еще учиться и учиться! хорошо хоть интерес есть))

я имею ввиду почему именно
C
1
n, x, y, u[i], s[i]
вот эти переменные там, а не те которые писались в функции... или типа адреса xp и yp передались в u[i] и s[i]?? если да, то адрес это для меня пока что окно в новый мир((

теперь понял! =) еще раз СПАСИБО!!!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2010, 19:59     Выпуклые многоугольники
Еще ссылки по теме:

Delphi МНОГОУГОЛЬНИКИ!!!!!!!!
QBasic рисует выпуклые четырехугольники QBasic
Класс Многоугольники C++

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

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
23.05.2010, 19:59     Выпуклые многоугольники #19
Нет, функция - это универсальная вещь. Мы ведь можем написать в объявлении в качестве параметров переменные с одними именами, а при вызове передавать туда переменные с другими именами. Главное, чтобы типы совпадали.
На счёт адресов. Суть здесь в том, что имя массива без операции индексации (квадратные скобки) представляет собой ни что иное, как адрес начала этого массива. И, передавая в функцию x и y, мы на самом деле передаём адраса начала массивов x и y. Ну а переменные u[i] и s[i] - это всего лишь какие-то целые числа - элементы целочисленного массива.
Yandex
Объявления
23.05.2010, 19:59     Выпуклые многоугольники
Ответ Создать тему
Опции темы

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