Есть четырехугольник с координатами p0(x0,y0), p1(x1,y1), p2(x2,y2), p3(x3,y3) и точка с координатами n(x,y). Как узнать лежит точка внутри четырехугольника или нет.

Нашёл такой алгоритм:

Код

type   TReal1DArray        = array of Double; function IsPointInPolygon(x : Double;      y : Double;      N : Integer;      const XPO : TReal1DArray;      const YPO : TReal1DArray):Boolean; var     I : Integer;     XPI : TReal1DArray;     YPI : TReal1DArray; begin     SetLength(XPI, N+1);     SetLength(YPI, N+1);     I:=1;     while I<=N do     begin         XPI[I] := XPO[I];         YPI[I] := YPO[I];         Inc(I);     end;     XPI[0] := XPI[N];     YPI[0] := YPI[N];     i := 0;     Result := False;     repeat         if  not ((y>YPI[i]) xor (y<=YPI[i+1])) then         begin             if x-XPI[i]<(y-YPI[i])*(XPI[i+1]-XPI[i])/(YPI[i+1]-YPI[i]) then             begin                 Result :=  not Result;             end;         end;         i := i+1;     until  not (i<=n-1); end;

Но он работает не точно.

Если все векторные произведения векторов (вершина1-вершина2) и (вершина1-точка) имеют один знак - точка внутри.

Способ 1-й. Любая линия, представленная уравнением y=ax+b делит плоскость на "положительную" и "отрицательную". Т.е. Если мы представим уравнение в виде ax-y+b=0 и будем подставлять в уравнение точки, не лежащие на этой прямой, то для всех точек, лежащих по одну сторону от прямой величина "ошибки"(т.е. отличия от нуля) будет положительна, для другой полуплоскости эта величина будет отрицательна. Всегда можно составить уравнение 4-х прямых, образующих многоугольник так, что внутри будет отрицательная область (не подведи меня мой склероз ). Дальше думаю сам разберешься...
Способ 2-й. 4-хугольник разбивается на два треугольника. Если точка лежит внутри хотя бы одного треуголника - она лежит внутри 4-хугольника. ПРинадлежность треугольнику можно проверить эллементарно аннализирую раастояние до всех его 3-х вершин

Еще если можешь посчитать площадь этого 4-х угольника, то сравни площади фигуры и сумму площадей 4 треугольников, полученых соединением точки с вершинами. Вот формула площади треугольника по вершинам:

Код

S= 1/2 * abs( (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) )

Вывод из векторного произведения векторов, долго, поэтому не вывожу.

Использовать алгоритм для построяния выпуклой оболочки.

Гость_Гость
Странно, что ваш код не работает, потому как это классический алгоритм Жордана. Может, где-то неверно реализован - там есть тонкости. А еще метод не работает для точки на границе - только строго внутри-снаружи.
Здесь тест "точка в полигоне" обсуждается очень подробно, есть код на C и Фортране.

Это сообщение отредактировал(а) Earnest - 5.7.2005, 19:57

Хм. Я таким кодом и пользуюсь. Только сбоев еще небыло.

Это сообщение отредактировал(а) SoWa - 6.7.2005, 07:46

http://forum.vingrad.ru/index.php?showtopic=40818

Функция приведенная в самом начале у меня не работала не правильно.
При замене кода

Код

XPI[I] := XPO[I]; YPI[I] := YPO[I];

на

Код

XPI[I] := XPO[I-1]; YPI[I] := YPO[I-1];

У меня все заработало нормально.

Это сообщение отредактировал(а) Marriage - 23.8.2005, 10:11

Предлагаю использовать API функии



Функция CreatePolygonRgn создает многоугольную область.

HRGN CreatePolygonRgn(

CONST POINT *lppt, // указатель на массив точек
int cPoints, // число точек в массиве
int fnPolyFillMode // режим заполнения многоугольника
);


Параметры

lppt – указатель на массив структур типа POINT, которые определяют вершины многоугольника. Многоугольник полагается замкнутым. Каждая вершина может быть задана лишь один раз.

cPoints – определяет количество точек в массиве.

fnPolyFillMode – тебе он не нужен

Возвращаемые значения

В случае успеха возвращается дескриптор области.
В случае неудачи возвращается NULL.




Структура POINT определяет x- и y- координаты точки.

typedef struct tagPOINT {
LONG x;
LONG y;
} POINT;


Члены

x – определяет x-координату точки.
y – определяет y-координату точки.



Функция PtInRegion определяет, находится ли заданная точка внутри указанной области.

BOOL PtInRegion(

HRGN hrgn, // дескриптор области
int X, // x-координата точки
int Y // y-координата точки
);


Параметры

hrgn – идентифицирует область.

X – указывает x-координату точки.

Y – указывает y-координату точки.

Возвращаемые значения

Если заданная точка находится в указанной области, то возвращается ненулевое значение.

Если заданная точка находится вне указанной области, то возвращается нуль.

Цитата(Akina @ 5.7.2005, 18:17)

Если все векторные произведения векторов (вершина1-вершина2) и (вершина1-точка) имеют один знак - точка внутри.

Не мог бы напомнить, есть какая-то теорема по данному поводу?

Цитата(podval @ 5.9.2005, 12:01)

есть какая-то теорема по данному поводу?

нет наверное...

Мне тоже задали задачку но посложней->там дан многоугольник(т.е. число точек x1,y1;x2,y2....xi,yi ; где i может быть >10)!Лежит ли x,y или не лежит!

Вот это делема!подскажите кто может

Цитата(B0BAH @ 15.9.2005, 17:40)

Мне тоже задали задачку но посложней

Есть готовые алгоритмы деления произвольного многоугольника на треугольники. Так что чего тут более сложного?

http://algolist.manual.ru/maths/geom/belong/poly2d.php про это тему и вообще http://algolist.manual.ru --очень крут