Helpex - Trao đổi & giúp đỡ Đăng nhập
70

Tôi muốn tìm xem một điểm có nằm trong hình chữ nhật hay không. Hình chữ nhật có thể được định hướng theo bất kỳ cách nào, và không cần phải được căn chỉnh trục.

Một phương pháp tôi có thể nghĩ đến là xoay tọa độ hình chữ nhật và điểm để làm cho trục hình chữ nhật được căn chỉnh và sau đó chỉ cần kiểm tra tọa độ của điểm xem chúng có nằm trong hình chữ nhật hay không.

Phương pháp trên yêu cầu quay và do đó các hoạt động điểm nổi. Có cách nào hiệu quả khác để làm điều này?

70 hữu ích 3 bình luận 114k xem chia sẻ
75

Hình chữ nhật được thể hiện như thế nào? Ba điểm? Bốn điểm? Điểm, cạnh và góc? Hai điểm và một bên? Thứ gì khác? Không biết rằng, bất kỳ nỗ lực để trả lời câu hỏi của bạn sẽ chỉ có giá trị học tập thuần túy.

Trong mọi trường hợp, đối với mọi đa giác lồi (bao gồm cả hình chữ nhật), phép thử rất đơn giản: kiểm tra từng cạnh của đa giác, giả sử mỗi cạnh được định hướng theo hướng ngược chiều kim đồng hồ và kiểm tra xem điểm có nằm bên trái của cạnh không (ở bên trái bằng tay nửa mặt phẳng). Nếu tất cả các cạnh vượt qua bài kiểm tra - điểm nằm bên trong. Nếu ít nhất một lần thất bại - điểm nằm ngoài.

Để kiểm tra xem điểm có (xp, yp)nằm ở phía bên trái của cạnh hay không (x1, y1) - (x2, y2), bạn chỉ cần tính toán

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

Nếu D > 0, điểm nằm ở phía bên tay trái. Nếu D < 0, điểm nằm ở phía bên tay phải. Nếu D = 0, điểm là trên dòng.


Phiên bản trước của câu trả lời này mô tả một phiên bản thử nghiệm bên trái có vẻ khác nhau (xem bên dưới). Nhưng nó có thể dễ dàng chỉ ra rằng nó tính toán cùng một giá trị.

... Để kiểm tra xem điểm có (xp, yp)nằm ở phía bên trái của cạnh hay không (x1, y1) - (x2, y2), bạn cần xây dựng phương trình đường thẳng cho đường thẳng chứa cạnh. Phương trình như sau

A * x + B * y + C = 0

Ở đâu

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

Bây giờ tất cả những gì bạn cần làm là tính toán

D = A * xp + B * yp + C

Nếu D > 0, điểm nằm ở phía bên tay trái. Nếu D < 0, điểm nằm ở phía bên tay phải. Nếu D = 0, điểm là trên dòng.

Tuy nhiên, thử nghiệm này, một lần nữa, hoạt động cho bất kỳ đa giác lồi, có nghĩa là nó có thể quá chung chung cho một hình chữ nhật. Một hình chữ nhật có thể cho phép thử nghiệm đơn giản hơn ... Ví dụ, trong một hình chữ nhật (hoặc trong bất kỳ hình bình hành nào khác), các giá trị ABcó cùng độ lớn nhưng các dấu hiệu khác nhau cho các cạnh đối diện (nghĩa là song song), có thể được khai thác để đơn giản hóa thử nghiệm .

75 hữu ích 5 bình luận chia sẻ
38

Giả sử hình chữ nhật được biểu thị bằng ba điểm A, B, C, với AB và BC vuông góc, bạn chỉ cần kiểm tra các hình chiếu của điểm truy vấn M trên AB và BC:

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

ABlà vectơ AB, có tọa độ (Bx-Ax, By-Ay) và dot(U,V)là sản phẩm chấm của vectơ U và V : Ux*Vx+Uy*Vy.

Cập nhật . Hãy lấy một ví dụ để minh họa điều này: A (5,0) B (0,2) C (1,5) và D (6,3). Từ tọa độ điểm, ta được AB = (- 5,2), BC = (1,3), dot (AB, AB) = 29, dot (BC, BC) = 10.

Đối với điểm truy vấn M (4.2), chúng ta có AM = (- 1,2), BM = (4,0), dot (AB, AM) = 9, dot (BC, BM) = 4. M nằm bên trong hình chữ nhật.

