На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Принадлежность точки к полигону
    Народ!
    Нужен алгорит определения принадлежности точки к полигону.
    В полигоне порядка 1000 вершин.
    Времени на перебор всех вершин нет.

    Спасибо за внимание.
    Сообщение отредактировано: vot -
      А сколько пикселей на экране покрывает такой полигон? Может легче завести вспомогательную картинку с изображением этого полигона закрашенным определенным цветом, а потом проверять какой цвет у выбранной точки...
        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 делать, то дольше чем перебором получится..
                      Все равно придется определять области закраски...
                      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                      0 пользователей:


                      Рейтинг@Mail.ru
                      [ Script execution time: 0,0248 ]   [ 15 queries used ]   [ Generated: 21.05.24, 07:50 GMT ]