Đường cắt đoạn đường và đoạn

Question

Làm cách nào để phát hiện xem đường (hướng d và -d từ điểm p) và đoạn đường (giữa các điểm p1 và p2) có giao nhau trong 2D không? Nếu họ làm thế nào, làm thế nào tôi có thể nhận được điểm giao nhau của họ.

Có rất nhiều ví dụ về cách phát hiện xem hai đoạn đường có cắt nhau hay không nhưng trường hợp này thậm chí còn đơn giản hơn.

Tôi thấy điều này nhưng tôi không hiểu một phụ điều hành là gì: http://www.loria.fr/~lazard//ARC-Visi3D/Pant-project/files/Line_Segment_Line.html

Answer 1

Nếu đây là một nhiệm vụ 2D (đường và nằm phân khúc trong cùng mặt phẳng và họ được quy định bởi 2 chiều tọa độ), thật dễ dàng.

Tạo một vectơ bình thường d (hướng của đường thẳng).

Tính toán các sản phẩm chấm d * (p1-p) và d * (p2-p). Nếu họ có cùng một dấu hiệu, không có giao lộ. Nếu họ có những dấu hiệu ngược lại, có một giao lộ. Với một chút suy nghĩ, bạn có thể tìm ra cách tính vị trí của giao lộ theo p, p1-p và p2-p.

Answer 2

Bạn có thể chỉ cần kiểm tra xem hai dòng (dòng của bạn và một dòng phân đoạn đường) có cắt nhau và đánh giá điểm giao nhau hay không.

dòng 1: (x, y) (t) = p + t * d; dòng 2: (x, y) (t) = p1 + k * (p2 - p1)

Tại điểm giao nhau: p + t * d = p1 + k * (p2 - p1) - hai phương trình (mỗi x và mỗi y)

Từ các phương trình đó, bạn có thể chỉ cần tìm các tham số k và t.Nếu 0 < k < 1 điểm giao nhau là trong (p1, p2)

Nếu bạn biết k hay t bạn chỉ có thể tính toán giao điểm từ (x, y) (t) = p + t * d hoặc (x, y) (t) = p1 + k * (p2 - p1)

Answer 3

hãy p(x,y) và a hướng của nó phương trình dòng là D = a.x+b nơi b = y - a.x

hãy p1(x1,y1) và p2(x2,y2) một phân khúc mà phương trình là D' = a'.x+b' cho bất kỳ x nào trong [x1;x2] nơi a' = (y2-y1)/(x2-x1) và b' = y2 - a'.x2 = y1 - a'.x1

bạn đã có một ngã tư nếu có một x giữa [x1;x2] mà D = D' do đó nếu X = (b'-b)/(a-a') thuộc về [x1;x2] sau đó Y = a.X+b = a'.X+b cung cấp cho bạn giao điểm P(X,Y)

ví dụ:

let p(255,255), a = 1 =>b = 0

hãy p1(60,179) và p2(168,54)

=>a' = -125/108

=>b' = 24596/99

=>X = (24596/99 - 0)/(1+125/108) = 115,1587983

=>Y = (24596/99 - 0)/(1+125/108) = 115,1587983

X là từ 60 đến 168 để có một giao nhau điểm ion tại P(X,Y)