Đối với điểm truy vấn P (6,1), chúng ta có AP = (1,1), BP = (6, -1), dấu chấm (AB, AP) = - 3, dấu chấm (BC, BP) = 3. P không nằm trong hình chữ nhật, vì hình chiếu của nó ở cạnh AB không nằm trong đoạn AB.

38 hữu ích 4 bình luận chia sẻ
17

Tôi đã mượn từ câu trả lời của Eric Bainville:

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

Mà trong javascript trông như thế này:

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; 
}

ví dụ:

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};

sau đó:

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

Đây là một codepen để vẽ đầu ra dưới dạng thử nghiệm trực quan :) http://codepen.io/mattburns/pen/jrrprN

Tìm kiếm một điểm nằm trong một hình chữ nhật hay không?

17 hữu ích 4 bình luận chia sẻ
15
# 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
15 hữu ích 5 bình luận chia sẻ
12

Tôi nhận ra đây là một chủ đề cũ, nhưng đối với bất kỳ ai quan tâm đến việc xem xét nó từ góc độ toán học thuần túy, có một chủ đề tuyệt vời về trao đổi ngăn xếp toán học, ở đây:

https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-r chữ nhật

Chỉnh sửa: Lấy cảm hứng từ chủ đề này, tôi đã kết hợp một phương pháp vectơ đơn giản để nhanh chóng xác định điểm của bạn nằm ở đâu.

Giả sử bạn có một hình chữ nhật với các điểm tại p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y3) và p4 = (x4, y4), đi theo chiều kim đồng hồ. Nếu một điểm p = (x, y) nằm bên trong hình chữ nhật, thì sản phẩm chấm (p - p1). (P2 - p1) sẽ nằm giữa 0 và | p2 - p1 | ^ 2 và (p - p1). (p4 - p1) sẽ nằm giữa 0 và | p4 - p1 | ^ 2. Điều này tương đương với việc lấy hình chiếu của vectơ p - p1 dọc theo chiều dài và chiều rộng của hình chữ nhật, với p1 là gốc.

Điều này có thể có ý nghĩa hơn nếu tôi hiển thị một mã tương đương:

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"

Và đó là nó. Nó cũng sẽ làm việc cho hình bình hành.

12 hữu ích 1 bình luận chia sẻ
6

Nếu bạn không thể giải quyết vấn đề cho hình chữ nhật, hãy thử phân chia vấn đề thành các vấn đề dễ dàng hơn. Chia hình chữ nhật thành 2 hình tam giác một kiểm tra nếu điểm nằm trong bất kỳ điểm nào giống như chúng giải thích ở đây

Về cơ bản, bạn quay vòng qua các cạnh trên mỗi hai cặp đường từ một điểm. Sau đó sử dụng sản phẩm chéo để kiểm tra xem điểm có nằm giữa hai dòng sử dụng sản phẩm chéo không. Nếu nó được xác minh cho cả 3 điểm, thì điểm đó nằm trong tam giác. Điểm hay của phương pháp này là nó không tạo ra bất kỳ lỗi dấu phẩy nào xảy ra nếu bạn kiểm tra các góc.

6 hữu ích 1 bình luận chia sẻ
5
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;}

Tìm kiếm một điểm nằm trong một hình chữ nhật hay không?

Tôi vừa thực hiện Câu trả lời của AnT bằng c ++. Tôi đã sử dụng mã này để kiểm tra xem sự phối hợp của pixel (X, Y) có nằm trong hình dạng hay không.

5 hữu ích 3 bình luận chia sẻ
4

Nếu một điểm nằm trong một hình chữ nhật. Trên máy bay. Đối với tọa độ toán học hoặc trắc địa (GPS)

  • Đặt hình chữ nhật được đặt bởi các đỉnh A, B, C, D. Điểm là P. Tọa độ là hình chữ nhật: x, y.
  • Hãy kéo dài các cạnh của hình chữ nhật. Vậy ta có 4 đường thẳng l AB , l BC , l CD , l DA , hoặc, cho ngắn gọn, l 1 , l 2 , l 3 , l 4 .
  • Lập phương trình cho mọi l i . Các loại phương trình:

    f i (P) = 0.

P là một điểm. Đối với các điểm, thuộc l i , phương trình là đúng.

  • Chúng ta cần các hàm ở bên trái của phương trình. Chúng là f 1 , f 2 , f 3 , f 4 .
  • Lưu ý rằng với mọi điểm từ một phía của l i thì hàm f i lớn hơn 0, đối với các điểm từ phía bên kia f i nhỏ hơn 0.
  • Vì vậy, nếu chúng ta đang kiểm tra P có trong hình chữ nhật, chúng ta chỉ cần cho p nằm đúng cạnh của cả bốn dòng. Vì vậy, chúng ta phải kiểm tra bốn chức năng cho các dấu hiệu của họ.
  • Nhưng bên nào của dòng là đúng, hình chữ nhật thuộc về? Đó là cạnh bên, nơi đặt các đỉnh của hình chữ nhật không thuộc về đường thẳng. Để kiểm tra, chúng ta có thể chọn bất kỳ ai thuộc hai đỉnh không thuộc hai đỉnh.
  • Vì vậy, chúng ta phải kiểm tra điều này:

    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

Các bất đẳng thức không nghiêm ngặt, vì nếu một điểm nằm trên đường viền, nó cũng thuộc về hình chữ nhật. Nếu bạn không cần điểm trên biên giới, bạn có thể thay đổi bất đẳng thức cho những điểm nghiêm ngặt. Nhưng trong khi bạn làm việc trong các hoạt động điểm nổi, sự lựa chọn là không liên quan.

  • Đối với một điểm, đó là trong hình chữ nhật, tất cả bốn bất đẳng thức là đúng. Lưu ý rằng nó cũng hoạt động với mọi đa giác lồi, chỉ có số dòng / phương trình sẽ khác nhau.
  • Điều duy nhất còn lại là có được một phương trình cho một đường thẳng đi qua hai điểm. Đó là một phương trình tuyến tính nổi tiếng. Hãy viết nó cho một dòng AB và điểm P:

    f AB (P) ≡ (x A -x B ) (y P -y B ) - (y A -y B ) (x P -x B )

Việc kiểm tra có thể được đơn giản hóa - hãy đi dọc theo hình chữ nhật theo chiều kim đồng hồ - A, B, C, D, A. Sau đó, tất cả các cạnh chính xác sẽ ở bên phải của các dòng. Vì vậy, chúng ta không cần so sánh với phía có một đỉnh khác. Và chúng ta cần kiểm tra một tập hợp các bất đẳng thức ngắn hơn:

f AB (P)> = 0

f BC (P)> = 0

f CD (P)> = 0

f DA (P)> = 0

Nhưng điều này đúng với bộ tọa độ bình thường, của nhà toán học (từ toán học của trường), trong đó X nằm bên phải và Y ở trên cùng. Và đối với tọa độ trắc địa , như được sử dụng trong GPS, trong đó X ở trên cùng và Y ở bên phải, chúng ta phải biến các bất đẳng thức:

f AB (P) <= 0

f BC (P) <= 0

f CD (P) <= 0

f DA (P) <= 0

Nếu bạn không chắc chắn về hướng của các trục, hãy cẩn thận với kiểm tra đơn giản này - kiểm tra một điểm với vị trí đã biết, nếu bạn đã chọn các bất đẳng thức chính xác.

4 hữu ích 2 bình luận chia sẻ
0

Cách dễ nhất tôi nghĩ đến là chỉ chiếu điểm lên trục của hình chữ nhật. Hãy để tôi giải thích:

Nếu bạn có thể lấy vector từ tâm hình chữ nhật đến cạnh trên hoặc dưới và cạnh trái hoặc phải. Và bạn cũng có một vectơ từ tâm hình chữ nhật đến điểm của bạn, bạn có thể chiếu điểm đó lên các vectơ chiều rộng và chiều cao của mình.

P = vector điểm, H = vector chiều cao, W = vector chiều rộng

Lấy vectơ đơn vị W ', H' bằng cách chia các vectơ cho độ lớn của chúng

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

Trừ khi tôi nhầm, điều mà tôi không nghĩ là tôi ... (Sửa tôi nếu tôi sai) nhưng nếu độ lớn của hình chiếu của điểm của bạn trên vectơ chiều cao thì nhỏ hơn độ lớn của vectơ chiều cao (đó là một nửa chiều cao của hình chữ nhật) và độ lớn của hình chiếu của điểm của bạn trên vectơ chiều rộng là, sau đó bạn có một điểm bên trong hình chữ nhật của bạn.

Nếu bạn có một hệ tọa độ phổ quát, bạn có thể phải tìm ra các vectơ chiều cao / chiều rộng / điểm bằng cách sử dụng phép trừ vector. Vector chiếu là tuyệt vời! nhớ lấy.

0 hữu ích 0 bình luận chia sẻ
loading
Không tìm thấy câu trả lời bạn tìm kiếm? Duyệt qua các câu hỏi được gắn thẻ algorithm geometry , hoặc hỏi câu hỏi của bạn.

Có thể bạn quan tâm

loading