Chcę sprawdzić, czy punkt znajduje się wewnątrz prostokąta, czy nie. Prostokąt może być zorientowany w dowolny sposób i nie musi być wyrównany do osi.

Jedną z metod, o których mogłem wymyślić, było obrócenie prostokąta i współrzędnych punktu w celu wyrównania osi prostokąta, a następnie po prostu przetestowanie współrzędnych punktu, czy leżą one w granicach prostokąta, czy nie.

Powyższa metoda wymaga rotacji, a więc operacji zmiennoprzecinkowych. Czy istnieje inny skuteczny sposób na zrobienie tego?

Jak jest reprezentowany prostokąt? Trzy punkty? Cztery punkty? Punkt, boki i kąt? Dwa punkty i bok? Coś innego? Nie wiedząc o tym, wszelkie próby odpowiedzi na twoje pytanie będą miały wyłącznie czysto akademicką wartość.

W każdym razie dla dowolnego wypukłego wielokąta (w tym prostokąta) test jest bardzo prosty: sprawdź każdą krawędź wielokąta, zakładając, że każda krawędź jest zorientowana w kierunku przeciwnym do ruchu wskazówek zegara i sprawdź, czy punkt leży po lewej stronie krawędzi (po lewej półpłaszczyzna ręczna). Jeśli wszystkie krawędzie przejdą test - punkt jest wewnątrz. Jeśli przynajmniej jeden zawodzi - punkt jest na zewnątrz.

Aby sprawdzić, czy punkt (xp, yp)leży po lewej stronie krawędzi (x1, y1) - (x2, y2), wystarczy obliczyć

D = (x2 - x1) * (yp - y1) - (xp - x1) * (y2 - y1)

Jeśli D > 0punkt znajduje się po lewej stronie. Jeśli D < 0punkt znajduje się po prawej stronie. Jeśli D = 0punkt jest na linii.

Poprzednia wersja tej odpowiedzi opisywała pozornie inną wersję testu lewej strony (patrz poniżej). Ale można łatwo wykazać, że oblicza tę samą wartość.

... Aby sprawdzić, czy punkt (xp, yp)leży po lewej stronie krawędzi (x1, y1) - (x2, y2), musisz zbudować równanie prostej dla prostej zawierającej krawędź. Równanie jest następujące

A * x + B * y + C = 0

gdzie

A = -(y2 - y1)
B = x2 - x1
C = -(A * x1 + B * y1)

Teraz wszystko, co musisz zrobić, to obliczyć

D = A * xp + B * yp + C

Jeśli D > 0punkt znajduje się po lewej stronie. Jeśli D < 0punkt znajduje się po prawej stronie. Jeśli D = 0punkt jest na linii.

Jednak ten test znowu działa dla każdego wypukłego wielokąta, co oznacza, że ​​może być zbyt ogólny dla prostokąta. Prostokąt może pozwolić na prostszy test ... Na przykład w prostokącie (lub w jakimkolwiek innym równoległoboku) wartości Ai Bmają tę samą wielkość, ale różne znaki dla przeciwnych (tj. Równoległych) krawędzi, które można wykorzystać do uproszczenia testu .

Zakładając, że prostokąt jest reprezentowany przez trzy punkty A, B, C, przy czym AB i BC są prostopadłe, wystarczy sprawdzić rzuty punktu zapytania M na AB i BC:

0 <= dot(AB,AM) <= dot(AB,AB) &&
0 <= dot(BC,BM) <= dot(BC,BC)

ABJest to wektor AB, o współrzędnych (BX-Ax, Ay, W) i dot(U,V)jest iloczyn skalarny wektorów U i V: Ux*Vx+Uy*Vy.

Aktualizuj . Zilustrujmy to na przykładzie: A (5,0) B (0,2) C (1,5) i D (6,3). Ze współrzędnych punktu otrzymujemy AB = (- 5,2), BC = (1,3), kropka (AB, AB) = 29, kropka (BC, BC) = 10.

Dla punktu zapytania M (4,2) mamy AM = (- 1,2), BM = (4,0), kropka (AB, AM) = 9, kropka (BC, BM) = 4. M znajduje się wewnątrz prostokąta.

Dla punktu zapytania P (6,1) mamy AP = (1,1), BP = (6, -1), kropka (AB, AP) = - 3, kropka (BC, BP) = 3. P nie znajduje się wewnątrz prostokąta, ponieważ jego rzut na bok AB nie znajduje się wewnątrz odcinka AB.

Pożyczyłem z odpowiedzi Erica Bainville'a:

0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC)

Co w javascript wygląda tak:

function pointInRectangle(m, r) {
    var AB = vector(r.A, r.B);
    var AM = vector(r.A, m);
    var BC = vector(r.B, r.C);
    var BM = vector(r.B, m);
    var dotABAM = dot(AB, AM);
    var dotABAB = dot(AB, AB);
    var dotBCBM = dot(BC, BM);
    var dotBCBC = dot(BC, BC);
    return 0 <= dotABAM && dotABAM <= dotABAB && 0 <= dotBCBM && dotBCBM <= dotBCBC;
}

function vector(p1, p2) {
    return {
            x: (p2.x - p1.x),
            y: (p2.y - p1.y)
    };
}

function dot(u, v) {
    return u.x * v.x + u.y * v.y; 
}

na przykład:

var r = {
    A: {x: 50, y: 0},
    B: {x: 0, y: 20},
    C: {x: 10, y: 50},
    D: {x: 60, y: 30}
};

var m = {x: 40, y: 20};

następnie:

pointInRectangle(m, r); // returns true.

Oto kod do narysowania wyniku jako testu wizualnego :) http://codepen.io/mattburns/pen/jrrprN

# Pseudo code
# Corners in ax,ay,bx,by,dx,dy
# Point in x, y

bax = bx - ax
bay = by - ay
dax = dx - ax
day = dy - ay

if ((x - ax) * bax + (y - ay) * bay < 0.0) return false
if ((x - bx) * bax + (y - by) * bay > 0.0) return false
if ((x - ax) * dax + (y - ay) * day < 0.0) return false
if ((x - dx) * dax + (y - dy) * day > 0.0) return false

return true

Zdaję sobie sprawę, że to stary wątek, ale dla każdego, kto jest zainteresowany spojrzeniem na to z czysto matematycznej perspektywy, jest doskonały wątek na temat wymiany stosów matematycznych, tutaj:

/math/190111/how-to-check-if-a-point-is-inside-a-rectangle

Edycja: Zainspirowany tym wątkiem, opracowałem prostą metodę wektorową, aby szybko określić, gdzie leży twój punkt.

Załóżmy, że masz prostokąt z punktami w punktach p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y3) i p4 = (x4, y4), zgodnie z ruchem wskazówek zegara. Jeśli punkt p = (x, y) leży wewnątrz prostokąta, to iloczyn skalarny (p - p1). (P2 - p1) będzie leżeć między 0 a | p2 - p1 | ^ 2, a (p - p1). (p4 - p1) będzie leżeć między 0 a | p4 - p1 | ^ 2. Jest to równoważne z rzutem wektora p - p1 wzdłuż długości i szerokości prostokąta, z punktem początkowym p1.

Może to mieć więcej sensu, jeśli pokażę równoważny kod:

p21 = (x2 - x1, y2 - y1)
p41 = (x4 - x1, y4 - y1)

p21magnitude_squared = p21[0]^2 + p21[1]^2
p41magnitude_squared = p41[0]^2 + p41[1]^2

for x, y in list_of_points_to_test:

    p = (x - x1, y - y1)

    if 0 <= p[0] * p21[0] + p[1] * p21[1] <= p21magnitude_squared:
        if 0 <= p[0] * p41[0] + p[1] * p41[1]) <= p41magnitude_squared:
            return "Inside"
        else:
            return "Outside"
    else:
        return "Outside"

I to wszystko. Będzie również działać w przypadku równoległoboków.

