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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.62
asmfreak
0 / 0 / 0
Регистрация: 01.07.2012
Сообщений: 3
#1

Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника - C++

01.07.2012, 02:38. Просмотров 1737. Ответов 10
Метки нет (Все метки)

Здравствуйте!
Я - студент уже второго курса. Пишу для себя и "налетел" на такую вот задачу.
Я не уверен, правильно ли я выбрал форум, ибо задача больше алгоритмическая.

Что есть: Класс - двусвязный список координат точек, составляющих невыпуклый многоугольник.
Задача: Написать функцию, которая определяет, находится ли точка внутри этого невыпуклого многоугольника.
Решения нет. =) По крайней мере у меня.

Если есть какой-либо известный алгоритм, то направьте меня на него, пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.07.2012, 02:38     Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника
Посмотрите здесь:
C++ Найти площадь многоугольника, заданного перечислением координат вершин в порядке обхода его границы
C++ алгоритм линейного поиска заданного ключа
C++ Дан массив упорядоченных по возрастанию целых чисел. разработать алгоритм бинарного поиска заданного числа, результат номер искомого числа или 0 если
C++ Вывести содержимое произвольно заданного файла (не работает программа)
C++ Самый быстрый алгоритм на с++ для поиска изображений с погрешностью
Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат (найти площадь многоугольника) C++
C++ Найти периметр многоугольника, заданного уравнениями сторон
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ramybozy
8 / 8 / 0
Регистрация: 01.07.2012
Сообщений: 138
01.07.2012, 05:47     Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника #2
1) Прежде всего, заключите свой многоугольник (кстати, неважно выпуклый он или нет), ну например в квадрат. Это сделать нетрудно, пройдясь по максимумам и минимумам абсцисс и ординат координат всех точек, являющихся вершинами многоугольника.
2) Далее, на любой из сторон вашего многоугольника выберите произвольно какую-нибудь точку (назовем ее точкой M). А затем через эту точку и через данную точку (назовем ее точкой N) проведите прямую, которая пересечет обрамляющий квадрат в двух точках A и B.
3) Теперь о точке M можно забыть, она уже свою роль сыграла. Теперь начинаем двигаться по прямой AB из точки A в точку B, считая пересечения с контуром нашего многоугольника. Ваша искомая точка N также лежит на этой прямой.
Пусть в данной последовательности (в которой точка A имеет номер 1), точка N имеет номер n. Осталось заметить, что точка N будет лежать внутри искомого многоугольника тогда и только тогда, когда n число четное и большее 2.
asidorchenko
379 / 205 / 25
Регистрация: 09.04.2012
Сообщений: 635
01.07.2012, 06:22     Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника #3
Разбить на треугольники и проверить принадлежность каждому треугольнику.
Разбиение на треугольники неоднозначное. Это называется триангуляцией.

Координат недостаточно, чтобы определить ребра невыпуклого многоульника. Ребро это набор из двух вершин. Информацию о ребрах нужно хранить отдельно!

Многоугольник это граф представляющий множество вершин и ребер. Граф связный. Ребро это связность вершин графа. Алгоритмы на графах.
Catstail
Модератор
22510 / 10915 / 1774
Регистрация: 12.02.2012
Сообщений: 18,061
01.07.2012, 10:01     Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника #4
Алгоритм ramybozy хорош, но есть одна тонкость: может оказаться, что прямая не пересекает, какую-либо сторону, а совпадает с ней. В этом случае нужно чуть сместить точку на квадрате.
darkknight2008
62 / 62 / 6
Регистрация: 16.10.2011
Сообщений: 200
01.07.2012, 11:34     Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника #5
Лучше проверять лежит ли точка по одну сторону от каждой из сторон многоугольника. (Кстати должно работать и для не выпуклого многоугольника)
Van111
кодер с++
208 / 187 / 4
Регистрация: 03.08.2011
Сообщений: 2,597
Записей в блоге: 12
01.07.2012, 11:48     Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника #6
asmfreak, сначала надо определить центр , потом сравнивать каждую точку ребра(сделайте цикл с просчётом расположения точек в ребре с шагом .01 например) с заданной точкой. и отталкиваясь от значения центра, координаты вашей точки должна быть либо больше либо меньше координат точек грани.
asmfreak
0 / 0 / 0
Регистрация: 01.07.2012
Сообщений: 3
01.07.2012, 12:54  [ТС]     Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника #7
asidorchenko, Собственно положение в списке и определяет "связи" координат. А можно по-подробней про триангуляцию? Я почитал вики, но ясней мне от этого не стало. Как "триангулировать" невыпуклый многоугольник?

darkknight2008, Алгоритм с выше/ниже, к сожалению, не работает.

Добавлено через 1 минуту
ramybozy, Мне самому подобные алгоритмы в голову приходили, но, к сожалению, этот метод слишком неопределённый. =(
ramybozy
8 / 8 / 0
Регистрация: 01.07.2012
Сообщений: 138
01.07.2012, 17:28     Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника #8
Как хотите. Вообще этот алгоритм излоден в учебнике Бутузова по геометрии для школьников 7 класса. И для его реализации достаточно знания простеньких формул аналитической геометрии.

И еще, хочу вам дать маленький совет, если вы попытаетесь использовать слишком упрощенный алгоритм для решения данной задачи.
Геометрия говорит нам, что существуют невыпуклые многоугольники, у которых имеются внутренние точки, которые не видны не из одной из его вершины. Это к тому, чтобы вы не пытались строить решение, тривильно соединяя искомую точку со всеми вершинами многоугольника.
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
01.07.2012, 17:50     Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника #9
Как то решал уже тут на форуме для кого то подобную задачу, сохранил исходник, думаю поможет:
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;
}
Здесь в качестве хранения вершин выступает простой двумерный массив arr[ size ][ 2 ]. Где size - это количестве вершин. Соответственно в arr[ i ][ 0 ] хранится x-координата вершины, а в arr[ i ][ 1 ] y-координата. Так же вершины должны быть упорядочены.
В основной функции вычисляется расстояние от точки до i-го ребра, если точка находится на ребре то сразу возвращается true. Иначе ищется пересечение луча, исходящего из данной точки, с этим ребром. В конечном итоге, если точка не лежит ни на одном из ребер, проверяется количество пересечений, если оно не четное - значит точка находится внутри многоугольника, иначе снаружи.
jdbaha
0 / 0 / 0
Регистрация: 14.03.2012
Сообщений: 7
02.07.2012, 23:33     Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника #10
закрась многоугольник в 1 цвет, а снаружи многоугольника в другой. и считывай цвета точек которые ты задаешь. делал подобное правда в делфи
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2012, 19:00     Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника
Еще ссылки по теме:
C++ Найти периметр многоугольника заданного координатами вершин
C++ Алгоритм Габова для поиска максимального паросочетания в произвольном графе за O(V^3)
C++ Алгоритм для поиска всех путей между 2 вершинами графа
Алгоритм построчного заполнения многоугольника с использованием затравочного пикселя C++
Найдите самую длинную диагональ многоугольника, заданного координатами своих вершин на плоскости C++

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

Или воспользуйтесь поиском по форуму:
asmfreak
0 / 0 / 0
Регистрация: 01.07.2012
Сообщений: 3
06.07.2012, 19:00  [ТС]     Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника #11
Спасибо всем!

Модератором/администраторам!
Я думаю, что можно закрыть тему. Спасибо!
Yandex
Объявления
06.07.2012, 19:00     Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника
Ответ Создать тему
Опции темы

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