Làm cách nào để kiểm tra xem một đoạn đường có cắt ngang một mặt bích được căn chỉnh theo trục trong 2D không?

Question

Làm cách nào để kiểm tra xem một đoạn đường có cắt ngang một mặt bích được căn chỉnh theo trục trong 2D không? Phân đoạn được xác định với hai đầu của nó: p1, p2. Hình chữ nhật được xác định với các điểm trên cùng bên trái và dưới cùng bên phải.

Answer 1

Sử dụng Cohen-Sutherland algorithm.

Được sử dụng để cắt nhưng có thể được điều chỉnh một chút cho tác vụ này. Nó chia không gian 2D thành một bảng tic-tac-toe với hình chữ nhật của bạn làm "hình vuông trung tâm".
sau đó nó sẽ kiểm tra xem ai trong số chín vùng mỗi của dòng bạn hai điểm nằm trong.

• Nếu cả hai điểm được trái, phải, trên hoặc dưới, bạn trivially từ chối.
• Nếu một trong hai điểm ở bên trong, bạn thường chấp nhận.
• Trong các trường hợp còn lại hiếm bạn có thể làm toán để giao nhau với bất cứ bên của hình chữ nhật là có thể đến giao nhau với, trên cơ sở đó khu vực mà họ đang ở.

Answer 2

Một tìm kiếm Google nhanh chóng hiện lên một trang với mã C++ để kiểm tra giao lộ.

Về cơ bản, nó kiểm tra giao điểm giữa đường kẻ và mọi đường viền hoặc hình chữ nhật.

Rectangle and line intersection code

Answer 3

Kể từ khi hình chữ nhật của bạn được liên kết, Liang-Barsky có thể là một giải pháp tốt. Nó nhanh hơn Cohen-Sutherland, nếu tốc độ có ý nghĩa ở đây.

Siggraph explanation
Another good description
And of course, Wikipedia

Answer 4

tôi đã làm một giải pháp khăn ăn ít ..

Tiếp theo tìm m và c và do đó phương trình y = mx + c

y = (Point2.Y - Point1.Y)/(Point2.X - Point1.X) 

Thay thế các tọa độ P1 để tìm c

Bây giờ cho một đỉnh hình chữ nhật, đặt giá trị X trong phương trình đường thẳng, có được giá trị Y và xem nếu giá trị Y nằm trong giới hạn hình chữ nhật hiển thị dưới đây

(bạn có thể tìm thấy những giá trị không đổi X1, X2, Y1, Y2 cho hình chữ nhật như vậy)

X1 <= x <= X2 & 
Y1 <= y <= Y2 

Nếu giá trị Y đáp ứng các điều kiện nêu trên và nằm giữa (Point1.Y, Point2.Y) - chúng ta có một giao lộ. Hãy thử mọi đỉnh nếu cái này không thể cắt được.

Answer 5

Wrote khá đơn giản và làm việc giải pháp:

 bool SegmentIntersectRectangle(double a_rectangleMinX, 
           double a_rectangleMinY, 
           double a_rectangleMaxX, 
           double a_rectangleMaxY, 
           double a_p1x, 
           double a_p1y, 
           double a_p2x, 
           double a_p2y) 
    { 
    // Find min and max X for the segment 

    double minX = a_p1x; 
    double maxX = a_p2x; 

    if(a_p1x > a_p2x) 
    { 
     minX = a_p2x; 
     maxX = a_p1x; 
    } 

    // Find the intersection of the segment's and rectangle's x-projections 

    if(maxX > a_rectangleMaxX) 
    { 
     maxX = a_rectangleMaxX; 
    } 

    if(minX < a_rectangleMinX) 
    { 
     minX = a_rectangleMinX; 
    } 

    if(minX > maxX) // If their projections do not intersect return false 
    { 
     return false; 
    } 

    // Find corresponding min and max Y for min and max X we found before 

    double minY = a_p1y; 
    double maxY = a_p2y; 

    double dx = a_p2x - a_p1x; 

    if(Math::Abs(dx) > 0.0000001) 
    { 
     double a = (a_p2y - a_p1y)/dx; 
     double b = a_p1y - a * a_p1x; 
     minY = a * minX + b; 
     maxY = a * maxX + b; 
    } 

    if(minY > maxY) 
    { 
     double tmp = maxY; 
     maxY = minY; 
     minY = tmp; 
    } 

    // Find the intersection of the segment's and rectangle's y-projections 

    if(maxY > a_rectangleMaxY) 
    { 
     maxY = a_rectangleMaxY; 
    } 

    if(minY < a_rectangleMinY) 
    { 
     minY = a_rectangleMinY; 
    } 

    if(minY > maxY) // If Y-projections do not intersect return false 
    { 
     return false; 
    } 

    return true; 
    } 