bool pointInRectangle(Point A, Point B, Point C, Point D, Point m ) {
    Point AB = vect2d(A, B);  float C1 = -1 * (AB.y*A.x + AB.x*A.y); float  D1 = (AB.y*m.x + AB.x*m.y) + C1;
    Point AD = vect2d(A, D);  float C2 = -1 * (AD.y*A.x + AD.x*A.y); float D2 = (AD.y*m.x + AD.x*m.y) + C2;
    Point BC = vect2d(B, C);  float C3 = -1 * (BC.y*B.x + BC.x*B.y); float D3 = (BC.y*m.x + BC.x*m.y) + C3;
    Point CD = vect2d(C, D);  float C4 = -1 * (CD.y*C.x + CD.x*C.y); float D4 = (CD.y*m.x + CD.x*m.y) + C4;
    return     0 >= D1 && 0 >= D4 && 0 <= D2 && 0 >= D3;}





Point vect2d(Point p1, Point p2) {
    Point temp;
    temp.x = (p2.x - p1.x);
    temp.y = -1 * (p2.y - p1.y);
    return temp;}

Właśnie zaimplementowałem odpowiedź AnT za pomocą c ++. Użyłem tego kodu, aby sprawdzić, czy koordynacja piksela (X, Y) leży wewnątrz kształtu, czy nie.

Jeśli nie możesz rozwiązać problemu dla prostokąta, spróbuj podzielić problem na łatwiejsze. Podziel prostokąt na 2 trójkąty i sprawdź, czy punkt znajduje się wewnątrz któregokolwiek z nich, tak jak wyjaśniono tutaj

Zasadniczo przechodzisz między krawędziami na każdych dwóch parach linii z punktu. Następnie za pomocą iloczynu poprzecznego sprawdź, czy punkt znajduje się między dwiema liniami za pomocą iloczynu poprzecznego. Jeśli jest zweryfikowany dla wszystkich 3 punktów, to punkt znajduje się wewnątrz trójkąta. Zaletą tej metody jest to, że nie tworzy ona żadnych błędów punktów zmiennoprzecinkowych, które zdarzają się, gdy sprawdzasz kąty.

Jeśli punkt znajduje się wewnątrz prostokąta. W samolocie. Dla współrzędnych matematycznych lub geodezji (GPS)

• Niech prostokąt będzie wyznaczony przez wierzchołki A, B, C, D. Punkt to P. Współrzędne są prostokątne: x, y.
• Pozwala przedłużyć boki prostokąta. Mamy więc 4 proste l _AB , l _BC , l _CD , l _DA lub, w skrócie, l ₁ , l ₂ , l ₃ , l ₄ .

• Zrób równanie dla każdego l _i . Rodzaj równania:

  f _i (P) = 0.

P to punkt. W przypadku punktów należących do l _i równanie jest prawdziwe.

• Potrzebujemy funkcji po lewej stronie równań. Są to f ₁ , f ₂ , f ₃ , f ₄ .
• Zauważ, że dla każdego punktu z jednej strony l _i funkcja f _i jest większa niż 0, dla punktów z drugiej strony f _i jest mniejsza niż 0.
• Tak więc, jeśli sprawdzamy, czy P jest w prostokącie, potrzebujemy tylko, aby p znajdował się po właściwych stronach wszystkich czterech linii. Musimy więc sprawdzić cztery funkcje pod kątem ich znaków.
• Ale która strona linii jest właściwa, do której należy prostokąt? Jest to bok, w którym leżą wierzchołki prostokąta nie należące do linii. Do sprawdzenia możemy wybrać dowolny z dwóch nienależących wierzchołków.

• Więc musimy to sprawdzić:

  f _AB (P) f _AB (C)> = 0

  f _BC (P) f _BC (D)> = 0

  f _CD (P) f _CD (A)> = 0

  f _DA (P) f _DA (B)> = 0

Nierówności nie są ścisłe, bo jeśli punkt znajduje się na granicy, to również należy do prostokąta. Jeśli nie potrzebujesz punktów na granicy, możesz zmienić nierówności na ścisłe. Ale podczas pracy w operacjach zmiennoprzecinkowych wybór nie ma znaczenia.

• Na przykład w prostokącie wszystkie cztery nierówności są prawdziwe. Zauważ, że działa to również dla każdego wypukłego wielokąta, różni się tylko liczba linii / równań.

• Pozostaje tylko otrzymać równanie dla prostej przechodzącej przez dwa punkty. Jest to dobrze znane równanie liniowe. Napiszmy to dla prostej AB i punktu P:

  f _AB (P) ≡ (x _A -x _B ) (y _P -y _B ) - (y _A -y _B ) (x _P -x _B )

Sprawdzanie można uprościć - przejdźmy wzdłuż prostokąta zgodnie z ruchem wskazówek zegara - A, B, C, D, A. Wtedy wszystkie poprawne strony będą po prawej stronie linii. Nie musimy więc porównywać ze stroną, na której znajduje się inny wierzchołek. I musimy sprawdzić zestaw krótszych nierówności:

f _AB (P)> = 0

f _BC (P)> = 0

f _CD (P)> = 0

f _DA (P)> = 0

Ale jest to poprawne dla normalnego, matematycznego (ze szkolnej matematyki) zestawu współrzędnych, gdzie X jest po prawej stronie, a Y do góry. A dla współrzędnych geodezji , które są używane w GPS, gdzie X jest na górze, a Y na prawo, musimy odwrócić równania:

f _AB (P) <= 0

f _BC (P) <= 0

f _CD (P) <= 0

f _DA (P) <= 0

Jeśli nie masz pewności co do kierunków osi, zachowaj ostrożność przy tej uproszczonej kontroli - sprawdź jeden punkt ze znanym położeniem, jeśli wybrałeś prawidłowe nierówności.

Najprostszym sposobem, o którym pomyślałem, było po prostu rzutowanie punktu na oś prostokąta. Pozwól mi wyjaśnić:

Jeśli możesz uzyskać wektor od środka prostokąta do górnej lub dolnej krawędzi i lewej lub prawej krawędzi. Masz również wektor od środka prostokąta do punktu, możesz rzutować ten punkt na wektory szerokości i wysokości.

P = wektor punktowy, H = wektor wysokości, W = wektor szerokości

Uzyskaj wektor jednostkowy W ', H', dzieląc wektory przez ich wielkość

