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

[LevioFUN]

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

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

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

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

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

[AVer]

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

[LevioFUN]

1.) Герона...
2.) "находяшегося ближе всего к точке" - ?
3.) x1,x2,x3 - точки много-ка? (последовательные или могут с "перескоком"?)

[AVer]

смотри вложение. немного коряво, потому что делал быстро.

[SuperVisor]

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

[LevioFUN]

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

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

[AVer]

SuperVisor

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

Это классическое pascal-решение. Просто нам такую же задавали....

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

[LevioFUN]

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

да и с выпуклыми не проходит =\

[AVer]

Ну тогда делай как говорит SuperVisor. Самое простое и быстрое решение в Delphi.

[SuperVisor]

Сообщение от AVer

Это классическое pascal-решение. Просто нам такую же задавали....

"5. Не придумывай велосипед. Тут опять действует созидательная функция хакеров. Они не должны стоять на месте и обязаны делиться своими знаниями. Например, вы написали какой-то уникальный код, поделитесь им с другими, чтобы людям не пришлось создавать то же самое. Вы можете не выдавать все секреты, но должны помогать другим.

"Delphi глазами хакера" М.Феленов