Answer 6

Những poster ban đầu muốn DETECT một ngã tư giữa đoạn thẳng và đa giác. Không cần phải LOCATE giao lộ, nếu có.Nếu đó là cách bạn muốn nói, bạn có thể làm ít công việc hơn Liang-Barsky hoặc Cohen-Sutherland:

Hãy để điểm cuối của đoạn là p1 = (x1 y1) và p2 = (x2 y2).
Cho các góc của hình chữ nhật là (xBL yBL) và (xTR yTR).

Sau đó, tất cả những gì bạn phải làm là

A. Kiểm tra xem tất cả bốn góc của hình chữ nhật có ở cùng một bên của đường kẻ không. Phương trình ngầm cho một dòng thông qua p1 và p2 là:

F (xy) = (y2-y1) * x + (x1-x2) * y + (x2 * y1-x1 * y2)

Nếu F (xy) = 0, (xy) đang BẬT.
Nếu F (x y)> 0, (x y) là "ở trên" dòng.
Nếu F (x y) < 0, (x y) là "bên dưới" dòng.

Thay thế tất cả bốn góc thành F (x y). Nếu tất cả chúng đều âm hoặc dương, thì không có giao lộ. Nếu một số là dương và một số âm, đi đến bước B.

B. Chiếu điểm cuối lên trục x và kiểm tra xem bóng của phân đoạn có cắt bóng của đa giác hay không. Lặp lại trên trục y:

Nếu (x1> xTR và x2> xTR), không có giao nhau (dòng nằm bên phải hình chữ nhật).
Nếu (x1 < xBL và x2 < xBL), không có giao lộ (dòng nằm bên trái hình chữ nhật).
Nếu (y1> yTR và y2> yTR), không có giao lộ (đường nằm phía trên hình chữ nhật).
Nếu (y1 < yBL và y2 < yBL), không có giao lộ (đường bên dưới hình chữ nhật).
khác, có giao lộ. Do Cohen-Sutherland hoặc bất kỳ mã nào được đề cập trong các câu trả lời khác cho câu hỏi của bạn.

Bạn có thể, tất nhiên, làm B trước, sau đó A.

Alejo

Answer 7

Hoặc chỉ cần sử dụng/sao chép mã đã có trong phương thức Java

java.awt.geom.Rectangle2D.intersectsLine(double x1, double y1, double x2, double y2) 

Dưới đây là phương pháp sau đang được chuyển đổi sang tĩnh để thuận tiện:

/** 
* Code copied from {@link java.awt.geom.Rectangle2D#intersectsLine(double, double, double, double)} 
*/ 
public class RectangleLineIntersectTest { 
    private static final int OUT_LEFT = 1; 
    private static final int OUT_TOP = 2; 
    private static final int OUT_RIGHT = 4; 
    private static final int OUT_BOTTOM = 8; 

    private static int outcode(double pX, double pY, double rectX, double rectY, double rectWidth, double rectHeight) { 
     int out = 0; 
     if (rectWidth <= 0) { 
      out |= OUT_LEFT | OUT_RIGHT; 
     } else if (pX < rectX) { 
      out |= OUT_LEFT; 
     } else if (pX > rectX + rectWidth) { 
      out |= OUT_RIGHT; 
     } 
     if (rectHeight <= 0) { 
      out |= OUT_TOP | OUT_BOTTOM; 
     } else if (pY < rectY) { 
      out |= OUT_TOP; 
     } else if (pY > rectY + rectHeight) { 
      out |= OUT_BOTTOM; 
     } 
     return out; 
    } 

