Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94306 Mon, 28 Oct 2002 20:21:47 +0000 Принадлежность точки к полигону https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94306 Это конечно возможно, но займет пару гигов места... не подходит..
А если в RTM делать, то дольше чем перебором получится..
Все равно придется определять области закраски...
]]> Muran Алгоритмы https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94305 Thu, 24 Oct 2002 08:23:24 +0000 Принадлежность точки к полигону https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94305 Цитата S.Yu.Gubanov, 17.10.02, 12:35:34
А сколько пикселей на экране покрывает такой полигон? Может легче завести вспомогательную картинку с изображением этого полигона закрашенным определенным цветом, а потом проверять какой цвет у выбранной точки...

]]> Cubloid Алгоритмы https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94304 Wed, 23 Oct 2002 16:39:36 +0000 Принадлежность точки к полигону https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94304 Цитата Cubloid, 19.10.02, 18:46:37
А возможно применить сканирование на плоскости, что-то типа того, что предложили выше с цветным отображением полигона в памяти?


А что это такое?
]]> Muran Алгоритмы https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94303 Sun, 20 Oct 2002 19:05:27 +0000 Принадлежность точки к полигону https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94303 вот еслибы выпуклый, или звездчатый... (звездчатый, это когда внутри есть такая точка, отрезки из которой к любой вершине не пересекают границу полигона)]]> Demo_S Алгоритмы https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94302 Sat, 19 Oct 2002 14:46:37 +0000 Принадлежность точки к полигону https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94302 А возможно применить сканирование на плоскости, что-то типа того, что предложили выше с цветным отображением полигона в памяти?]]> Cubloid Алгоритмы https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94301 Sat, 19 Oct 2002 13:04:38 +0000 Принадлежность точки к полигону https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94301 А метод с лучем мы уже реализовали, но все равно долго...
Полигон может задаваться точками, линиями(при этом надо искать пересечение)
и аркой. Супер изврат, но как есть...Думали, может как нибудь хитро отсортировать вершины, но пока ничего не вышло...]]> Muran Алгоритмы https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94300 Thu, 17 Oct 2002 20:00:21 +0000 Принадлежность точки к полигону https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94300 вообще куча методов была в факе по 3d графике, только я урл не помню (на форуме точно урл уже давал, можно попробовать отъюзать поиск)
а если скажешь, какого типа полигон, я тебе так напишу, благо возился с этим немало:)]]> Demo_S Алгоритмы https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94299 Thu, 17 Oct 2002 13:36:57 +0000 Принадлежность точки к полигону https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94299 Хотя надо проверить на пересечение с 1000-1 ребер :(
2) Вершины нумеруем.
Fi=0;
Проводим луч из точки в 1-ую вершину и считаем угол для поворота в луча во 2-ую вершину если по часовой то с + если против часой то с - и прибавляем к Fi. Повторяем сей шаг по циклу и возвращаемся в 1 вершину.
Если Fi==0, то не принадлежит, иначе принадлежит.
Других базовых методов не знаю.

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

В качестве второго приближения можно построить выпуклую оболочку на вершинах прямоугольника.
Но не знаю на сколько быстро можно это сделать.
И опять применить 1 или 2 способ.
При чем в первом способе заведомо будет либо 1 либо 2 точки пересечения.

Или еще вариант оставить от полигона каждую 10 вершину и применить любой способ. А потом каждую например 9 и так пока результат например 3 раза не изменится. Ну это вообще моя личная глупость...

Моежт еще можно триангуляцию сделать этому полигону? Оптимизировать как-нибудь?]]> Cubloid Алгоритмы https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94298 Thu, 17 Oct 2002 08:35:34 +0000 Принадлежность точки к полигону https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94298 S.Yu.Gubanov Алгоритмы https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94297 Thu, 17 Oct 2002 08:19:51 +0000 Принадлежность точки к полигону https://forum.sources.ru/index.php?showtopic=9811&view=findpost&p=94297 Нужен алгорит определения принадлежности точки к полигону.
В полигоне порядка 1000 вершин.
Времени на перебор всех вершин нет.

Спасибо за внимание.]]> Muran Алгоритмы