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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 72, средняя оценка - 4.69
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
#1

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

10.05.2012, 18:01. Просмотров 10350. Ответов 86
Метки нет (Все метки)

Нужен такой вот алгоритм (а ещё лучше функция ).Поиск по форуму не увенчался успехом (темы есть , но кода нет). Вершины многоугольника не пересекаются. Помогите пожалуйста.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.05.2012, 18:01
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Принадлежит ли точка многоугольнику (C++):

Принадлежит ли точка выпуклому многоугольнику - C++
Добрый день. Была задана следующая задача: пользователь задает координаты вершин многоугольника, затем координаты точки.Нужно определить,...

Дана точка М(x, y). Присвоить z = 1, если точка принадлежит окружности с радиусом R и центром в точке (a, b) и z = 0 в противном случае. - C++
Дана точка М(x, y). Присвоить z = 1, если точка принадлежит окружности с радиусом R и центром в точке (a, b) и z = 0 в противном случае.

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

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

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

Принадлежит ли точка фигуре - C++
Определить принадлежность точки областям, обозначенным прописными буквами A и B. Строчными буквами обозначены определяемые пользователем...

86
OstapBender
584 / 523 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 01:22 #61
Error 14 error C2660: 'intersection' : function does not take 3 arguments

Error 17 error C2664: 'func' : cannot convert parameter 1 from 'int **' to 'const int **'
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
11.05.2012, 01:29 #62
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 *const *const 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;
}
Не проверял компилятором, так должно работать.

Добавлено через 3 минуты
Проверил, вроде с простыми фигурами работает, если есть возможность, то проверьте с сложными.
1
OstapBender
584 / 523 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 01:39 #63
не работает на квадрате)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
arr[0][0] = 0;
arr[0][1] = 100;
 
arr[1][0] = 100;
arr[1][1] = 100;
 
arr[2][0] = 100;
arr[2][1] = 0;
 
arr[3][0] = 0;
arr[3][1] = 0;
 
 
int pointX = 20;
int pointY = 20;
 
 
if ( func( arr, size, pointX, pointY ))
std::cout << "yep";
else 
std::cout << "nop";
1
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
11.05.2012, 02:59 #64
Исправил, должно все работать:
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
bool intersection( const double rayX, const double rayY, const double pointX1, const double pointY1, const double pointX2, const double pointY2 ) {
   double Ua = (( pointX2 - pointX1 ) * ( rayY - pointY1 ) - ( pointY2 - pointY1 ) * ( rayX - pointX1 )) / -( pointX2 - pointX1 );
   double Ub = ( rayX - pointX1 ) / ( pointX2 - pointX1 );
   
   if ( 0 <= Ub && Ub <= 1 && Ua >= 0 )
      return true;
   
   return false;   
}
 
bool func( const double *const *const arr, const std::size_t size, const double pointX, const double 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;
}
Добавлено через 27 минут
Единственно не учитываются точки лежащие на ребрах. Можно попробовать изменить условие на
C++
1
if ( 0 <= Ub && Ub < 1 && Ua >= 0 )
Тогда по идеи будет учитывать их.
1
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
11.05.2012, 12:15  [ТС] #65
Цитата Сообщение от Toshkarik Посмотреть сообщение
const double *const *const arr
what the ... ?
константный указатель на вещественную константу указывающую на константу ?

Добавлено через 15 минут
Цитата Сообщение от Toshkarik Посмотреть сообщение
Единственно не учитываются точки лежащие на ребрах. Можно попробовать изменить условие на
Если его так изменить тогда и то что ниже будет говорить что точка многоугольника, пример:
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
int main()
{
    const int size=4;
    double **arr = new double *[ size ];
    for(int i=0;i<size;i++)
     arr[i]= new double[2];
 
    arr[0][0] = 0;
    arr[0][1] = 100;
 
    arr[1][0] = 100;
    arr[1][1] = 100;
 
    arr[2][0] = 100;
    arr[2][1] = 0;
 
    arr[3][0] = 0;
    arr[3][1] = 0;
 
 
    int pointX = 0;
    int pointY = -2;
 
 
    if ( func( arr, size, pointX, pointY ))
    std::cout << "yep";
    else
    std::cout << "nop";
}
Если в intersection будет
C++
1
if ( 0 <= Ub && Ub < 1 && Ua >= 0 )
то выдаст yep.

Прошёлся мейном по углам кодом Toshkarik (с вариантом не учитывающим точки лежащие на ребре, любопытно получилось. Все точки что я задавал должны принадлежать прямоугольнику, ну а в виде комментариев я дописал что выдаёт алгоритм
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
    arr[0][0] = 0;
    arr[0][1] = 100;
 
    arr[1][0] = 100;
    arr[1][1] = 100;
 
    arr[2][0] = 100;
    arr[2][1] = 0;
 
    arr[3][0] = 0;
    arr[3][1] = 0;
 
    //нет
    int pointX = 0;
    int pointY = 0;
 
    //да
    int pointX = 100;
    int pointY = 100;
 
    //да
    int pointX = 0;
    int pointY = 100;
 
    //нет
    int pointX = 100;
    int pointY = 0;
Тоесть для прямоугольника все точки от 0,0 до 100,0 включительно ошибочно не входят в многоугольник. Буду рад если Toshkarik сможет допилить свой алгоритм.
0
OstapBender
584 / 523 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 13:24 #66
Только для выпуклых:
(не рекомендуется к промышленному использованию, из-за затратности функций acos (с) википедия. )
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
    Vertex point = {-20, -50};
 
    int const n = 5;
    Vertex figure[n] = {
 
        {0,0},
        {0,100},
        {100,100},
        {150,50},
        {100,0}
 
    };
 
    double summAng = 0;
    
    for (int i=0; i<n; i++) {
 
        int next = i+1;
 
        if (next >= n) {
            next = 0;
        }
 
        double A1 = point.y - figure[i].y;
        double B1 = point.x - figure[i].x;
 
        double A2 = point.y - figure[next].y;
        double B2 = point.x - figure[next].x;
 
        summAng += 180 * acos( ((A1 * A2) + (B1 * B2)) / ( pow( B1*B1 + A1*A1, 0.5) * pow( B2*B2 + A2*A2, 0.5) ) ) / 3.14159;
 
    }
 
    if (((summAng > 359.6) && (summAng < 360.4)) ||
        ((summAng > -0.6) && (summAng < 0.4)) )
        puts("inside");
    else
        puts("Outside");
1
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
11.05.2012, 15:22  [ТС] #67
Ещё погонял алгоритм Toshkarik, со звездой он тоже работает хорошо (в том плане чо за границы звезды не выходит), но тоже ведь нужно как-то учесть тот случай когда точка на одном из рёбер (не на всех, часть точек на ребрах оно считает правильно).

мейн со звездой
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
int main()
{
    const int size=10;
    double **arr = new double *[ size ];
    for(int i=0;i<size;i++)
     arr[i]= new double[2];
 
    arr[0][0] = 10;
    arr[0][1] = 40;
 
    arr[1][0] = 15;
    arr[1][1] = 40;
 
    arr[2][0] = 20;
    arr[2][1] = 45;
 
    arr[3][0] = 30;
    arr[3][1] = 40;
 
    arr[4][0] = 40;
    arr[4][1] = 40;
 
    arr[5][0] = 25;
    arr[5][1] = 30;
 
    arr[6][0] = 30;
    arr[6][1] = 20;
 
    arr[7][0] = 20;
    arr[7][1] = 25;
 
    arr[8][0] = 10;
    arr[8][1] = 20;
 
    arr[9][0] = 15;
    arr[9][1] = 30;
 
    int pointX = 25;
    int pointY = 30;
 
 
    if ( func( arr, size, pointX, pointY ))
    std::cout << "yep";
    else
    std::cout << "nop";
}
0
Миниатюры
Принадлежит ли точка многоугольнику  
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
11.05.2012, 16:54 #68
Цитата Сообщение от Gepar Посмотреть сообщение
const double *const *const arr
Константный указатель на константный указатель на константные данные.
По поводу ребер - нужно найти условие, когда точка совпадает с ребром, в алгоритме это считается за пересечение. Попробую что нибудь сделать.

Добавлено через 18 минут
Я тут подумал, можно проверять не лежит ли точка на ребре уравнением, если лежит то возвращать false. Но, мы ведь направляем луч параллельно оси X, если точка будет на одном из верхних ребер то опять же не будет считаться, что точка принадлежит фигуре. Можно попробовать единственно передавать еще одним параметром по ссылке, лежит ли точка на ребре. Потом в конце добавить проверку, если число пересечений 0 и точка лежит на ребре, то true.
1
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
11.05.2012, 17:06  [ТС] #69
Внезапно мне сообщают что многоугольники выпуклые и правильные (второе наверное означает что не пересекаются линии). Подскажите самый быстрый и оптимальный алгортим для выпуклых прямоугольников пожалуйста

Добавлено через 10 минут
OstapBender, а тоже самое по поиску принадлежности точки выпуклому многоугольнику, но более эффективно как реализовать?
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
11.05.2012, 17:41 #70
Добил все таки задачу:
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
bool intersection( const double rayX, const double rayY, const double pointX1, const double pointY1, const double pointX2, const double pointY2 ) {
   double Ua = (( pointX2 - pointX1 ) * ( rayY - pointY1 ) - ( pointY2 - pointY1 ) * ( rayX - pointX1 )) / -( pointX2 - pointX1 );
   double Ub = ( rayX - pointX1 ) / ( pointX2 - pointX1 );
   
   if ( 0 <= Ub && Ub <= 1 && Ua >= 0 )
      return true;
   
   return false;   
}
 
double squareDistance( const double pointX1, const double pointY1, const double pointX2, const double pointY2 ) {
   return (( pointX1 - pointX2 ) * ( pointX1 - pointX2 ) + ( pointY1 - pointY2 ) * ( pointY1 - pointY2 ));
}
 
bool func( const double *const *const arr, const std::size_t size, const double pointX, const double pointY ) {
   unsigned int count = 0;
   double d1 = squareDistance( arr[ 0 ][ 0 ], arr[ 0 ][ 1 ], arr[ size - 1 ][ 0 ], arr[ size - 1 ][ 1 ]),
          d2 = squareDistance( arr[ 0 ][ 0 ], arr[ 0 ][ 1 ], pointX, pointY ),
          d3 = squareDistance( arr[ size - 1 ][ 0 ], arr[ size - 1 ][ 1 ], pointX, pointY );
   
   if ( d1 == d2 + d3 )
         return true;
   
   for ( std::size_t i = 1; i < size; i++ ) {
      d1 = squareDistance( arr[ i - 1 ][ 0 ], arr[ i - 1 ][ 1 ], arr[ i ][ 0 ], arr[ i ][ 1 ]);
      d2 = squareDistance( arr[ i - 1 ][ 0 ], arr[ i - 1 ][ 1 ], pointX, pointY );
      d3 = squareDistance( arr[ i ][ 0 ], arr[ i ][ 1 ], pointX, pointY );
      
      if ( d1 == d2 + d3 )
         return true;
         
      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;
}
Теперь если точка на ребре, то сразу возвращается true.

Цитата Сообщение от Gepar Посмотреть сообщение
Подскажите самый быстрый и оптимальный алгортим для выпуклых прямоугольников пожалуйста
Ну так попробуйте тот, который я предлагал изначально, методом разбивки на простые треугольники. Или, есть еще способ, через векторное произведение. О нем только читал мельком, попозже гляну что имеется ввиду.
1
golatin
267 / 224 / 44
Регистрация: 12.10.2011
Сообщений: 336
Завершенные тесты: 1
11.05.2012, 18:01 #71
Посмотрите здесь
http://habrahabr.ru/post/125356/
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
12.05.2012, 09:26  [ТС] #72
golatin, видел, в отзывах раскритиковали что это медленнее чем метод с треугольниками.

Добавлено через 1 час 16 минут
И ещё вопрос отдалённо касающийся темы: для прямоугольников как лучше всего определять принадлежит ли им точка ? Тоже разбивать на два треугольника или есть методы получше?

Добавлено через 12 часов 52 минуты
Что-то не получается у меня этот метод треугольников на многоугольнике применить. Помогите пожалуйста кодом функции.
0
castaway
Эксперт С++
4885 / 3020 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
12.05.2012, 11:32 #73
Цитата Сообщение от Gepar Посмотреть сообщение
для прямоугольников как лучше всего определять принадлежит ли им точка ? Тоже разбивать на два треугольника или есть методы получше?
Не надо тут ничего разбивать.
C
1
2
3
4
5
6
int inrect( int rect[][2], int x, int y )
{
    if ( x < rect[0][0] || x > rect[1][0] ||
         y < rect[0][1] || y > rect[1][1] ) return 0;
    return 1;
}

Цитата Сообщение от Gepar Посмотреть сообщение
Что-то не получается у меня этот метод треугольников на многоугольнике применить. Помогите пожалуйста кодом функции.
Быстрее метода не нашел:
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
int inpoly( unsigned int poly[][2], int npoints, unsigned int xt, unsigned int yt )
{
    int             i;
    int             inside = 0;
    unsigned int    xnew, ynew;
    unsigned int    xold, yold;
    unsigned int    x1, y1;
    unsigned int    x2, y2;
 
    if ( npoints < 3 ) return 0;
 
    xold = poly[npoints - 1][0];
    yold = poly[npoints - 1][1];
 
    for ( i = 0; i < npoints; i++ ) {
 
        xnew = poly[i][0];
        ynew = poly[i][1];
 
        if ( xnew > xold ) {
            x1 = xold;
            x2 = xnew;
            y1 = yold;
            y2 = ynew;
        } else {
            x1 = xnew;
            x2 = xold;
            y1 = ynew;
            y2 = yold;
        }
 
        if ( (xnew < xt) == (xt <= xold) &&
             ((long)yt - (long)y1) * (long)(x2 - x1) <
             ((long)y2 - (long)y1) * (long)(xt - x1) ) inside = !inside;
 
        xold = xnew;
        yold = ynew;
    }
    return inside;
}
0
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
12.05.2012, 11:44  [ТС] #74
lazybiz, но он не учитывает точки что идут на линиях соединяющих точки многоугольника
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
int main()
{
    const int size=4;
    unsigned int arr[size][2];
 
    arr[0][0] = 0;
    arr[0][1] = 100;
 
    arr[1][0] = 100;
    arr[1][1] = 100;
 
    arr[2][0] = 100;
    arr[2][1] = 0;
 
    arr[3][0] = 0;
    arr[3][1] = 0;
 
 
    int pointX = 10;
    int pointY = 100;
 
 
    if ( inpoly( arr, size, pointX, pointY ))//выдаст nop
    std::cout << "yep";
    else
    std::cout << "nop";
}
0
castaway
Эксперт С++
4885 / 3020 / 370
Регистрация: 10.11.2010
Сообщений: 11,078
Записей в блоге: 10
Завершенные тесты: 1
12.05.2012, 12:03 #75
Цитата Сообщение от Gepar Посмотреть сообщение
lazybiz, но он не учитывает точки что идут на линиях соединяющих точки многоугольника
Ну тогда я думаю тебя устроит такой вариант:
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
#define fmin( a, b )    (((a) > (b)) ? (b) : (a))
#define fmax( a, b )    (((a) > (b)) ? (a) : (b))
 
int pointinpoly( double pgon[][2], int numverts, double x, double y )
{
    int     i, crossings = 0;
 
    for ( i = 0; i < numverts; i++ ) {
 
        double x1 = pgon[i][0];
        double y1 = pgon[i][1];
        double x2 = pgon[(i + 1) % numverts][0];
        double y2 = pgon[(i + 1) % numverts][1];
        double d = (y - y1) * (x2 - x1) - (x - x1) * (y2 - y1);
 
        if ( (y1 >= y) != (y2 >= y) ) {
            crossings += y2 - y1 >= 0 ? d >= 0 : d <= 0;
        }
 
        if ( !d && fmin( x1, x2 ) <= x && x <= fmax( x1, x2 )
                && fmin( y1, y2 ) <= y && y <= fmax( y1, y2 ) ) {
            return 1;
        }
    }
    return crossings & 1;
}
Он не такой быстрый как тот, но считает более правильно как мне кажется.
0
12.05.2012, 12:03
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.05.2012, 12:03
Привет! Вот еще темы с ответами:

Принадлежит ли точка четырехугольнику. - C++
Надеюсь на помощь форумчан: Задача следующяя: задана коодинатами точек четырёхугольная фигура A(-2,-1) B(-1,1) C(0,0) D(1,0) С...

Принадлежит ли точка прямоугольнику? - C++
Составить программку для определения принадлежности точки в прямоугольной области(прямоугольнику).

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

Принадлежит ли точка прямоугольнику? - C++
Даны координаты (x1, y1), (x2, y2), (x3, y3), (x4, y4) - вершины прямоугольника, и (x,y) - координаты точки. Определить, принадлежит ли...


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

Или воспользуйтесь поиском по форуму:
75
Ответ Создать тему
Опции темы

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