Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
     
  Галерея  
  Весельчак У  
  Наша Вики  
  Хранилище  
  Проекты  
     
Правила
     
  Правила форума Правила русского языка  
     
Помощь Поиск Календарь Почта Войти Регистрация  
Форум программистов «Весельчак У» > Программирование > Общий > Алгоритмы и математические задачи. (Модераторы: nikedeforest, Вад) > Тема: [habrahabr] Алгоритм определения попадания точки в контур
 
Страниц: [1]   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: [habrahabr] Алгоритм определения попадания точки в контур  (Прочитано 22952 раз)
0 Пользователей и 1 Гость смотрят эту тему.
baldr
Команда клуба

cy
Offline Offline
Пол: Мужской
Дорогие россияне


WWW
« : 01-08-2011 14:46 » 
На хабре вышла статья - возможно, заинтересует кого-то у нас. Тут много было похожих обсуждений.

http://habrahabr.ru/blogs/algorithm/125356/

Алгоритм определения попадания точки в контур на основе комплексного анализа
Записан
Приличный компьютер всегда будет стоить дороже 1000 долларов, потому что 500 долларов - это не вполне прилично
x77
Команда клуба

ro
Offline Offline
Пол: Мужской
меняю стакан шмали на обратный билет с Марса.
« Ответ #1 : 05-08-2011 15:37 » 
на практике,

1. задаем регион (CreatePolyRgn, например)
2. юзаем PtInRgn.

там парни просто математику расписали, но для прикладного программинга все это уже давно реализовано.
Записан
я люблю shelek.ru
baldr
Команда клуба

cy
Offline Offline
Пол: Мужской
Дорогие россияне


WWW
« Ответ #2 : 06-08-2011 06:00 » 
x77, да, но для некоторых языков нет функции PtInRgn()...
Записан
Приличный компьютер всегда будет стоить дороже 1000 долларов, потому что 500 долларов - это не вполне прилично
гайка
Гость
« Ответ #3 : 06-08-2011 07:21 » 
Ага, к тому же всегда полезно знать, как выглядит изнутри то, с чем ты работаешь. не обязательно, но полезно...
Записан
LifeMaker
Гость
« Ответ #4 : 06-08-2011 09:24 » 
Цитата: x77 от 05-08-2011 15:37
на практике,

1. задаем регион (CreatePolyRgn, например)
2. юзаем PtInRgn.

там парни просто математику расписали, но для прикладного программинга все это уже давно реализовано.
практика бывает сильно разная.
бывает linux, бывает macos в конце концов
Записан
Dmitry
Помогающий

ru
Offline Offline
« Ответ #5 : 06-08-2011 15:20 » 
Цитата: x77 от 05-08-2011 15:37
на практике...
круто, работает Улыбаюсь
* Inner.exe (9.5 Кб - загружено 1125 раз.)
Записан
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!
« Ответ #6 : 07-08-2011 12:32 » 
у многих задач есть "заморочки" Улыбаюсь



Причем метод "лучей" даст такой же результат. А вот что даст описанный в статье алгоритм - не знаю. "Тонкость" возникает когда регион сам себе пересекает. Получается, что пересение исключается из региона - надо исключать или нет - вопрос Улыбаюсь
* 1.JPG (13.92 Кб - загружено 2954 раз.)
* 2.jpg (15.37 Кб - загружено 2922 раз.)
« Последнее редактирование: 07-08-2011 12:37 от PooH » Записан
Удачного всем кодинга! -=x[PooH]x=-
Dmitry
Помогающий

ru
Offline Offline
« Ответ #7 : 07-08-2011 13:55 » 
Да, получается, что точка лежит внутри региона, если регион покрывает эту точку нечётное количество раз. По-идее, чтобы регион сам себя перекрывал - такого в природе не бывает Улыбаюсь Т.е. регион надо представлять в виде региона-внешнего контура и регионов-дырок. Тогда проблем никаках не будет. Алгоритм приведение региона к такому виду представляю, за исключением одного момента - при обходе надо как-то определить, с какой стороны у нас внутренняя часть.
Записан
baldr
Команда клуба

cy
Offline Offline
Пол: Мужской
Дорогие россияне


WWW
« Ответ #8 : 08-08-2011 06:31 » 
Я даже из рисунка сам не могу определить где внутренняя часть Жаль
Записан
Приличный компьютер всегда будет стоить дороже 1000 долларов, потому что 500 долларов - это не вполне прилично
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13
« Ответ #9 : 08-08-2011 18:23 » 
baldr, Dmitry, PooH, на самом деле таких полигонов в природе компутере не бывает. Вернее, их не допустят дизайнеры 3D объектов Отлично

Так что, такой общий случай не нужен, а полигон считать всегда многоугольником, который вырезан из жёсткой пластины (при самопересечениях такой автоматически развалится на несколько многоугольников)
Записан
>FAQ ПО ПРОГР.
>ССЫЛКИ ПО ПРОГР.
>Правила"Неотложки"
Dmitry
Помогающий

ru
Offline Offline
« Ответ #10 : 08-08-2011 20:40 » 
Алексей1153++, Я так и написал, что не бывает Ага
Конечно, нет смысла перегружать алгоритм из-за таких извращений.
Записан
Страниц: [1]   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Форум программистов «Весельчак У» > Программирование > Общий > Алгоритмы и математические задачи. (Модераторы: nikedeforest, Вад) > Тема: [habrahabr] Алгоритм определения попадания точки в контур

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines