Принадлежность точки контуру

← →
Vitaliy_____ (2007-08-24 12:05) [0]

Доброе время суток!
Подскажите идею для реализации темы.
Сделал процедурку проверки на принадлежность точки выпуклому контуру через сумму углов к вершинам. Сейчас возникла необходимость проверять невыпуклые многоугольники. Кто силен в математике. Нужно или свести задачу к уже решенной (но тогда надо решить как разбить невыпуклый многоугольник на сумму выпуклых). Либо, возможно, есть другие алгоритмы.
Слышал идею, что контур отрисовывается на канве чего-либо, а потом смотрится цвет точки. Это не пойдет. Во-первых координаты вещественные должны быть, во-вторых для больших контуров такой подход не очень-то применим.
Если дадите ссылку на хорошую статью по этой теме - буду очень благодарен.

← →
Ega23 © (2007-08-24 12:21) [1]

Каждая сторона многоугольника - суть отрезок. Отрезок - часть прямой. Прямую можно задать уравнением (достаточно координат точек - концов отрезка). Вот и делай подстановку координат каждой точки в уравнение каждой стороны. При этом проверяй её на принадлежность конкретному отрезку данной прямой.

Это самый тупой способ, который пришёл в голову.
Возможно, какое-нибудь разбиение многоугольника на треугольники будет более оптимальным. Но это уже - читать учебники... :)

← →
Рамиль © (2007-08-24 12:28) [2]

http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%B2_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D0%B5

http://program.rin.ru/razdel/html/655.html

← →
Vlad Oshin © (2007-08-24 12:30) [3]

точка в регионе, апи есть такая

← →
Vitaliy_____ (2007-08-24 12:33) [4]

> точка в регионе, апи есть такая

А имя ее? Возможно это будет много проще...

← →
Vlad Oshin © (2007-08-24 12:38) [5]

http://www.yandex.ru/yandsearch?text=%F2%EE%F7%EA%E0+%E2+%F0%E5%E3%E8%EE%ED%E5+delphi+

№7
Rgn := CreatePolygonRgn(Points, PointsCount,...);
Result := PtInRgn(Point,Rgn);
CloseHandle(Rgn);

← →
Vitaliy_____ (2007-08-24 12:46) [6]

> Rgn := CreatePolygonRgn(Points, PointsCount,...);
> Result := PtInRgn(Point,Rgn);

Вот PtInRect вижу, а PtInRgn нет. Чего подключить надо?

← →
Vlad Oshin © (2007-08-24 12:58) [7]

наверное хелп сбился, перестройте

The PtInRegion function determines whether the specified point is inside the specified region.

BOOL PtInRegion(

HRGN hrgn, // handle of region
int X, // x-coordinate of point
int Y // y-coordinate of point
);

Parameters

hrgn

Identifies the region to be examined.

X

Specifies the x-coordinate of the point.

Y

Specifies the y-coordinate of the point.

Return Values

If the specified point is in the region, the return value is nonzero.
If the specified point is not in the region, the return value is zero.

See Also

RectInRegion

← →
Vitaliy_____ (2007-08-24 13:12) [8]

Ладно, буду разбираться в понедельник. Сейчас что-то не плющит. В принципе накидали нормально, надо только найти как заставить это работать.
Vlad Oshin А это точно есть в 7-й делфи? Что-то ругается он на название. Хэлп тут у меня вообще глючный: он даже поиск не может по себе сделать (построить перечень слов). Дома посмотрю, а тут я переставить не могу если потребуется. Если что, подскажи что нужно подключить (чего там uses)?

← →
boa_kaa © (2007-08-24 13:12) [9]

Ответ здесь: http://algolist.manual.ru/maths/geom/belong/poly2d.php

Больше алгоритмов на граф. тему уровнем выше: http://algolist.manual.ru/maths/geom/

или у Шикина & Борескова

← →
Ega23 © (2007-08-24 13:13) [10]

> Vitaliy_____ (24.08.07 13:12) [8]

Так я не понял: тебе именно графическое решение надо? Или аналитическое?

← →
Vitaliy_____ (2007-08-24 13:21) [11]

> Так я не понял: тебе именно графическое решение надо? Или
> аналитическое?

Мне именно графическое НЕ надо. Нужно аналитическое :)

← →
Vlad Oshin © (2007-08-24 13:22) [12]

h:hrgn;

PtInRegion(h,1,1);

редактор подсказывал типы при наборе, компилятор скомпилировал и запустил, delphi 7.

← →
Ega23 © (2007-08-24 13:25) [13]

> Мне именно графическое НЕ надо. Нужно аналитическое :)

См. ответы [1] и [2]

← →
Vlad Oshin © (2007-08-24 13:35) [14]

тогда проще всего так

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

← →
Ega23 © (2007-08-24 13:37) [15]

> пускается из точки любой луч и считается кол-во пересечений
> со сторонами многоугольника.
> четно - не принадлежит
>

сколько разных лучей на плоскости можно пустить из одной точки, принадлежащей данной плоскости?

← →
Vlad Oshin © (2007-08-24 13:38) [16]

> сколько разных лучей на плоскости можно пустить из одной
> точки, принадлежащей данной плоскости?

много

← →
Ega23 © (2007-08-24 13:41) [17]

> много

бесконечно много.

← →
Vlad Oshin © (2007-08-24 13:44) [18]

> бесконечно много.

это жадность.

Нужен один.

← →
Ega23 © (2007-08-24 13:46) [19]

> Нужен один.

Не понял, кто нужен: Один или Мак-Лауд?

← →
boa_kaa © (2007-08-24 14:48) [20]

Еще раз настоятельно рекомендую

> boa_kaa © (24.08.07 13:12) [9]

← →
ari_9 (2007-08-25 13:55) [21]

Vlad Oshin прав, достаточно взять любой произвольный луч и посчитать количество его пересечений со сторонами многоугольника

в коде это выглядит так, Vertexes - массив вершин многоугольника :

Result := False; for k := 0 to High(Vertexes) do begin if k < High(Vertexes) then l := k + 1 else l := 0; if (Y > Vertexes[k].Y) = (Y <= Vertexes[l].Y) then if (X - Vertexes[k].X < (Y - Vertexes[k].Y) * (Vertexes[l].X - Vertexes[k].X) / (Vertexes[l].Y - Vertexes[k].Y)) then Result := not Result; end;

← →
palva © (2007-08-25 23:06) [22]

ari_9 (25.08.07 13:55) [21]
Если замкнутый контур два раза охватывает точку, этот алгоритм не работает.
Вот если бы можно было наложить условие, что контур не имеет самопересечений... Но автору нужен общий случай.

← →
zorik © (2007-08-27 09:39) [23]

type TPointR=Record x,y:real; end; arrOfPoint=array of TpointR; function PointInPolygon(TestPolygon: arrofPoint; TestPoint : TPointR) : Boolean; var ToTheLeftofPoint, ToTheRightofPoint : Byte; np : Integer; OpenPolygon : Boolean; XIntersection : Real; begin ToTheLeftofPoint := 0; ToTheRightofPoint := 0; OpenPolygon := False; {tests if the polygon is closed} if not ((TestPolygon[0].X=TestPolygon[High(TestPolygon)].X) and (TestPolygon[0].Y=TestPolygon[High(TestPolygon)].Y)) then OpenPolygon := True; {tests for each couple of points to see if the side between them crosses the horizontal line going through TestPoint} for np := 1 to High(TestPolygon) do if ((TestPolygon[np-1].Y <= TestPoint.Y) and (TestPolygon[np].Y > TestPoint.Y)) or ((TestPolygon[np-1].Y > TestPoint.Y) and (TestPolygon[np].Y <= TestPoint.Y)) {if it does} then begin {computes the x coordinate of the intersection} XIntersection := TestPolygon[np-1].X + ((TestPolygon[np].X-TestPolygon[np-1].X)/ (TestPolygon[np].Y-TestPolygon[np-1].Y)) *(TestPoint.Y-TestPolygon[np-1].Y); {increments appropriate counter} if XIntersection < TestPoint.X then Inc(ToTheLeftofPoint); if XIntersection > TestPoint.X then Inc(ToTheRightofPoint); end; {if the polygon is open, test for the last side} if OpenPolygon then begin np := High(TestPolygon); {Thanks to William Boyd - 03/06/2001} if ((TestPolygon[np].Y <= TestPoint.Y) and (TestPolygon[0].Y > TestPoint.Y)) or ((TestPolygon[np].Y > TestPoint.Y) and (TestPolygon[0].Y <= TestPoint.Y)) then begin XIntersection := TestPolygon[np].X + ((TestPolygon[0].X-TestPolygon[np].X)/ (TestPolygon[0].Y-TestPolygon[np].Y)) *(TestPoint.Y-TestPolygon[np].Y); if XIntersection < TestPoint.X then Inc(ToTheLeftofPoint); if XIntersection > TestPoint.X then Inc(ToTheRightofPoint); end; end; if (ToTheLeftofPoint mod 2 = 1) and (ToTheRightofPoint mod 2 = 1) then Result := True else Result := False; end;

