Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Точка в четырехугольнике


Автор: Гость_Гость 5.7.2005, 16:30
Есть четырехугольник с координатами 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;




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

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

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

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

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

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

Автор: boevik 5.7.2005, 18:56
Использовать алгоритм для построяния выпуклой оболочки.

Автор: Earnest 5.7.2005, 19:43
Гость_Гость
Странно, что ваш код не работает, потому как это классический алгоритм Жордана. Может, где-то неверно реализован - там есть тонкости. А еще метод не работает для точки на границе - только строго внутри-снаружи.
http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html тест "точка в полигоне" обсуждается очень подробно, есть код на C и Фортране.

Автор: SoWa 6.7.2005, 07:45
Хм. Я таким кодом и пользуюсь. Только сбоев еще небыло.

Автор: maxim1000 6.7.2005, 15:55
http://forum.vingrad.ru/index.php?showtopic=40818

Автор: Marriage 23.8.2005, 10:09
Функция приведенная в самом начале у меня не работала не правильно.
При замене кода
Код

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


на

Код

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


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

Автор: SashaVinnica 4.9.2005, 18:58
Предлагаю использовать 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-координату точки.

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

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

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

Автор: podval 5.9.2005, 11:01
Цитата(Akina @ 5.7.2005, 18:17)
Если все векторные произведения векторов (вершина1-вершина2) и (вершина1-точка) имеют один знак - точка внутри.

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

Автор: Akina 5.9.2005, 13:05
Цитата(podval @ 5.9.2005, 12:01)
есть какая-то теорема по данному поводу?

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

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

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

Автор: Akina 15.9.2005, 18:09
Цитата(B0BAH @ 15.9.2005, 17:40)
Мне тоже задали задачку но посложней

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

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)