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

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

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

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

10.05.2012, 18:01. Просмотров 10366. Ответов 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
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
1177 / 533 / 20
Регистрация: 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
27 / 27 / 3
Регистрация: 15.11.2009
Сообщений: 143
11.05.2012, 00:22 #48
ПЛЯЯЯЯЯЯЯЯ!! Тока допер, что нельзя однозначно по точкам задать многоугольник.
Что делать-то теперь?

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

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

Добавлено через 46 секунд
на то он и бесконечный луч)
1
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 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 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 01:05 #55
Цитата Сообщение от Toshkarik Посмотреть сообщение
const int **arr
это как использовать ...
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
11.05.2012, 01:06 #56
Цитата Сообщение от OstapBender Посмотреть сообщение
это как использовать ...
Как двумерный массив, как же еще. Передается указатель на массив указателей на константные данные.
0
OstapBender
584 / 523 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 01:08 #57
Toshkarik, ну приведи пример чтоли
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
11.05.2012, 01:10 #58
В функции же используется. Какой еще нужен пример?
0
OstapBender
584 / 523 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
11.05.2012, 01:11 #59
Toshkarik, пример вызова функции.
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 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
Привет! Вот еще темы с ответами:

Принадлежит ли точка четырехугольнику. - 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) - координаты точки. Определить, принадлежит ли...


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

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

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