Вот алгоритм. Давно где-то скачал.

← →
palva © (2007-08-27 09:46) [24]

> Вот алгоритм. Давно где-то скачал.
. . . > if (ToTheLeftofPoint mod 2 = 1) and (ToTheRightofPoint mod 2 = 1) > then Result := True else Result := False;
Из орешника, наверное, качал.

← →
Думкин © (2007-08-27 10:12) [25]

> Сделал процедурку проверки на принадлежность точки выпуклому
> контуру через сумму углов к вершинам.

А в случае невыпуклого это не работает, разве?

← →
Виталий_____ (2007-09-06 16:10) [26]

> А в случае невыпуклого это не работает, разве?

К сожалению, нет.

← →
reonid © (2007-09-06 16:23) [27]

Алгоритм луча.
Точка принадлежит многоугольнику, если луч, исходящий из точки,
пересекает нечетное количество рёбер.
Работает для выпуклых, вогнутых, самопересекающихся и проч.

function PtInPolygonF(const P: array of TPointF; const Pt: TPointF): Boolean;
var i, j, k, Count, Intersect: Integer;
t: TFloat;
function MaxY(i, j: Integer; var k: Integer): TFloat;
begin
if P[i].Y > P[j].Y then
begin Result := P[i].Y; k := i; end else
begin Result := P[j].Y; k := j; end;
end;
begin
Count := Length(P);
Intersect := 0;
for i := 0 to Count - 1 do
begin
j := (i+1)mod Count;
if not( ( Pt.Y<P[i].Y )and( Pt.Y<P[j].Y ) )and
not( ( Pt.Y>P[i].Y )and( Pt.Y>P[j].Y ) )and
not( P[i].Y = P[j].Y )then
if MaxY(i, j, k) = Pt.Y then
begin
if P[k].X > Pt.X then Inc(Intersect)
end
else if not (Min(P[i].Y, P[j].Y) = Pt.Y) then
begin
t := (Pt.Y - P[i].Y )/( P[j].Y - P[i].Y );
if (t>0)and(t<1)and(P[i].X+t*(P[j].X-P[i].X)>Pt.X)then Inc(Intersect);
end;
end;
Result := Intersect mod 2 = 1;
end;

> Работает для выпуклых, вогнутых, самопересекающихся и проч.
Пример: Многоугольник окружает точку двумя витками (одно самопересечение).
Луч пересекает стороны четное число раз. Вывод: точка многоугольнику не принадлежит.

← →
Паша 1 (2007-09-06 16:32) [29]

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

> [29] Паша 1 (06.09.07 16:32)

Добавить проверку: если луч прошёл через точку, то выбрать другой.

Паша 1 (06.09.07 16:32) [29]
Всё учтено.

> Всё учтено.
Тогда объясните почему алгоритм не работает здесь
palva © (06.09.07 16:28) [28]
С интуитивной точки зрения точка многоугольнику принадлежит. Или у вас особое определение принадлежности? Тогда какое?

Если я правильно понял картинку, то обычно такая точка
считается внешней по отношению к многоугольнику.

Если имелось ввиду что-нибудь типа этого
_____ ____ / \/ \ / / \ \ | | \ | | \ * / | \ \_/ / \ / \_________/

reonid © (06.09.07 17:11) [35]
Понятно. Т.е. точки с четным индексом охвата по вашему определению не принадлежат многоугольнику.

2palva © (06.09.07 17:41) [36]
Почему же "по моему определению"?
Создай подобный регион в режиме ALTERNATE и закрась его.
Или же создай подобную фигуру в Кореле.

> Почему же "по моему определению"?
Я вас не очень понимаю. Я попросил сформулировать определение. Вы этого не сделали. Я сформулировал за вас, исходя из того, как я понял ваш алгоритм. Теперь оказывается это не ваше определение. Вы то сами какой точки зрения придерживаетесь? Точка в reonid © (06.09.07 17:11) [35] многоугольнику не принадлежит. А если многоугольник сделает еще один виток, то будет принадлежать. Правильно я понимаю?

Принадлежность точки контуру Найти похожие ветки