Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

Thuật toán tìm giao điểm của tất cả các đoạn thẳng cho trước n đường

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 05:01:41 28 4
mua khóa gpt4 Nike

Tôi đang tìm một thuật toán để tìm tất cả các điểm giao nhau cho n đoạn đường. Sau đây là từ ../../../teaching/373/notes/x06-sweepline.pdf Mã giả của

Đầu vào S[1 .. n] là một phân đoạn mảng hàng. label[i] là nhãn của điểm cuối ngoài cùng bên trái thứ i. 

sắp xếp các điểm cuối của S từ trái sang phải
tạo một chuỗi nhãn trống
với i ← 1 tới 2n
    dòng ← nhãn[i]
    nếu isLeftEndPoint[i]
        Chèn(dòng)
        if Intersect(S[line], S[Successor(line)])
            trả về ĐÚNG
        if Intersect(S[line], S[Predecessor(line)])
            trả về ĐÚNG
    khác
        if Intersect(S[Người kế nhiệm(dòng)], S[Người tiền nhiệm(dòng)])
            trả về ĐÚNG
        Xóa(nhãn[i])

trả về SAI

Áp dụng thuật toán cho tập hợp các đường sau, chỉ kiểm tra một điểm giao nhau. Muốn biết sự tồn tại của 2 giao điểm còn lại tôi phải làm gì? nhập mô tả hình ảnh ở đây

  1. Dòng [1] đi vào
  2. dòng[2] được nhập vào, kiểm tra giao điểm giữa dòng [1] và dòng [2].
  3. dòng[3] được nhập vào, kiểm tra giao điểm giữa dòng [2] và dòng [3].
  4. dòng [4] được nhập, kiểm tra giao điểm giữa dòng [4] và dòng [1]. Tìm giao điểm A.
  5. Dòng [4] rời đi mà không có bất kỳ sự kiểm tra nào.
  6. Dòng [1] rời đi mà không có bất kỳ kiểm tra nào.
  7. Dòng [2] rời đi mà không có bất kỳ sự kiểm tra nào.
  8. Dòng [3] rời đi mà không có bất kỳ sự kiểm tra nào.

câu trả lời hay nhất

Phương trình đường chuẩn Ax+By=C

Độ dốc (m) của đường thẳng xác định bởi phương trình chuẩn là

m = -(A/B)

Phương trình gạch chéo điểm y-y1=m(x-x1)

Thay m = (-A/B) vào phương trình độ dốc điểm y2-y1 = (A/-B)*(x2-x1)

(y2-y1)/(x2-x1) = A/-B

Vì vậy:

A = y2-y1
B = x1-x2C = Ax+By

x = (C-Bởi)/A

y = (C-Ax)/B

Cho hai dòng phương trình A1x1+B1y1=C1 và A2x2+B2y2=C2.
Sau đó chỉ định điểm giao nhau giữa các đường bằng cách sử dụng
A1x+B1y-C1 = A2x+B2y-C2

điểm

A1x+B1y=C1
A2x+B2y=C2

A1B2x+B1B2y=B2C1 (nhân phương trình đầu tiên với B2)
A1B2x+B1B2y-B2C1=0

A2B1x+B1B2y=B1C2 (nhân phương trình thứ hai với B1)
A2B1x+B1B2y-B1C2=0

Làm cho hai phương trình bằng nhau
A1B2x+B1B2y-B2C1=A2B1x+B1B2y-B1C2
A1B2x+B1B2y-B2C1-A2B1x-B1B2y+B1C2=0
A1B2x-B2C1-A2B1x+B1C2=0
A1B2x-A2B1x=B2C1-B1C2
x(A1B2-A2B1)=B2C1-B1C2

x = (B2C1-B1C2)/A1B2-A2B1

A1x+B1y=C1
A2x+B2y=C2

A1A2x+A2B1y=A2C1 (nhân phương trình đầu tiên với A2)
A1A2x+A2B1y-A2C1=0

A1A2x+A1B2y=A1C2 (nhân phương trình thứ hai với A1)
A1A2x+A1B2y-A1C2=0

