1186 / 542 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
|
|
1 | |
Принадлежит ли точка многоугольнику10.05.2012, 18:01. Показов 30570. Ответов 86
Метки нет (Все метки)
Нужен такой вот алгоритм (а ещё лучше функция ).Поиск по форуму не увенчался успехом (темы есть , но кода нет). Вершины многоугольника не пересекаются. Помогите пожалуйста.
0
|
10.05.2012, 18:01 | |
Ответы с готовыми решениями:
86
Принадлежит ли точка выпуклому многоугольнику Определить, принадлежит ли точка многоугольнику по координатам в координатной плоскости Дана точка М(x, y). Присвоить z = 1, если точка принадлежит окружности с радиусом R и центром в точке (a, b) и z = 0 в противном случае. Даны отрезки [a, b] и [c, d] и точка A с координатой х. Определить, принадлежит ли данная точка одному из этих отрезков, обоим или лежит вне их |
30 / 30 / 12
Регистрация: 15.11.2009
Сообщений: 148
|
||||||
10.05.2012, 18:36 | 2 | |||||
вот так написал
0
|
594 / 532 / 76
Регистрация: 22.03.2011
Сообщений: 1,585
|
|
10.05.2012, 18:47 | 3 |
Gepar,
почитай http://ru.wikipedia.org/wiki/%... 0%BA%D1%83 ... там есть метод суммы углов.. но это как я понимаю тоже только для плоскости... метод с бесконечным лучем (в плоскости): 1. берешь любую точку лежающую на любой прямой образующей фигуру 2. проводишь луч из исходной точки в эту точку .. продолжаешь его очень далеко (в бесконечность типа) 3. смотришь сколько раз луч пересекает фигуру (пересечение 2-х отрезков с каждой из прямых составляющих фигуру) - если количество пересечений четное - точка внутри фигуры. нечетное - вне фигуры... к пространству хз.... Добавлено через 17 секунд ser4ega, лол втф
0
|
30 / 30 / 12
Регистрация: 15.11.2009
Сообщений: 148
|
|
10.05.2012, 19:22 | 4 |
OstapBender, это мой топорный метод. Прямоугольник там задан 4мя точками, и большая проверка. Я по рисунку смотрел своему=)
0
|
1186 / 542 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
|
|
10.05.2012, 19:23 [ТС] | 5 |
Забыл предупредить: у меня на плоскости, никаких 3д не надо. Только 2д координаты.
ser4ega, но у многоугольников же количество углов = n. Функция которая принимает фиксированное число углов не подходит. Мне необходима функция которая примет координаты точки (x,y), а потом количество точек (size) и массив точек многоугольника ну и ответит попадает ли точка в многоугольник или нет. OstapBender, википедия не помогает, там слишком сложно всё: там какие-то хитрые 3д многоугльники с учётом количества оборотов ... Мне бы несколько попроще.
0
|
30 / 30 / 12
Регистрация: 15.11.2009
Сообщений: 148
|
|
10.05.2012, 19:25 | 6 |
надо еще добавить защиту от деления на 0, на случай, если прямоугольник лежит горизонтально.
И проверки немного изменить, на этот же случай Добавлено через 59 секунд Сорь, я подумал почему-то про прямоугольник. СЕЙЧАС ПЕРЕПИШУ
0
|
1186 / 542 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
|
||||||
10.05.2012, 19:25 [ТС] | 7 | |||||
ser4ega, с вычислением попадания точки в прямоугольник у меня проблем не возникло, там всё просто
0
|
594 / 532 / 76
Регистрация: 22.03.2011
Сообщений: 1,585
|
|
10.05.2012, 19:28 | 8 |
Gepar, проще не выйдет.... со сложными фигурами только так ...
попробуй реализовать метод с бесконечным лучем, он же не сложный.
0
|
30 / 30 / 12
Регистрация: 15.11.2009
Сообщений: 148
|
|
10.05.2012, 19:33 | 9 |
Gepar, как работает твой код? Я не понимат
0
|
1186 / 542 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
|
|
10.05.2012, 19:52 [ТС] | 10 |
ser4ega, там где 1 и 2 должно быть y1 и y2.
OstapBender, так нету там такого на вики. Приведите пожалуйста пример
0
|
30 / 30 / 12
Регистрация: 15.11.2009
Сообщений: 148
|
||||||
10.05.2012, 19:54 | 11 | |||||
так вот?
Gepar, у тебя прямоугольник получается всегда горизонтальный - не катит
1
|
1186 / 542 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
|
||||||
10.05.2012, 20:18 [ТС] | 12 | |||||
ser4ega, ну вообще надо как-то так:
Добавлено через 1 минуту Да я вот тоже засомневался, а не будет ли у меня какой другой прямоугольник .... Наверное надо разбивать его на два треугольника и смотреть на принадлежность им. Ну да сейчас бы проблему с многоугольником решить ...
0
|
10.05.2012, 20:33 | 13 |
Gepar, у вас многоугольник выпуклый?
0
|
594 / 532 / 76
Регистрация: 22.03.2011
Сообщений: 1,585
|
|||||||||||
10.05.2012, 21:01 | 14 | ||||||||||
Gepar, я ж тебе алгоритм написал...
короче начал я делать... имхо все должно работать. но есть 1 НО. нет нормальной функции пересечения отрезков, с этим дополнительно придется морочиться... 2 что я нашел в инете выдают неверный результат. КОД ЕПТ
функции из инета: ...
в общем мне чесно говоря надоело, может через час вернусь к этому
1
|
1186 / 542 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
|
||||||
10.05.2012, 21:18 [ТС] | 15 | |||||
Нашёл алгоритм, непонятно только рабочий ли он
HighPredator, да неизвестно чего там тыкать за многоугольники будут. Наверное все подряд так что упростить задачу до определения только выпуклых нельзя. Добавлено через 8 минут Не работает тот алгоритм что нашёл
0
|
30 / 30 / 12
Регистрация: 15.11.2009
Сообщений: 148
|
|
10.05.2012, 21:20 | 16 |
Gepar, а мой работает?
Должон работать, пусть я там и не использовал коорд, дела это не меняет, если работает - для двумерного пространства разобрались
1
|
1186 / 542 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
|
|
10.05.2012, 21:20 [ТС] | 17 |
Самому уже надоело, бесить вот начинает, но сделать надо. Беда ещё в том что это не основная задача, основная задача хранить это дело как-то и искать оптимально быстро в какие фигуры точка попадает ... но этот вопрос я уже поставил в другой теме, жаль что там никто так и не отписался.
Помогите пожалуйста с этим алгоритмом попадания точки в многоугольник, я не сильно понял то описание что на вики, мне бы функцию ...
0
|
30 / 30 / 12
Регистрация: 15.11.2009
Сообщений: 148
|
|
10.05.2012, 21:31 | 18 |
Gepar, подумай над случаем прохождения луча через вершину, и еще вероятностью нахождения луча на ребре или точки на ребре. Это тяжелее оказалось
1
|
1186 / 542 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
|
|||||||||||
10.05.2012, 21:37 [ТС] | 19 | ||||||||||
Эм, я удивлён, но работает Только мне непонятно вовсе как оно работает, но работает, но тут тоже не всё гладко: попадение на пересечение оно отбрасывает, тоесть для прямоугольника:
Добавлено через 4 минуты Погонял ещё - и правда пока справляется. В том числе и со всякими пятиугольниками вроде этого
0
|
30 / 30 / 12
Регистрация: 15.11.2009
Сообщений: 148
|
||||||
10.05.2012, 22:01 | 20 | |||||
Вот. Что делать с вершиной не знаю. Думаю) Как ты там?
0
|
10.05.2012, 22:01 | |
Помогаю со студенческими работами здесь
20
Определить принадлежит точка точка координатам Принадлежит ни точка кольцу (на C) Принадлежит ли точка прямоугольнику? Принадлежит ли точка графику Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |