Точка внутри невыпуклой области

[uhm]

Вот есть у меня замкнутая невыпуклая область, назовем ее... мнэ-э... скажем, Полуэ... ой, то есть, полигоном. Известны все вершины полигона и порядок, в котором они идут. Требуется понять, лежит ли произвольно заданная точка внутри полигона. Два вопроса:

1) Работает ли API PtInRegion для невыпуклых полигонов?

2) Если писать такое самому - какой алгоритм использовать? Я придумал нечто такое: триангулировать полигон, а потом проверять попадание точки в каждый треугольник. Нет ли какого-нибудь более простого способа?

[Amed]

А почему бы не проверить, работает ли PtInRegion для невупыклых полигонов?

[uhm]

Вот честно - лень
А вдруг кто и так знает?

Вообще, если приспичит - проверю, конечно. Но меня как раз больше второй вопрос интересует, первый - это я так, "заодним" спросил

[Лёха_Virus]

я делал такую весчь для четырехугольников (выпуклых ессесно). делается так: сосдаются неравентсва каждой грани (помнишь как в алгебре 2x+3>12 чё-то типа этого ) и потом проверяется удовлетворяет ли точка ВСЕМ неравенствам.
если надо могу код выложить.

[uhm]

Не, спасибо, для выпуклых многогранников все более-менее очевидно. Меня только невыпуклые интересуют.

[uhm]

Update: проверил - PtInRegion работает с невыпуклыми полигонами (во всяком случае, для невыпуклого пятиугольника все прекрасно работало).

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

[Amed]

а) тривиальная
б) закрыта
в) строчек

А по поводу триангуирования полигона, - разве это настолько сложно?

[tyomitch]

Задачка нетривиальная, но и сложного ничего нет. Безо всякой триангуляции: http://algolist.manual.ru/maths/geom/belong/poly2d.php

[Лёха_Virus]

Не, спасибо, для выпуклых многогранников все более-менее очевидно. Меня только невыпуклые интересуют.

ой, сорри... не так прочитал твой вопрос.

[uhm]

Amed'у: насчет "закрыта" - принимается, насчет остального - смотри Цитаты дня. Кстати - "тривиальная"!!!

Триангулирование - несложно, но, все-таки, по сравнению с задачей про выпуклый полигон, это сильное усложнение.

Tyomitch'у: спасибо, я оценил. Очень красивый алгоритм.

Всем спасибо!

[A.A.Z.]

2 Amed:

а) тревиальная

uhm прав, ты не прав Проверить можно легко - зайди на [url=encycl.yandex.ru]yandex.энциклопедии[/url] и набери там "тревиальный". Получишь сообщение
"Опечатка? Возможно, имелось ввиду "тривиальный""

[alibek]

http://gramota.ru/
Правописание рекомендуется проверять там.

[alibek]

Толково-словообразовательный словарь:
ТРИВИАЛЬНЫЙ (прил.)
1. Лишенный свежести и оригинальности, избитый, пошлый.

[uhm]

Блин, уже и пошутить нельзя... Обвинят во всех смертных грехах, а потом начнут обсуждать, как правильно пишется тривиальное слово

[tyomitch]

2 Amed:

а) тревиальная

uhm прав, ты не прав Проверить можно легко - зайди на [url=encycl.yandex.ru]yandex.энциклопедии[/url] и набери там "тревиальный". Получишь сообщение
"Опечатка? Возможно, имелось ввиду "тривиальный""

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

[Amed]

Ой, как я мог!?

Я знаю, дорогие друзья, что слово "тривиальная" пишется через и. Считайте это опиской.

[uhm]

БЛИН!!!
Доктор, меня никто не понимает!
Если вы внимательно посмотрите на мой пост, увидите, что некоторые слова там заключены в кавычки. А кавычки, в том числе, используются для оформления цитат. А цитировал я вот отсюда:

http://bbs.vbstreets.ru/viewtopic.php?t=1310&postdays=0&postorder=asc&start=195!

[A.A.Z.]

Так что Amed во всем виноват

[Amed]

...как всегда

Как аватар? Вставляет?

[A.A.Z.]

"А" чуть-чуть пожирнее надо сделать