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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 72, средняя оценка - 4.69
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 18:01     Принадлежит ли точка многоугольнику #1
Нужен такой вот алгоритм (а ещё лучше функция ).Поиск по форуму не увенчался успехом (темы есть , но кода нет). Вершины многоугольника не пересекаются. Помогите пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
10.05.2012, 23:30     Принадлежит ли точка многоугольнику #41
Итак как это будет выглядеть на псевдокоде:

Код
Задать произвольное направление луча от заданной точки ( например параллельно оси x )
Инициализировать счетчик пересечений нулем

Инициализировать i единицей
Пока i < n
   Решить систему из двух уравнений: 1 уравнение луча, 2 уравнение отрезка из двух точек - первая точка arr[ i ], вторая - arr[ i - 1 ]
   Если отрезок и луч пересекаются
      Увеличить счетчик на пересечений 1

Решить систему из двух уравнений: 1 уравнение луча, 2 уравнение отрезка из двух точек - первая точка arr[ 0 ], вторая - arr[ n - 1 ]
Если отрезок и луч пересекаются
      Увеличить счетчик на пересечений 1

Если число пересечений нечетное
   Вернуть true
Иначе
   Вернуть false
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
10.05.2012, 23:32     Принадлежит ли точка многоугольнику #42
а ларчик то просто открывался :
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
#undef min
#undef max
 
double max(double v1,double v2) {
    return v1 > v2 ? v1 : v2;
}
 
double min(double v1, double v2) {
    return v1 < v2 ? v1 : v2;
}
 
struct Vertex {
    double x,y,z;
};
 
struct Line {
    Vertex p1, p2;
};
 
bool LinesIntersect(Vertex p11, Vertex p12, Vertex p21, Vertex p22) {
 
double maxx1 = max(p11.x, p12.x), maxy1 = max(p11.y, p12.y);
double minx1 = min(p11.x, p12.x), miny1 = min(p11.y, p12.y);
double maxx2 = max(p21.x, p22.x), maxy2 = max(p21.y, p22.y);
double minx2 = min(p21.x, p22.x), miny2 = min(p21.y, p22.y);
 
if (minx1 > maxx2 || maxx1 < minx2 || miny1 > maxy2 || maxy1 < miny2)
  return FALSE;  // Момент, када линии имеют одну общую вершину...
 
 
double dx1 = p12.x-p11.x, dy1 = p12.y-p11.y; // Длина проекций первой линии на ось x и y
double dx2 = p22.x-p21.x, dy2 = p22.y-p21.y; // Длина проекций второй линии на ось x и y
double dxx = p11.x-p21.x, dyy = p11.y-p21.y;
double div, mul;
 
 
if ((div = (int)((double)dy2*dx1-(double)dx2*dy1)) == 0) 
  return FALSE; // Линии параллельны...
if (div > 0) {
  if ((mul = (int)((double)dx1*dyy-(double)dy1*dxx)) < 0 || mul > div)
    return FALSE; // Первый отрезок пересекается за своими границами...
  if ((mul = (int)((double)dx2*dyy-(double)dy2*dxx)) < 0 || mul > div)
     return FALSE; // Второй отрезок пересекается за своими границами...
}
else {
if ((mul = -(int)((double)dx1*dyy-(double)dy1*dxx)) < 0 || mul > -div)
  return FALSE; // Первый отрезок пересекается за своими границами...
if ((mul = -(int)((double)dx2*dyy-(double)dy2*dxx)) < 0 || mul > -div)
  return FALSE; // Второй отрезок пересекается за своими границами...
}
return TRUE;
}
 
 
 
 
 
double getLineY(Vertex p1, Vertex p2, double x) {
    return ( ((x - p1.x) * (p2.y - p1.y)) / (p2.x - p1.x)) + p1.y;
}
 
 
 
 
int main() {
 
    const int n = 5;
 
    Line figure[n] = {
 
        {{0,100,0},{100,100,0}},
        {{100,100,0},{50,50,0}},
        {{50,50,0},{100,0,0}},
        {{100,0,0},{0,0,0}},
        {{0,0,0},{0,100,0}}
 
    };
 
    Vertex point = {20, 80, 0};
 
    Vertex line_p = {(figure[0].p1.x + figure[0].p2.x) / 2, 0, 0};
 
    line_p.y = getLineY(figure[0].p1, figure[0].p2, line_p.x);
 
    Vertex far_point;
 
    if (point.x > line_p.x)
        far_point.x = -500;
    else
        far_point.x = 500;
 
    far_point.y = getLineY(point, line_p, far_point.x);
 
    int count = 0;
 
    for (int i=0; i<n; i++) {
 
        if (LinesIntersect(figure[i].p1, figure[i].p2, point, far_point)) {
            printf("Intersected line %d\n",i+1);
            count++;
        }
 
    }
 
    //std::cout << count;
 
    if (count & 1) {
        puts("Inside");
    }
    else {
        puts("Outside");
    }
 
    std::cin.get();
    
}
в 1-м месте был пропущен else.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 23:45  [ТС]     Принадлежит ли точка многоугольнику #43
OstapBender, что-то я в вашем коде потерялся: почему 3х мерное пространство? почему LinesIntersect принимает 4 координаты? Что в main вообще происходит? Почему часть кода си, а часть с++ (printf,а рядом потоки cin/cout)? Похоже что в main часть каких-то вычислений ещё, но почему они в main, а не в функциях по вычислениях.

Добавлено через 3 минуты
Toshkarik, наверное всё же нужна функция. Помогите с её написанием пожалуйста. Я вижу я уже окончательно запутался со всеми этими методами обходов вершин многоугольников ...
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
10.05.2012, 23:47     Принадлежит ли точка многоугольнику #44
Gepar, я немного поправил код, но понял ошибку. Когда я писал, я думал, что координаты вершин в массиве хранятся последовательно. Щас еще что-нибудь написать попробую Пока код нерабочий. Попробую упорядочить массив вершин
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool belong(float x[], float y[],float dotx,float doty, int n)
{//n - размерность массива, массивы x и y хранят координаты вершин многоугольника, dotx, doty - координаты точки
     bool b=false;
     for(int i=0;i<n-1;i++)//луч направляем вдоль оси х
/*1*/  {if((dotx<x[i]||dotx<x[i+1])&&doty<y[i]&&doty>y[i+1]||(dotx<x[i]||dotx<x[i+1])&&doty>y[i]&&doty<y[i+1]) {b=!b;cout<<1<<endl;}//если пересечет многоуолник нечетное число раз - тру
/*2*/     if(dotx==x[i]&&doty==y[i]){cout<<2<<endl;return true;}//если точка в вершине
     /*3*/if(y[i]!=y[i+1]){cout<<3<<endl;
     /*4*/if(((dotx<x[i]&&dotx>x[i+1])||(dotx>x[i]&&dotx<x[i+1]))&&(dotx*(y[i]-y[i+1])/(x[i]-x[i+1])==doty)){cout<<4<<endl; return true;}}//если точка лежит на ребре
     /*5*/if((y[i]==y[i+1])&&(doty==y[i])&&((dotx<x[i]&&dotx>x[i+1])||(dotx>x[i]&&dotx<x[i+1]))) {cout<<5<<endl;return true;}//если точка лежит на ребре
    /*6*/ if((y[i]==y[i+1])&&(doty==y[i])){cout<<6<<endl; b=!b;}//если ребро принадлежит лучу, мы его как будто все таки пересекаем =)
   }
   /*7*/    if((dotx<x[0]||dotx<x[n-1])&&doty<y[0]&&doty>y[n-1]||(dotx<x[0]||dotx<x[n-1])&&doty>y[0]&&doty<y[n-1]){cout<<7<<endl; b=!b;}//пересечение с последним ребром
 /*8*/      if((y[0]==y[n-1])&&(y[0]==doty)){cout<<8<<endl;b=!b;}//если ребро принадлежит лучу, мы его как будто все таки пересекаем =)
 /*9*/      if(dotx==x[n-1]&&doty==y[n-1]){cout<<9<<endl;return true;}//если точка в вершине
  /*10*/   cout<<10<<endl;
     return b;
     }
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
10.05.2012, 23:57  [ТС]     Принадлежит ли точка многоугольнику #45
Цитата Сообщение от ser4ega Посмотреть сообщение
Когда я писал, я думал, что координаты вершин в массиве хранятся последовательно.
Ну они последовательно хранятся. Только неизвестно в какую сторону они пойдут: слева-направо, или справа-налево. Тоесть тот же мой домик может рисоваться начиная как с нижних точек(20,10 или 30,10) так и с верхней (25,30).
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
10.05.2012, 23:59     Принадлежит ли точка многоугольнику #46
Gepar, 3-х мерная тока структура Vertex, 3-ю координату я не использую..
Цитата Сообщение от Gepar Посмотреть сообщение
Что в main вообще происходит
алгоритм который я описал на 2ой странице!
Цитата Сообщение от Gepar Посмотреть сообщение
Почему часть кода си, а часть с++ (printf,а рядом потоки cin/cout)
простишь?? ...
Цитата Сообщение от Gepar Посмотреть сообщение
Похоже что в main часть каких-то вычислений ещё, но почему они в main, а не в функциях по вычислениях.
хз вынеси в функцию.

там требуется изменить только список вершин и точку .

Добавлено через 1 минуту
Цитата Сообщение от Gepar Посмотреть сообщение
почему LinesIntersect принимает 4 координаты?
название функции какбе Намекает - пересечение 2-х линий - 4 вершины...
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
11.05.2012, 00:16  [ТС]     Принадлежит ли точка многоугольнику #47
Цитата Сообщение от OstapBender Посмотреть сообщение
epar, 3-х мерная тока структура Vertex, 3-ю координату я не использую..
А... ээээ... ммм... так а писать сразу 3 зачем тогда, задел на будущее?

Добавлено через 9 минут
Цитата Сообщение от OstapBender Посмотреть сообщение
if (point.x > line_p.x)
far_point.x = -500;
else
far_point.x = 500;
А это псевдо уход в бесконечность я так понимаю? Так а меня предупредили что у меня могут быть огромнейшие координаты, ну 999500 например.
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
11.05.2012, 00:22     Принадлежит ли точка многоугольнику #48
ПЛЯЯЯЯЯЯЯЯ!! Тока допер, что нельзя однозначно по точкам задать многоугольник.
Что делать-то теперь?

Кто не верит - ручка, листик, точки и обводим как хотим, вариант не вседа единственный

как я понял, вариант единственнен только для выпуклых фигур, мафака !!
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
11.05.2012, 00:26  [ТС]     Принадлежит ли точка многоугольнику #49
ser4ega, почему это? Вполне можно же , каждая точка сводится с предыдущей. Последняя сводится с первой. То что они не пересекаются задано условием. Всё ок с рисованием многоугольника, не ок с определением вхождения точки ...
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 00:28     Принадлежит ли точка многоугольнику #50
Gepar, ну простите БОСС ___))
Цитата Сообщение от Gepar Посмотреть сообщение
А это псевдо уход в бесконечность я так понимаю?
точно. для отладки и 500 норм.
ser4ega
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
11.05.2012, 00:32     Принадлежит ли точка многоугольнику #51
я это к тому, что теперь реально важен порядок следования точек в массиве
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,511
11.05.2012, 00:33  [ТС]     Принадлежит ли точка многоугольнику #52
Цитата Сообщение от ser4ega Посмотреть сообщение
Кто не верит - ручка, листик, точки и обводим как хотим, вариант не вседа единственный
Точки сводим по принципу
1 -> 2 ->3 -> 4 ->5 ->6 -> 1.
Другое дело неизвестно как они будут на плоскости выглядеть. Может быть 2 и 3 будут левее 1, а может быть правее, но это не столь важно, важно что все эти линии пересекаться не будут.

*ухожу спать. Присоединюсь к дальнейшим поискам завтра утром под 9:00. Буду рад если участники сегодняшней беседы заглянут в тему и завтра, ато на данный момент вопрос ещё окончательно не решён. Например я не знаю что делать с этими +500 и -500 в коде OstapBender. ведь точка может быть и сразу типа 999500, но не могу же я задать её вида 999999 для всех-всех точек, это будет не рационально для точек вида 10, 20 да 100,50. Вызывать каждый раз max для всех точек многоугольника чтобы определить самую большую координату тоже не очень то хорошо так как это тоже занимает время ... ну да завтра нужно будет решиться со всем этим.
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 00:48     Принадлежит ли точка многоугольнику #53
Gepar, а вот и не угадал.
задашь 999999 и всё будет ок.

Добавлено через 46 секунд
на то он и бесконечный луч)
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
11.05.2012, 01:04     Принадлежит ли точка многоугольнику #54
Вот что то попробовал сделать, попробуйте пожалуйста, самому интересно, сработает или нет:
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
bool intersection( const double rayX, const double rayY, const double pointX1, const double pointY1, const double pointX2, const double pointY2 ) {
   double rayY2 = ( pointY1 > pointY2 ? pointY1 : pointY2 );
   double Ub = ( rayX - pointX1 ) / ( pointX2 - pointX1 );
   double Ua = ( pointY1 + Ub * ( pointY2 - pointY1 ) - rayY ) / ( rayY2 - rayY );
   
   if ( 0 <= Ub && Ub <= 1 && 0 <= Ua && Ua <= 1 )
      return true;
   
   return false;   
}
 
bool func( const int **arr, const std::size_t size, const int pointX, const int pointY ) {
   unsigned int count = 0;
   
   for ( std::size_t i = 1; i < size; i++ )
      if ( intersection( pointX, pointY, arr[ i - 1 ][ 0 ]), arr[ i - 1 ][ 1 ], arr[ i ][ 0 ], arr[ i ][ 1 ])
         count++;
 
   if ( intersection( pointX, pointY, arr[ 0 ][ 0 ]), arr[ 0 ][ 1 ], arr[ size - 1 ][ 0 ], arr[ size - 1 ][ 1 ])
         count++;
   
   if ( count % 2 )
      return true;
   
   return false;
}
Добавлено через 7 минут
Бесконечность луча в данном случае абстрактна. Ее можно принять как равную максимальной Y-координате одной из вершин отрезка, с которым мы ищем пересечение. В моем коде у луча X-координата не изменяется, мы его делаем параллельным оси X, а за "конец" луча берется максимальная Y-координата отрезка, с которым ищем пересечение.
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 01:05     Принадлежит ли точка многоугольнику #55
Цитата Сообщение от Toshkarik Посмотреть сообщение
const int **arr
это как использовать ...
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
11.05.2012, 01:06     Принадлежит ли точка многоугольнику #56
Цитата Сообщение от OstapBender Посмотреть сообщение
это как использовать ...
Как двумерный массив, как же еще. Передается указатель на массив указателей на константные данные.
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 01:08     Принадлежит ли точка многоугольнику #57
Toshkarik, ну приведи пример чтоли
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
11.05.2012, 01:10     Принадлежит ли точка многоугольнику #58
В функции же используется. Какой еще нужен пример?
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 01:11     Принадлежит ли точка многоугольнику #59
Toshkarik, пример вызова функции.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.05.2012, 01:13     Принадлежит ли точка многоугольнику
Еще ссылки по теме:

C++ Даны отрезки [a, b] и [c, d] и точка A с координатой х. Определить, принадлежит ли данная точка одному из этих отрезков, обоим или лежит вне их
C++ Определить, принадлежит ли точка M(x,y)
Принадлежит ли точка области C++

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

Или воспользуйтесь поиском по форуму:
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
11.05.2012, 01:13     Принадлежит ли точка многоугольнику #60
Массив может быть объявлен где угодно вот так:
C++
1
2
3
4
5
6
7
8
9
10
int **array = new int *[ size ];
 
for ( std::size_t i = 0; i < size; i++ )
   array[ i ] = new int [ 2 ];
 
//тут присваиваем значения точкам
//...
//тут вызываем функцию
if ( func( array, size, pointX, pointY ))
   //делаем что то
Yandex
Объявления
11.05.2012, 01:13     Принадлежит ли точка многоугольнику
Ответ Создать тему
Опции темы

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