С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

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

Если есть какой-либо известный алгоритм, то направьте меня на него, пожалуйста.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.07.2012, 02:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм поиска внутренних координат для произвольно заданного невыпуклого многоугольника (C++):

Найти площадь многоугольника, заданного перечислением координат вершин в порядке обхода его границы - C++
Найти площадь многоугольника, заданного перечислением координат вершин в порядке обхода его границы.

алгоритм линейного поиска заданного ключа - C++
как то странно считает номер...или я что-то не дописал ((( #include <iostream> #include <ctime> using namespace std; const int...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab () { int s1 = 0; int s2 =...

Дан массив упорядоченных по возрастанию целых чисел. разработать алгоритм бинарного поиска заданного числа, результат номер искомого числа или 0 если - C++
помогите решить задачу: Дан массив упорядоченных по возрастанию целых чисел. разработать алгоритм бинарного поиска заданного числа,...

Вывести содержимое произвольно заданного файла (не работает программа) - C++
Эта программа по идее должна выводить на экран содержимое произвольно заданного файла, компилируется без ошибок, но содержимое файла...

Самый быстрый алгоритм на с++ для поиска изображений с погрешностью - C++
Подскажите самый быстрый алгоритм для поиска одного изображения на другом с погрешностью. То есть загружается два изображения и происходит...

10
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.
0
asidorchenko
379 / 205 / 25
Регистрация: 09.04.2012
Сообщений: 635
01.07.2012, 06:22 #3
Разбить на треугольники и проверить принадлежность каждому треугольнику.
Разбиение на треугольники неоднозначное. Это называется триангуляцией.

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

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

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

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

И еще, хочу вам дать маленький совет, если вы попытаетесь использовать слишком упрощенный алгоритм для решения данной задачи.
Геометрия говорит нам, что существуют невыпуклые многоугольники, у которых имеются внутренние точки, которые не видны не из одной из его вершины. Это к тому, чтобы вы не пытались строить решение, тривильно соединяя искомую точку со всеми вершинами многоугольника.
0
Toshkarik
1147 / 864 / 51
Регистрация: 03.08.2011
Сообщений: 2,404
Завершенные тесты: 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. Иначе ищется пересечение луча, исходящего из данной точки, с этим ребром. В конечном итоге, если точка не лежит ни на одном из ребер, проверяется количество пересечений, если оно не четное - значит точка находится внутри многоугольника, иначе снаружи.
1
jdbaha
0 / 0 / 0
Регистрация: 14.03.2012
Сообщений: 7
02.07.2012, 23:33 #10
закрась многоугольник в 1 цвет, а снаружи многоугольника в другой. и считывай цвета точек которые ты задаешь. делал подобное правда в делфи
0
asmfreak
0 / 0 / 0
Регистрация: 01.07.2012
Сообщений: 3
06.07.2012, 19:00  [ТС] #11
Спасибо всем!

Модератором/администраторам!
Я думаю, что можно закрыть тему. Спасибо!
0
06.07.2012, 19:00
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2012, 19:00
Привет! Вот еще темы с ответами:

Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат (найти площадь многоугольника) - C++
Здравствуйте форумчане! Необходим совет) собственно задача: Многоугольник на плоскости задан целочисленными координатами своих N...

Найти периметр многоугольника заданного координатами вершин - C++
1)Координаты вершин многоугольника заданы массивами {Xi,Yi}, i=1,2,…,n Считается, что вершины упорядочены в порядке обхода по часовой...

Найти периметр многоугольника, заданного уравнениями сторон - C++
Помогите пожалуйста с решением задачи! Я кое-что уже написала, но ничего не работает. Самой разобраться в коде не получается. Подскажите...

Алгоритм для поиска всех путей между 2 вершинами графа - C++
Здравствуйте, возник вопрос какой алгоритм необходимо использовать для поиска всех путей, между 2 вершинами графа.


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

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

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