    public static boolean intersectsLine(double lineX1, double lineY1, double lineX2, double lineY2, double rectX, double rectY, double rectWidth, double rectHeight) { 
     int out1, out2; 
     if ((out2 = outcode(lineX2, lineY2, rectX, rectY, rectWidth, rectHeight)) == 0) { 
      return true; 
     } 
     while ((out1 = outcode(lineX1, lineY1, rectX, rectY, rectWidth, rectHeight)) != 0) { 
      if ((out1 & out2) != 0) { 
       return false; 
      } 
      if ((out1 & (OUT_LEFT | OUT_RIGHT)) != 0) { 
       double x = rectX; 
       if ((out1 & OUT_RIGHT) != 0) { 
        x += rectWidth; 
       } 
       lineY1 = lineY1 + (x - lineX1) * (lineY2 - lineY1)/(lineX2 - lineX1); 
       lineX1 = x; 
      } else { 
       double y = rectY; 
       if ((out1 & OUT_BOTTOM) != 0) { 
        y += rectHeight; 
       } 
       lineX1 = lineX1 + (y - lineY1) * (lineX2 - lineX1)/(lineY2 - lineY1); 
       lineY1 = y; 
      } 
     } 
     return true; 
    } 
} 

Answer 8

Tôi đã xem xét vấn đề tương tự và tại đây ' những gì tôi nghĩ ra. Lần đầu tiên tôi so sánh các cạnh và nhận ra điều gì đó. Nếu điểm giữa của một cạnh rơi vào trục đối diện của ô đầu tiên nằm trong phạm vi một nửa độ dài của cạnh đó của các điểm ngoài trên đầu tiên trong cùng một trục, thì có một giao điểm của bên đó ở đâu đó. Nhưng đó là suy nghĩ 1 chiều và yêu cầu nhìn vào mỗi bên của hộp thứ hai để tìm ra. Nó đột nhiên xảy ra với tôi rằng nếu bạn tìm thấy 'điểm giữa' của hộp thứ hai và so sánh tọa độ của điểm giữa để xem liệu chúng có nằm trong khoảng 1/2 chiều dài của một cạnh (của hộp thứ hai) của bên ngoài hay không. kích thước đầu tiên, sau đó có một giao lộ ở đâu đó.

i.e. box 1 is bounded by x1,y1 to x2,y2 
box 2 is bounded by a1,b1 to a2,b2 

the width and height of box 2 is: 
w2 = a2 - a1 (half of that is w2/2) 
h2 = b2 - b1 (half of that is h2/2) 
the midpoints of box 2 are: 
am = a1 + w2/2 
bm = b1 + h2/2 

So now you just check if 
(x1 - w2/2) < am < (x2 + w2/2) and (y1 - h2/2) < bm < (y2 + h2/2) 
then the two overlap somewhere. 
If you want to check also for edges intersecting to count as 'overlap' then 
change the < to <= 

Tất nhiên bạn có thể chỉ là một cách dễ dàng so sánh các cách khác xung quanh (kiểm tra trung điểm của box1 được trong vòng 1/2 chiều dài của dimenions ngoài của hộp 2)

Và thậm chí đơn giản hóa hơn - dịch chuyển trung điểm bởi một nửa độ dài của bạn và nó giống với điểm gốc của hộp đó. Có nghĩa là bây giờ bạn có thể kiểm tra điểm đó để rơi vào phạm vi giới hạn của bạn và bằng cách dịch chuyển đồng bằng lên và sang trái, góc dưới bây giờ là góc dưới của hộp đầu tiên. ít hơn nhiều toán:

(x1 - w2) < a1 < x2 
&& 
(y1 - h2) < b1 < y2 
[overlap exists] 

hoặc không thay:

((x1-(a2-a1)) < a1 < x2) && ((y1-(b2-b1)) < b1 < y2) [overlap exists] 
((x1-(a2-a1)) <= a1 <= x2) && ((y1-(b2-b1)) <= b1 <= y2) [overlap or intersect exists] 

Answer 9

mã ví dụ trong PHP (Tôi đang sử dụng một mô hình đối tượng có phương pháp cho những thứ như getLeft(), GetRight(), getTop(), getBottom() để lấy tọa độ ngoài của đa giác và cũng có getWidth() và getHeight() - tùy thuộc vào tham số nào được cho ăn, nó sẽ tính toán và nhớ cache các ẩn số - nghĩa là tôi có thể tạo đa giác với x1 , y1 và ... w, h hoặc x2, y2 và nó có thể tính toán những người khác)

Tôi sử dụng 'n' để chỉ định thứ e 'new' item được kiểm tra chồng chéo ($ nItem là một thể hiện của đối tượng đa giác của tôi) - các mục cần kiểm tra lại [đây là một chương trình bin/sort knapsack] nằm trong một mảng bao gồm nhiều trường hợp (giống nhau) đối tượng đa giác.

public function checkForOverlaps(BinPack_Polygon $nItem) { 
    // grab some local variables for the stuff re-used over and over in loop 
    $nX = $nItem->getLeft(); 
    $nY = $nItem->getTop(); 
    $nW = $nItem->getWidth(); 
    $nH = $nItem->getHeight(); 
    // loop through the stored polygons checking for overlaps 
    foreach($this->packed as $_i => $pI) { 
    if(((($pI->getLeft() - $nW) < $nX) && ($nX < $pI->getRight())) && 
     ((($pI->getTop() - $nH) < $nY) && ($nY < $pI->getBottom()))) { 
     return false; 
    } 
    } 
    return true; 
} 

Answer 10

Một số mẫu mã cho giải pháp của tôi (trong php):

// returns 'true' on overlap checking against an array of similar objects in $this->packed 
public function checkForOverlaps(BinPack_Polygon $nItem) { 
    $nX = $nItem->getLeft(); 
    $nY = $nItem->getTop(); 
    $nW = $nItem->getWidth(); 
    $nH = $nItem->getHeight(); 
    // loop through the stored polygons checking for overlaps 
    foreach($this->packed as $_i => $pI) { 
    if(((($pI->getLeft() - $nW) < $nX) && ($nX < $pI->getRight())) && ((($pI->getTop() - $nH) < $nY) && ($nY < $pI->getBottom()))) { 
     return true; 
    } 
    } 
    return false; 
} 

Answer 11

Bạn cũng có thể tạo ra một hình chữ nhật ra khỏi phân khúc và kiểm tra xem các hình chữ nhật khác va chạm với nó, vì nó chỉ là một là loạt so sánh. Từ nguồn pygame:

def _rect_collide(a, b): 
    return a.x + a.w > b.x and b.x + b.w > a.x and \ 
      a.y + a.h > b.y and b.y + b.h > a.y 

Answer 12

Dưới đây là một phiên bản javascript của câu trả lời @ metamal của

var isRectangleIntersectedByLine = function (
    a_rectangleMinX, 
    a_rectangleMinY, 
    a_rectangleMaxX, 
    a_rectangleMaxY, 
    a_p1x, 
    a_p1y, 
    a_p2x, 
    a_p2y) { 

    // Find min and max X for the segment 
    var minX = a_p1x 
    var maxX = a_p2x 

    if (a_p1x > a_p2x) { 
    minX = a_p2x 
    maxX = a_p1x 
    } 

    // Find the intersection of the segment's and rectangle's x-projections 
    if (maxX > a_rectangleMaxX) 
    maxX = a_rectangleMaxX 

    if (minX < a_rectangleMinX) 
    minX = a_rectangleMinX 

    // If their projections do not intersect return false 
    if (minX > maxX) 
    return false 

    // Find corresponding min and max Y for min and max X we found before 
    var minY = a_p1y 
    var maxY = a_p2y 

    var dx = a_p2x - a_p1x 

    if (Math.abs(dx) > 0.0000001) { 
    var a = (a_p2y - a_p1y)/dx 
    var b = a_p1y - a * a_p1x 
    minY = a * minX + b 
    maxY = a * maxX + b 
    } 

    if (minY > maxY) { 
    var tmp = maxY 
    maxY = minY 
    minY = tmp 
    } 

    // Find the intersection of the segment's and rectangle's y-projections 
    if(maxY > a_rectangleMaxY) 
    maxY = a_rectangleMaxY 

    if (minY < a_rectangleMinY) 
    minY = a_rectangleMinY 

    // If Y-projections do not intersect return false 
    if(minY > maxY) 
    return false 

    return true 
}