Làm cho hai phương trình bằng nhau

A1A2x+A2B1y-A2C1=A1A2x+A1B2y-A1C2
A1A2x+A2B1y-A2C1-A1A2x-A1B2y+A1C2=0
A1C2-A2C2=A1B2y-A2B1y
A1B2y-A2B1y=A1C2-A2C2
y(A1B2-A2B1)=A1C2-A2C1
y(A1B2-A2B1)=A1C2-A2C1
y = (A1C2-A2C1)/(A1B1-A2B1)

Mẫu số của y và x giống nhau nên mẫu số = A1B1-A2B1

Vì vậy:

x = (B2C1-B1C2)/mẫu số
y = (A1C2-A2C1)/mẫu số

Đây là hai đường thẳng có điểm (x1, y1), (x2, y2)
Tọa độ x, y của giao điểm với (x3, y3), (x4, y4)

Bây giờ điều này giống nhau đối với các đoạn thẳng, nhưng chúng ta cần kiểm tra xem tọa độ x hoặc y có nằm trong cả hai đoạn hay không. Điều này có nghĩa là giữa tọa độ x của hai đoạn đường có giá trị nhỏ hơn và tọa độ x của hai đoạn đường có giá trị lớn hơn

Đây là chương trình C++ trả về true nếu các đoạn thẳng giao nhau, ngược lại là false. Nếu các đoạn thẳng cắt nhau, nó sẽ lưu điểm giao nhau vào biến i.

điểm cấu trúc
{
    nổi x, y;
};

//p1 và p2 là các điểm của đoạn đầu tiên
//p3 và p4 là các điểm của đoạn thứ hai
giao điểm bool(Điểm p1, Điểm p2, Điểm p3, Điểm p4, Điểm &i)
{
    float max1; //tọa độ x có giá trị lớn hơn ở đoạn 1;
    float min1; // tọa độ x với giá trị nhỏ hơn trong phân đoạn 1;
    float max2; //x-tọa độ có giá trị lớn hơn ở đoạn 2;
    float min2; // tọa độ x với giá trị nhỏ hơn trong phân đoạn 2;
    float A1 = p2.y - p1.y;
    float B1 = p1.x - p2.x;
    float C1 = A1 * p1.x + B1 * p1.y;
    float A2 = p4.y - p3.y;
    float B2 = p3.x - p4.x;
    float C2 = A2 * p3.x + B2 * p3.y;
    mệnh giá float = A1 * B2 - A2 * B1;

if (denom == 0.0) // Khi denom == 0, là do các đường thẳng song song
    return false; //Các đường song song không cắt nhau

ix = (C1 * B2 - C2 * B1)/mệnh giá;
iy = (A1*C2 - A2*C1)/mệnh giá;

nếu (p1.x > p2.x)
{
    max1 = p1.x;
    min1 = p2.x;

}
khác
{
    max1 = p2.x;
    min1 = p1.x;
}

nếu (p3.x > p4.x)
{
    max2 = p3.x;
    min2 = p4.x;

}
khác
{
    max2 = p4.x;
    min2 = p3.x;
}

//kiểm tra xem tọa độ x có nằm trong cả hai phân đoạn không
nếu (ix >= min1 && ix <= max1 &&
    ix >= min2 && ix <= max2)
    trả về đúng sự thật;
return false; //Không giao nhau, giao điểm của các đường không nằm giữa các đoạn

Bây giờ bạn chỉ cần so sánh tất cả các đoạn trong một vòng lặp và lưu các điểm giao nhau vào một mảng.

Về thuật toán tìm giao điểm của tất cả các đoạn thẳng cho n dòng, chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/33819998/

28 4 0
Bài viết khuyến nghị: Tràn ngăn xếp khi tôi triển khai phương pháp quicksort
Bài viết khuyến nghị: Sự cố Lombok với Java 8
Bài viết khuyến nghị: Tại sao và làm thế nào để tránh logic có điều kiện trong các bài kiểm tra đơn vị?
Bài viết khuyến nghị: Java - Tìm kiếm danh sách mảng cho các phần tử có chứa một phần tử
Taklimakan
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress