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

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: [habrahabr] Алгоритм определения попадания точки в контур  (Прочитано 21324 раз)
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.

там парни просто математику расписали, но для прикладного программинга все это уже давно реализовано.
Записан

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 » new

на практике,

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

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

ru
Offline Offline

« Ответ #5 : 06-08-2011 15:20 » 

на практике...
круто, работает Улыбаюсь

* Inner.exe (9.5 Кб - загружено 1036 раз.)
Записан
PooH
Глобальный модератор

ru
Offline Offline
Пол: Мужской
... и можно без хлеба!


« Ответ #6 : 07-08-2011 12:32 » 

у многих задач есть "заморочки" Улыбаюсь



Причем метод "лучей" даст такой же результат. А вот что даст описанный в статье алгоритм - не знаю. "Тонкость" возникает когда регион сам себе пересекает. Получается, что пересение исключается из региона - надо исключать или нет - вопрос Улыбаюсь

* 1.JPG (13.92 Кб - загружено 2834 раз.)
* 2.jpg (15.37 Кб - загружено 2798 раз.)
« Последнее редактирование: 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 объектов Отлично

Так что, такой общий случай не нужен, а полигон считать всегда многоугольником, который вырезан из жёсткой пластины (при самопересечениях такой автоматически развалится на несколько многоугольников)
Записан

Dmitry
Помогающий

ru
Offline Offline

« Ответ #10 : 08-08-2011 20:40 » 

Алексей1153++, Я так и написал, что не бывает Ага
Конечно, нет смысла перегружать алгоритм из-за таких извращений.
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines