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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 72, средняя оценка - 4.69
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
10.05.2012, 18:01     Принадлежит ли точка многоугольнику #1
Нужен такой вот алгоритм (а ещё лучше функция ).Поиск по форуму не увенчался успехом (темы есть , но кода нет). Вершины многоугольника не пересекаются. Помогите пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OstapBender
 Аватар для OstapBender
581 / 519 / 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 **'
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 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 минуты
Проверил, вроде с простыми фигурами работает, если есть возможность, то проверьте с сложными.
OstapBender
 Аватар для OstapBender
581 / 519 / 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";
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 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 )
Тогда по идеи будет учитывать их.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
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 сможет допилить свой алгоритм.
OstapBender
 Аватар для OstapBender
581 / 519 / 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");
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
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";
}
Миниатюры
Принадлежит ли точка многоугольнику  
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
11.05.2012, 16:54     Принадлежит ли точка многоугольнику #68
Цитата Сообщение от Gepar Посмотреть сообщение
const double *const *const arr
Константный указатель на константный указатель на константные данные.
По поводу ребер - нужно найти условие, когда точка совпадает с ребром, в алгоритме это считается за пересечение. Попробую что нибудь сделать.

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

Добавлено через 10 минут
OstapBender, а тоже самое по поиску принадлежности точки выпуклому многоугольнику, но более эффективно как реализовать?
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 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 Посмотреть сообщение
Подскажите самый быстрый и оптимальный алгортим для выпуклых прямоугольников пожалуйста
Ну так попробуйте тот, который я предлагал изначально, методом разбивки на простые треугольники. Или, есть еще способ, через векторное произведение. О нем только читал мельком, попозже гляну что имеется ввиду.
golatin
259 / 216 / 38
Регистрация: 12.10.2011
Сообщений: 311
Завершенные тесты: 1
11.05.2012, 18:01     Принадлежит ли точка многоугольнику #71
Посмотрите здесь
http://habrahabr.ru/post/125356/
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
12.05.2012, 09:26  [ТС]     Принадлежит ли точка многоугольнику #72
golatin, видел, в отзывах раскритиковали что это медленнее чем метод с треугольниками.

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

Добавлено через 12 часов 52 минуты
Что-то не получается у меня этот метод треугольников на многоугольнике применить. Помогите пожалуйста кодом функции.
castaway
Эксперт С++
4846 / 2985 / 368
Регистрация: 10.11.2010
Сообщений: 11,026
Записей в блоге: 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;
}
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
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";
}
castaway
Эксперт С++
4846 / 2985 / 368
Регистрация: 10.11.2010
Сообщений: 11,026
Записей в блоге: 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;
}
Он не такой быстрый как тот, но считает более правильно как мне кажется.
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
12.05.2012, 12:15  [ТС]     Принадлежит ли точка многоугольнику #76
lazybiz, наверное дело в оптимизации но второй вариант у меня выполняется даже чуть-чуть быстрее

Добавлено через 2 минуты
Осталось самое сложное - придумать в какой структуре хранить фигурки чтобы быстро находить их принадлежность точкам
castaway
Эксперт С++
4846 / 2985 / 368
Регистрация: 10.11.2010
Сообщений: 11,026
Записей в блоге: 10
Завершенные тесты: 1
12.05.2012, 12:22     Принадлежит ли точка многоугольнику #77
Цитата Сообщение от Gepar Посмотреть сообщение
lazybiz, наверное дело в оптимизации но второй вариант у меня выполняется даже чуть-чуть быстрее
Я решил что он медленней из-за двух остатков от деления. Хотя я даже знаю как ему можно попробовать оптимизировать... Можно избавиться от операций %.

Цитата Сообщение от Gepar Посмотреть сообщение
Осталось самое сложное - придумать в какой структуре хранить фигурки чтобы быстро находить их принадлежность точкам
Не понял. Что тут сложного?
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
12.05.2012, 12:39  [ТС]     Принадлежит ли точка многоугольнику #78
Цитата Сообщение от lazybiz Посмотреть сообщение
Не понял. Что тут сложного?
Если коротко то у меня есть 4 фигуры (все наследники от одного общего класса): треугольник, круг, прямоугольник и многоугольник. У каждой фигуры есть свой ID. Задача: организовать как-то хранение этого всего так чтобы когда нам будут давать точку (0,0 например) мы могли ответить в какие фигуры мы "попали" (вернуть ID фигур, то что под ID скрывается нас не интересует). Всё бы хорошо, да надо чтобы это работало максимально быстро и нужно это написать до понедельника
В общем-то решений тут наверное много, я лично вижу 2:
1) Правильное, каноничное, красивое. Использовать сегментное дерево специально созданное для таких целей. Сложности: нужно два дерева (одно для x, другое для y) + такое дерево не умеет хранить рандомную ерунду вроде многоугольника, поэтому при добавлении придётся рисовать возле каждой фигуры прямоугольник (+ затраченное время на поиск 4х угловых точек). Боюсь я с таким сам не справлюсь за 1.5 дня (кроме этого задания естественно у меня есть ещё подготовка к экзаменам), я с сегментными деревьями никогда не работал и вообще деревья со всякими хитрыми балансировками не люблю.

2) Надеюсь что сработает. Использовать упорядоченный односвязный список. Планирую хранить всё в односвязном списке где как узел будет у меня указатель на фигуру, её самая левая координата x и её самая правая координата x. Далее буду бегать по списку сверяясь попадает ли точка между этими двумя x и если попадает то вызывать метод belong для проверки. Боюсь только что это при количестве элементов >=1000 будет жутко медленно работать
Решение номер 2 в виде кода если кому интересно (список сам ещё не завёл, есть только функции нахождения принадлежности фигур, а также нахождения их левых и правых иксов):
код
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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
#ifndef __PROGTEST__
struct CCoord
 {
   CCoord   ( int x = 0, int y = 0 ) { m_X = x; m_Y = y; }
   int   m_X;
   int   m_Y;
 };
#endif /* __PROGTEST__ */
 
 
#define fmin( a, b )    (((a) > (b)) ? (b) : (a))
#define fmax( a, b )    (((a) > (b)) ? (a) : (b))
 
//базовый класс для фигур
class CObject
{
public:
    CObject(int _id)
    :ID(_id) {}
 
    virtual CObject* clone() const =0;
    virtual bool belong(int px, int py)=0;
    virtual int leftX()=0;
    virtual int rightX()=0;
 
    int ID;
};
 
class CRectangle: public CObject
{
public:
    CRectangle(int ID,int _x1,int _y1,int _x2,int _y2)
    :CObject(ID), x1(_x1), y1(_y1), x2(_x2), y2(_y2) {}
 
    virtual CObject* clone() const
    {
        return new CRectangle(*this);
    }
 
    virtual bool belong(int x, int y)
    {
        if((x>=x1 && x<=(x2-x1)) && (y>=(y1-y2) && y<=y1))
            return true;
 
        return false;
    }
 
    virtual int leftX()
    {
        return x1;
    }
 
    virtual int rightX()
    {
        return x2;
    }
 
private:
    //верхняя левая координата
    int x1;
    int y1;
 
    //нижняя правая коордианата
    int x2;
    int y2;
};
 
 
class CCircle: public CObject
{
public:
    CCircle(int ID, int _x, int _y, int _r)
    :CObject(ID), x(_x), y(_y), r(_r) {}
 
    virtual CObject* clone() const
    {
        return new CCircle(*this);
    }
 
    virtual bool belong(int px, int py)
    {
        return ((x-px)*(x-px)+(y-py)*(y-py)<=(r*r));
    }
 
    virtual int leftX()
    {
        return x-r;
    }
 
    virtual int rightX()
    {
        return x+r;
    }
 
 
private:
    //координата центра
    int x;
    int y;
 
    //радиус круга
    int r;
};
 
class CTriangle: public CObject
{
public:
    CTriangle(int ID, CCoord _a, CCoord _b, CCoord _c)
    : CObject(ID), a(_a), b(_b), c(_c) {}
 
    virtual CObject* clone() const
    {
        return new CTriangle(*this);
    }
 
    virtual bool belong(int x, int y)
    {
        int k = (a.m_X - x) * (b.m_Y - a.m_Y) - (b.m_X - a.m_X) *  (a.m_Y - y);
        int l = (b.m_X - x) * (c.m_Y - b.m_Y) - (c.m_X - b.m_X ) * (b.m_Y - y);
        int m = (c.m_X - x) * (a.m_Y - c.m_Y) - (a.m_X - c.m_X) *  (c.m_Y - y);
        if ((k >= 0 && l >= 0 && m >= 0) || (k <= 0 && l <= 0 && m <= 0))//(k==l==m==0)
         return true;
 
        return false;
    }
 
    virtual int leftX()
    {
        return a.m_X;
    }
 
    virtual int rightX()
    {
        return c.m_X;
    }
 
private:
    CCoord a;//левая
    CCoord b;//средняя
    CCoord c;//правая
};
 
 
class CPolygon: public CObject
{
public:
    CPolygon(int ID, int n, const CCoord* v)
    : CObject(ID),size(n), coord(new CCoord[size])
    {
        for(int i=0;i<size;i++)
         coord[i]= v[i];
    }
 
    CPolygon(const CPolygon& right)
    :CObject(right.ID), size(right.size), coord(new CCoord[size])
    {
        for(int i=0;i<size;i++)
         coord[i]=right.coord[i];
    }
 
    virtual CObject* clone() const
    {
        return new CPolygon(*this);
    }
 
    virtual int leftX()
    {
        int x=coord[0].m_X;
        for(int i=1;i<size;i++)
         if(coord[i].m_X<x)
          x=coord[i].m_X;
 
        return x;
    }
 
    virtual int rightX()
    {
        int x=coord[0].m_X;
        for(int i=1;i<size;i++)
         if(coord[i].m_X>x)
          x=coord[i].m_X;
 
        return x;
    }
 
 
//    bool 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;
//    }
 
    virtual bool belong(int x, int y)
    {
        int i, crossings = 0;
 
        for ( i = 0; i < size; i++ ) {
 
            double x1 = coord[i].m_X;
            double y1 = coord[i].m_Y;
            double x2 = coord[(i + 1) % size].m_X;
            double y2 = coord[(i + 1) % size].m_Y;
            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;
    }
 
private:
    int size;//сколько координат
 
    //указатель на массив координат
    CCoord* coord;
};
 
 
class CScreen
{
public:
    void Add(const CObject& toAdd)//должна хранить как-то координаты фигуры что дают
    {
        //lst.push_back(toAdd.clone());
    }
 
    void Optimize()
    {
 
    }
 