proj_P, H = P - (P.H ') H' proj_P, W = P - (P.W ') W'

Chyba że się mylę, co nie wydaje mi się ... (Popraw mnie, jeśli się mylę), ale jeśli wielkość rzutu twojego punktu na wektorze wysokości jest mniejsza niż wielkość wektora wysokości (który jest połowa wysokości prostokąta) i wielkość rzutu twojego punktu na wektor szerokości wynosi, wtedy masz punkt wewnątrz prostokąta.

Jeśli masz uniwersalny układ współrzędnych, być może będziesz musiał obliczyć wektory wysokości / szerokości / punktów za pomocą odejmowania wektorów. Projekcje wektorowe są niesamowite! Zapamietaj to.

W dalszej części odpowiedzi. musimy użyć rozwiązania /math/190111/how-to-check-if-a-point-is-inside-a-rectangle/190373#190373 , aby działało

Poniżej nie działa
0 <= kropka (AB, AM) <= kropka (AB, AB) && 0 <= kropka (BC, BM) <= kropka (BC, BC)

Poniżej działa
0 <= kropka (AB, AM) <= kropka (AB, AB) && 0 <= kropka (AM, AC) <= kropka (AC, AC)

sprawdzasz, wklejając poniżej w konsoli javascript // rozwiązanie Javascript dla tego samego

            var screenWidth = 320;
            var screenHeight = 568;
            var appHeaderWidth = 320;
            var AppHeaderHeight = 65;
            var regionWidth = 200;
            var regionHeight = 200;

            this.topLeftBoundary = {
                A: {x: 0, y: AppHeaderHeight},
                B: {x: regionWidth, y: AppHeaderHeight},
                C: {x: 0, y: regionHeight + AppHeaderHeight},
                D: {x: regionWidth, y: regionHeight + AppHeaderHeight}
            }

            this.topRightBoundary = {
                A: {x: screenWidth, y: AppHeaderHeight},
                B: {x: screenWidth - regionWidth, y: AppHeaderHeight},
                C: {x: screenWidth, y: regionHeight + AppHeaderHeight},
                D: {x: screenWidth - regionWidth, y: regionHeight + AppHeaderHeight}
            }

            this.bottomRightBoundary = {
                A: {x: screenWidth, y: screenHeight},
                B: {x: screenWidth - regionWidth, y: screenHeight},
                C: {x: screenWidth, y: screenHeight - regionHeight},
                D: {x: screenWidth - regionWidth, y: screenHeight - regionHeight}
            }

            this.bottomLeftBoundary = {
                A: {x: 0, y: screenHeight},
                B: {x: regionWidth, y: screenHeight},
                C: {x: 0, y: screenHeight - regionHeight},
                D: {x: regionWidth, y: screenHeight - regionHeight}
            }
            console.log(this.topLeftBoundary);
            console.log(this.topRightBoundary);
            console.log(this.bottomRightBoundary);
            console.log(this.bottomLeftBoundary);

            checkIfTapFallsInBoundary = function (region, point) {
                console.log("region " + JSON.stringify(region));
                console.log("point" + JSON.stringify(point));

                var r = region;
                var m = point;

                function vector(p1, p2) {
                    return {
                        x: (p2.x - p1.x),
                        y: (p2.y - p1.y)
                    };
                }

                function dot(u, v) {
                    console.log("DOT " + (u.x * v.x + u.y * v.y));
                    return u.x * v.x + u.y * v.y;
                }

                function pointInRectangle(m, r) {
                    var AB = vector(r.A, r.B);
                    var AM = vector(r.A, m);
                    var AC = vector(r.A, r.C);
                    var BC = vector(r.B, r.C);
                    var BM = vector(r.B, m);

                    console.log("AB " + JSON.stringify(AB));
                    console.log("AM " + JSON.stringify(AM));
                    console.log("AM " + JSON.stringify(AC));
                    console.log("BC " + JSON.stringify(BC));
                    console.log("BM " + JSON.stringify(BM));

                    var dotABAM = dot(AB, AM);
                    var dotABAB = dot(AB, AB);
                    var dotBCBM = dot(BC, BM);
                    var dotBCBC = dot(BC, BC);
                    var dotAMAC = dot(AM, AC);
                    var dotACAC = dot(AC, AC);

                    console.log("ABAM " + JSON.stringify(dotABAM));
                    console.log("ABAB " + JSON.stringify(dotABAB));
                    console.log("BCBM " + JSON.stringify(dotBCBM));
                    console.log("BCBC " + JSON.stringify(dotBCBC));
                    console.log("AMAC " + JSON.stringify(dotAMAC));
                    console.log("ACAC" + JSON.stringify(dotACAC));

                    var check = ((0 <= dotABAM && dotABAM <= dotABAB) && (0 <= dotBCBM && dotBCBM <= dotBCBC));
                    console.log(" first check" + check);
                    var check = ((0 <= dotABAM && dotABAM <= dotABAB) && (0 <= dotAMAC && dotAMAC <= dotACAC));
                    console.log("second check" + check);
                    return check;
                }

                return pointInRectangle(m, r);
            }

        //var point = {x: 136, y: 342};

            checkIfTapFallsInBoundary(topLeftBoundary, {x: 136, y: 342});
            checkIfTapFallsInBoundary(topRightBoundary, {x: 136, y: 274});
            checkIfTapFallsInBoundary(bottomRightBoundary, {x: 141, y: 475});
            checkIfTapFallsInBoundary(bottomRightBoundary, {x: 131, y: 272});
            checkIfTapFallsInBoundary(bottomLeftBoundary, {x: 131, y: 272});