Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Общие вопросы Delphi
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 01.12.2006, 21:05   #1
LevioFUN
 
Регистрация: 25.11.2006
Сообщений: 4
По умолчанию принадлежность точки многоугольнику

Задача:
есть многоугольник (последовательно заданы координаты всех вершин в порядке обхода (X[i],y[i])) и точка (x0,y0)

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


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

интересует другое - этот алгоритм довольно долог и сложен в реализации (ну может и не очень канечно =) ) может
ктонибудь подскажет другой алгоритм?

ЗЫ интересует алгоритм, код я и сам наваяю ...

Последний раз редактировалось LevioFUN; 01.12.2006 в 21:09. Причина: арфаграфия...
LevioFUN вне форума Ответить с цитированием
Старый 01.12.2006, 21:12   #2
AVer
Андрей
Форумчанин
 
Аватар для AVer
 
Регистрация: 21.11.2006
Сообщений: 457
По умолчанию

знаешь рассчет площади треугольника по формуле верона (или герона не помню точно...)? так вот. находишь площадь треугольника в многоугольнике находяшегося ближе всего к точке (пусть точки этого треугольника х1,х2,х3, где х2 "выпирающий" угол, т.е. х1,х3 - основание) и площадь треугольника х1,х3,х4 (х4 - координаты точки). если 2 площадь больше, то точка не пренадлежит треугольнику. мудро...
ICQ: 5311314
[SIGPIC][/SIGPIC]
AVer вне форума Ответить с цитированием
Старый 01.12.2006, 21:17   #3
LevioFUN
 
Регистрация: 25.11.2006
Сообщений: 4
По умолчанию

1.) Герона...
2.) "находяшегося ближе всего к точке" - ?
3.) x1,x2,x3 - точки много-ка? (последовательные или могут с "перескоком"?)
LevioFUN вне форума Ответить с цитированием
Старый 01.12.2006, 21:24   #4
AVer
Андрей
Форумчанин
 
Аватар для AVer
 
Регистрация: 21.11.2006
Сообщений: 457
По умолчанию

смотри вложение. немного коряво, потому что делал быстро.
Изображения
Тип файла: jpg Schema.jpg (8.2 Кб, 198 просмотров)
ICQ: 5311314
[SIGPIC][/SIGPIC]
AVer вне форума Ответить с цитированием
Старый 01.12.2006, 21:26   #5
SuperVisor
Павел Сергеевич
Форумчанин
 
Регистрация: 05.11.2006
Сообщений: 665
По умолчанию

Советую реализовать все гораздо проще: знаешь Canvas? Рисуешь белый квадрат, на нем черный многоугольник и проверяешь цвет твоей точки
Познавая других, мы познаем себя.
С'est la vie...
SuperVisor вне форума Ответить с цитированием
Старый 01.12.2006, 21:26   #6
LevioFUN
 
Регистрация: 25.11.2006
Сообщений: 4
По умолчанию

AVer
а почему для точки х4 выбран именно тр-к х1х2х3? как определить с каким тр-ом сравнивать?

SuperVisor
хм...это конечно может помочь...=\
надо подумать... но задачка все равно остается =)
я с ней давно сталкнулся, а счас вот захотелось придумать чейнить...

Последний раз редактировалось zetrix; 02.12.2006 в 09:06.
LevioFUN вне форума Ответить с цитированием
Старый 01.12.2006, 21:30   #7
AVer
Андрей
Форумчанин
 
Аватар для AVer
 
Регистрация: 21.11.2006
Сообщений: 457
По умолчанию

SuperVisor
Цитата:
Советую реализовать все гораздо проще: знаешь Canvas? Рисуешь белый квадрат, на нем черный многоугольник и проверяешь цвет твоей точки
Это классическое pascal-решение. Просто нам такую же задавали....

LevioFUN
Измеряешь расстояние до точек. Самая ближняя - х3, и соответственно 2 к ней ближние - х1 и х3.
ICQ: 5311314
[SIGPIC][/SIGPIC]

Последний раз редактировалось AVer; 01.12.2006 в 21:33.
AVer вне форума Ответить с цитированием
Старый 01.12.2006, 21:34   #8
LevioFUN
 
Регистрация: 25.11.2006
Сообщений: 4
По умолчанию

AVer
хм... все хорошо но много-к может быть "впуклым"...

да и с выпуклыми не проходит =\
Изображения
Тип файла: jpg example.jpg (28.0 Кб, 170 просмотров)

Последний раз редактировалось LevioFUN; 01.12.2006 в 21:45.
LevioFUN вне форума Ответить с цитированием
Старый 01.12.2006, 21:40   #9
AVer
Андрей
Форумчанин
 
Аватар для AVer
 
Регистрация: 21.11.2006
Сообщений: 457
По умолчанию

Ну тогда делай как говорит SuperVisor. Самое простое и быстрое решение в Delphi.
ICQ: 5311314
[SIGPIC][/SIGPIC]
AVer вне форума Ответить с цитированием
Старый 01.12.2006, 21:42   #10
SuperVisor
Павел Сергеевич
Форумчанин
 
Регистрация: 05.11.2006
Сообщений: 665
По умолчанию

Цитата:
Сообщение от AVer Посмотреть сообщение
Это классическое pascal-решение. Просто нам такую же задавали....
"5. Не придумывай велосипед. Тут опять действует созидательная функция хакеров. Они не должны стоять на месте и обязаны делиться своими знаниями. Например, вы написали какой-то уникальный код, поделитесь им с другими, чтобы людям не пришлось создавать то же самое. Вы можете не выдавать все секреты, но должны помогать другим.
"Delphi глазами хакера" М.Феленов
Познавая других, мы познаем себя.
С'est la vie...
SuperVisor вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Принадлежность точки Forro Помощь студентам 4 26.05.2008 14:33
Отбражение чисел - точки, это точки, а не запятые, обозначающие дробную часть Дикий Помощь студентам 7 12.05.2008 17:57
Принадлежность точки UnFaithful Паскаль, Turbo Pascal, PascalABC.NET 1 08.01.2008 06:16
Принадлежность объекта по координатам Angel_CJ Помощь студентам 9 12.09.2007 18:43