    //должна вернуть сколько(resLen) фигур пересекают точку x,y и их id(массив res)
    void Test(int x, int y, int resLen, int* res)
    {
//        int size= 100;
//        int realSize= 0;
//
//        //resLen = new int(0);
//        res=new int[size];
//
//        static list<CObject*>:: iterator it=lst.begin();
//        static list<CObject*>:: iterator end= lst.end();
//        while(it!=end)
//        {
//            if((*it)->belong(x,y))
//             res[(*resLen)++]=(*it)->ID;
//            it++;
//        }
 
    }
 
 
private:
//   list<CObject*> lst;
};
 
/*
int main()
{
    int   * res, resLen;
    CScreen  S0;
    S0 . Add ( CRectangle ( 1, 10, 20, 30, 40 ) );
    S0 . Add ( CRectangle ( 2, 20, 10, 40, 30 ) );
    S0 . Add ( CTriangle ( 3, CCoord ( 10, 20 ), CCoord ( 20, 10 ), CCoord ( 30, 30 ) ) );
    S0 . Optimize();
    S0 . Test ( 0, 0, resLen, res );
     // resLen = 0, res = [ ]
    delete [] res;
    S0 . Test ( 21, 21, resLen, res );
     // resLen = 3, res = [ 1 2 3 ]
    delete [] res;
    S0 . Test ( 16, 17, resLen, res );
     // resLen = 1, res = [ 3 ]
    delete [] res;
    S0 . Test ( 30, 22, resLen, res );
     // resLen = 2, res = [ 1 2 ]
    delete [] res;
    S0 . Test ( 35, 25, resLen, res );
     // resLen = 1, res = [ 2 ]
    delete [] res;
 
    CScreen  S1;
    S1 . Add ( CCircle ( 1, 10, 10, 15 ) );
    S1 . Add ( CCircle ( 2, 30, 10, 15 ) );
    S1 . Add ( CCircle ( 3, 20, 20, 15 ) );
    S1 . Optimize();
    S1 . Test ( 0, 0, resLen, res );
     // resLen = 1, res = [ 1 ]
    delete [] res;
    S1 . Test ( 15, 15, resLen, res );
     // resLen = 2, res = [ 1 3 ]
    delete [] res;
    S1 . Test ( 20, 11, resLen, res );
     // resLen = 3, res = [ 1 2 3 ]
    delete [] res;
    S1 . Test ( 32, 8, resLen, res );
     // resLen = 1, res = [ 2 ]
    delete [] res;
 
    CScreen  S2;
    CCoord  vertex1[4] = { CCoord ( 10, 0 ), CCoord ( 20, 20 ), CCoord ( 30, 20 ), CCoord ( 40, 0 ) };
    S2 . Add ( CPolygon ( 1, 4, vertex1 ) );
    CCoord  vertex2[5] = { CCoord ( 20, 10 ), CCoord ( 10, 20 ), CCoord ( 25, 30 ), CCoord ( 40, 20 ), CCoord ( 30, 10 ) };
    S2 . Add ( CPolygon ( 2, 5, vertex2 ) );
    S2 . Optimize();
    S2 . Test ( 25, 15, resLen, res );
     // resLen = 2, res = [ 1 2 ]
    delete [] res;
    S2 . Test ( 25, 25, resLen, res );
     // resLen = 1, res = [ 2 ]
    delete [] res;
    S2 . Test ( 15, 3, resLen, res );
     // resLen = 1, res = [ 1 ]
    delete [] res;
    S2 . Test ( 11, 10, resLen, res );
     // resLen = 0, res = [ ]
    delete [] res;
}*/

Если есть идеи по хранению фигур этих получше - пишите.
castaway
Эксперт С++
4846 / 2985 / 368
Регистрация: 10.11.2010
Сообщений: 11,026
Записей в блоге: 10
Завершенные тесты: 1
12.05.2012, 12:51     Принадлежит ли точка многоугольнику #79
Самую левую и самую правую координаты полигона нужно в конструкторе искать. Зачем ты их ищешь каждый раз при вызове leftX() и rightX() ?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.05.2012, 12:57     Принадлежит ли точка многоугольнику
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
12.05.2012, 12:57  [ТС]     Принадлежит ли точка многоугольнику #80
lazybiz, Потому что хранить я их на данный момент собираюсь в отдельной структуре в классе List, что-то типа
C++
1
2
3
4
5
6
7
struct Elem
{
int lx;
int ly;
CObject* obj;
Elem* next;
}
При создании такой структуры я сделаю по одному вызову leftX() и rightX(). А вот если сделать в CObject ещё доп. поля leftX и rightX да инициализировать их в конструкторе то тогда ведь придётся при поиске лезть к объекту класса вида
obj->leftX. Такой вызов каждый раз, как я понимаю, будет приводить к применению вирт. таблицы (хотя это мне и вовсе не надо) так как в obj может быть и наследник что предположительно будет замедлять работу всего этого. Если я ошибаюсь - поправьте.
Yandex
Объявления
12.05.2012, 12:57     Принадлежит ли точка многоугольнику
Ответ Создать тему
Опции темы

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