Принадлежность точки к полигону

Народ!
Нужен алгорит определения принадлежности точки к полигону.
В полигоне порядка 1000 вершин.
Времени на перебор всех вершин нет.

Спасибо за внимание.

Сообщение отредактировано: vot - 07.11.02, 18:32

А сколько пикселей на экране покрывает такой полигон? Может легче завести вспомогательную картинку с изображением этого полигона закрашенным определенным цветом, а потом проверять какой цвет у выбранной точки...

1) Проводим луч из точки через полигон, если луч пересекает четное число ребер, то не принадлежит, иначе принадлежит.
Хотя надо проверить на пересечение с 1000-1 ребер
2) Вершины нумеруем.
Fi=0;
Проводим луч из точки в 1-ую вершину и считаем угол для поворота в луча во 2-ую вершину если по часовой то с + если против часой то с - и прибавляем к Fi. Повторяем сей шаг по циклу и возвращаемся в 1 вершину.
Если Fi==0, то не принадлежит, иначе принадлежит.
Других базовых методов не знаю.

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

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

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

Моежт еще можно триангуляцию сделать этому полигону? Оптимизировать как-нибудь?

хе:) скажи только какой у тебя полигон, выпуклый ли не выпуклый?
вообще куча методов была в факе по 3d графике, только я урл не помню (на форуме точно урл уже давал, можно попробовать отъюзать поиск)
а если скажешь, какого типа полигон, я тебе так напишу, благо возился с этим немало:)

Полигон произвольный.
А метод с лучем мы уже реализовали, но все равно долго...
Полигон может задаваться точками, линиями(при этом надо искать пересечение)
и аркой. Супер изврат, но как есть...Думали, может как нибудь хитро отсортировать вершины, но пока ничего не вышло...

Я лично вижу один вариант - апроксимация более простой фигурой.
А возможно применить сканирование на плоскости, что-то типа того, что предложили выше с цветным отображением полигона в памяти?

гм, если произвольный, то я знаю только лучем...
вот еслибы выпуклый, или звездчатый... (звездчатый, это когда внутри есть такая точка, отрезки из которой к любой вершине не пересекают границу полигона)

Цитата Cubloid, 19.10.02, 18:46:37

А возможно применить сканирование на плоскости, что-то типа того, что предложили выше с цветным отображением полигона в памяти?

А что это такое?

Цитата S.Yu.Gubanov, 17.10.02, 12:35:34

А сколько пикселей на экране покрывает такой полигон? Может легче завести вспомогательную картинку с изображением этого полигона закрашенным определенным цветом, а потом проверять какой цвет у выбранной точки...

Этот способ действеннен, если есть заранее подготовленные закрашенные полигоны.
Это конечно возможно, но займет пару гигов места... не подходит..
А если в RTM делать, то дольше чем перебором получится..
Все равно придется определять области закраски...