Точка внутри полигона.

← →
Lexa (2005-06-05 14:12) [0]

На форме имеется картинка (TImage), пользователь тыкает мышкой, и нужно проверить, попал ли он в некоторую область (полигон, имеющий порядка 100 вершин). Подскажите, как это реализовать.

← →
KilkennyCat © (2005-06-05 14:20) [1]

закрасить ее цветом. проверить цвет пиксела.

← →
begin...end © (2005-06-05 14:20) [2]

CreatePolygonRgn + PtInRegion + F1

← →
gent (2005-06-05 18:29) [3]

Это - известная "олимпиадная" задача. Полигон м.б. любой (невыпуклый, самопересекающийся и т.п.). Решение вкратце: рисуешь луч из искомой точки в бесконечность и считаешь его пересечения с ребрами полигона. В зависимости от "чёт/нечет" получаешь "снаружи/внутри".

← →
Sergey Masloff (2005-06-05 19:25) [4]

gent (05.06.05 18:29) [3]
Олимпиады по фиг. PtInRegion работает с невыпуклыми "самопересекающимися" регионами. Более того, при использовании CreatePolygonRgn() поддерживаются оба режима - и альтернативный и виндинг. Так что жизнь сложней олимпиад ;-)

← →
gent (2005-06-06 01:20) [5]

> Sergey Masloff (05.06.05 19:25) [4]

Смешно. Человеку предлагают общее решение, а он пытается ограничиться Windows API. На кой черт, спрашивается, таскать с собой gdi32.dll? Тем более, что она реализует тот же алгоритм.

← →
KilkennyCat © (2005-06-06 01:29) [6]

Вот будет забавно, если луч пройдет строго вдоль ребра.

← →
Kerk © (2005-06-06 06:18) [7]

gent (05.06.05 18:29) [3]

Это максимум задание на лабу. Или ты школьные олимпиады имел ввиду.

← →
boalse © (2005-06-06 06:37) [8]

> Lexa (05.06.05 14:12)

Если Форма полигона очень сложная и его сложно описать при помощи точек, то лучше сделать, как посоветовал

> KilkennyCat © (05.06.05 14:20) [1]

Создать копию картинки, на ней в пэинте нарисовать нужный полигон и закрасить его, например, чёрным цветом, всё остальное белым. Когда тыкают мышою на Image, известны координаты по которым тыкнули. Получаем по этим координатам с картинки-копии цвет пикселя, если чёрный, значит попал, если белый - мимо.

← →
Sergey_Masloff (2005-06-06 09:21) [9]

gent (06.06.05 01:20) [5]
>Смешно. Человеку предлагают общее решение, а он пытается ?>ограничиться Windows API.
Рисуем полигон - пятиконечную звезду. Ну алгоритм я думаю знают все - тот что в центре получается пятиугольник. Рисуем в центре пятиугольника точку. Дальше слово предоставляется Вам - точка в области или вне?

>На кой черт, спрашивается, таскать с собой gdi32.dll?
;-)

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

← →
gent (2005-06-06 14:36) [10]

> Kerk © (06.06.05 06:18) [7]
> Это максимум задание на лабу...

Сказано же, известная задача. "На лабу" - это если книжки умные читать, а четверть века назад книжек таких не было...

> Sergey_Masloff (06.06.05 09:21) [9]
> ... точка в области или вне?

Как определите так и будет.
По алгоритму в [3] она вне полигона (это ALTERNATE в GDI).
Хотите внутри (== GDI WINDING)? Используйте другой алгоритм - вращение луча и суммирование углов.

← →
Sergey_Masloff (2005-06-06 15:02) [11]

gent (06.06.05 14:36) [10]
Так я и предлагаю использовать одну функцию ;-) А не реализовывать зачем-то алгоритм с вращением луча. Спорим за 15 минут не напишите готовый к использованию - не набросок а точно отлаженый.
Конечно "можно один раз написать потом пользоваться" - но ведь уже написано же. Брать и пользоваться только ;-)

> gent (06.06.05 01:20) [5]
> На кой черт, спрашивается, таскать с собой gdi32.dll?

Действительно, и на кой черт таскать ее с собой, если она и так всегда имеется?

← →
gent (2005-06-06 15:30) [13]

> Sergey_Masloff (06.06.05 15:02) [11]
> Спорим за 15 минут не напишите...

И пытаться не буду. Уже давно не интересно, кто выше на стенку писает...
----------------
Глупый спор получается. Я привел общий алгоритм, Вы - конкретику под WinAPI. Могу привести кучу доводов, кучу примеров в обе стороны. В самом верху этой темы есть товарищ "интересующийся" - ему решать, что выбрать. Если это институтское задание, то, скорей всего, преподаватель хочет алгоритм. Если "живая задача" - то в большинстве случаев устроит и GDI.

> gent (06.06.05 15:30) [13]

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

Он уже выбрал. В вопросе указано - WinXP. Значит, всегда есть gdi32, а в ней - практически готовое решение.

Какой алгоритм использовать - еще и очень зависит от конкретной задачи. Сначала нужно определиться с понятием "точка внутри полигона". Например, алгоритм, реализованный в функции PtInRegion считает, что узлы многоугольника - НЕ являются его частью. Тоже касается и любых точек, расположенных на сторонах многоугольника. Например:

var Rgn: HRGN; Pts: array [0..2] of TPoint; Pt: TPoint; begin Pts[0].X := 10; Pts[0].Y := 10; Pts[1].X := 20; Pts[1].Y := 20; Pts[2].X := 30; Pts[2].Y := 30; // точка - вершина треугольника Pt := Pts[0]; Rgn := CreatePolygonRgn(Pts[0],3,ALTERNATE); if Rgn <> 0 then begin case PtInRegion(RGN,Pt.X,Pt.Y) of True: ShowMessage ("INSIDE"); False: ShowMessage ("OUTSIDE"); end; DeleteObject(Rgn); end; end;
Так что - думайте сами, решайте сами.

Точка внутри полигона. Найти похожие ветки