Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.55/65: Рейтинг темы: голосов - 65, средняя оценка - 4.55
Gepar
1181 / 537 / 77
Регистрация: 01.07.2009
Сообщений: 3,517
#1

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

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

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

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

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

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

Определить принадлежит точка точка координатам
Такая задача даны действительные числа x y определить принадлежит точка ...

Принадлежит ли точка четырехугольнику?
Подскажите пожалуйста, как можно по проще проверить лежит ли заданная точка (x,...

86
Toshkarik
1149 / 866 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 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
1
OstapBender
584 / 523 / 75
Регистрация: 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.
0
Gepar
1181 / 537 / 77
Регистрация: 01.07.2009
Сообщений: 3,517
10.05.2012, 23:45  [ТС] #43
OstapBender, что-то я в вашем коде потерялся: почему 3х мерное пространство? почему LinesIntersect принимает 4 координаты? Что в main вообще происходит? Почему часть кода си, а часть с++ (printf,а рядом потоки cin/cout)? Похоже что в main часть каких-то вычислений ещё, но почему они в main, а не в функциях по вычислениях.

Добавлено через 3 минуты
Toshkarik, наверное всё же нужна функция. Помогите с её написанием пожалуйста. Я вижу я уже окончательно запутался со всеми этими методами обходов вершин многоугольников ...
0
ser4ega
28 / 28 / 12
Регистрация: 15.11.2009
Сообщений: 147
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;
     }
0
Gepar
1181 / 537 / 77
Регистрация: 01.07.2009
Сообщений: 3,517
10.05.2012, 23:57  [ТС] #45
Цитата Сообщение от ser4ega Посмотреть сообщение
Когда я писал, я думал, что координаты вершин в массиве хранятся последовательно.
Ну они последовательно хранятся. Только неизвестно в какую сторону они пойдут: слева-направо, или справа-налево. Тоесть тот же мой домик может рисоваться начиная как с нижних точек(20,10 или 30,10) так и с верхней (25,30).
0
OstapBender
584 / 523 / 75
Регистрация: 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 вершины...
0
Gepar
1181 / 537 / 77
Регистрация: 01.07.2009
Сообщений: 3,517
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 например.
0
ser4ega
28 / 28 / 12
Регистрация: 15.11.2009
Сообщений: 147
11.05.2012, 00:22 #48
ПЛЯЯЯЯЯЯЯЯ!! Тока допер, что нельзя однозначно по точкам задать многоугольник.
Что делать-то теперь?

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

как я понял, вариант единственнен только для выпуклых фигур, мафака !!
0
Gepar
1181 / 537 / 77
Регистрация: 01.07.2009
Сообщений: 3,517
11.05.2012, 00:26  [ТС] #49
ser4ega, почему это? Вполне можно же , каждая точка сводится с предыдущей. Последняя сводится с первой. То что они не пересекаются задано условием. Всё ок с рисованием многоугольника, не ок с определением вхождения точки ...
0
OstapBender
584 / 523 / 75
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 00:28 #50
Gepar, ну простите БОСС ___))
Цитата Сообщение от Gepar Посмотреть сообщение
А это псевдо уход в бесконечность я так понимаю?
точно. для отладки и 500 норм.
0
ser4ega
28 / 28 / 12
Регистрация: 15.11.2009
Сообщений: 147
11.05.2012, 00:32 #51
я это к тому, что теперь реально важен порядок следования точек в массиве
0
Gepar
1181 / 537 / 77
Регистрация: 01.07.2009
Сообщений: 3,517
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 для всех точек многоугольника чтобы определить самую большую координату тоже не очень то хорошо так как это тоже занимает время ... ну да завтра нужно будет решиться со всем этим.
0
OstapBender
584 / 523 / 75
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 00:48 #53
Gepar, а вот и не угадал.
задашь 999999 и всё будет ок.

Добавлено через 46 секунд
на то он и бесконечный луч)
1
Toshkarik
1149 / 866 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 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-координата отрезка, с которым ищем пересечение.
1
OstapBender
584 / 523 / 75
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 01:05 #55
Цитата Сообщение от Toshkarik Посмотреть сообщение
const int **arr
это как использовать ...
0
Toshkarik
1149 / 866 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
11.05.2012, 01:06 #56
Цитата Сообщение от OstapBender Посмотреть сообщение
это как использовать ...
Как двумерный массив, как же еще. Передается указатель на массив указателей на константные данные.
0
OstapBender
584 / 523 / 75
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 01:08 #57
Toshkarik, ну приведи пример чтоли
0
Toshkarik
1149 / 866 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 1
11.05.2012, 01:10 #58
В функции же используется. Какой еще нужен пример?
0
OstapBender
584 / 523 / 75
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 01:11 #59
Toshkarik, пример вызова функции.
0
Toshkarik
1149 / 866 / 90
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 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 ))
   //делаем что то
0
11.05.2012, 01:13
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.05.2012, 01:13

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

Принадлежит ли точка четырехугольнику.
Надеюсь на помощь форумчан: Задача следующяя: задана коодинатами точек...

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


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

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

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