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

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

на практике,

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

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

ru
Offline Offline

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

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

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

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


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

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



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

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

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

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines