ตรวจสอบว่าส่วนของเส้นตรงสองเส้นตัดกันหรือไม่

ให้สองส่วนบรรทัดได้รับ จุด p1, p2 จากส่วนของบรรทัดแรกและ q1, q2 จากส่วนของเส้นที่สอง เราต้องตรวจสอบว่าส่วนของเส้นตรงทั้งสองตัดกันหรือไม่

เราสามารถพูดได้ว่าส่วนของเส้นตรงทั้งสองตัดกันเมื่อตรงตามกรณีเหล่านี้:

• เมื่อ (p1, p2, q1) และ (p1, p2, q2) มีการวางแนวที่แตกต่างกันและ
• (q1, q2, p1) และ (q1, q2, p2) มีการวางแนวที่แตกต่างกัน

มีอีกเงื่อนไขหนึ่งคือเมื่อ (p1, p2, q1), (p1, p2, q2), (q1, q2, p1), (q1, q2, p2) เป็น collinear

อินพุตและเอาต์พุต

Input:Points of two line-segmentsLine-segment 1:(0, 0) to (5, 5)Line-segment 2:(2, -10) ถึง (3, 10)Output:เส้นกำลังตัดกัน 
อัลกอริทึม
 

 ทิศทาง (a, b, c) 
 

 ป้อนข้อมูล: สามแต้ม
 

 ผลลัพธ์: ตรวจสอบว่าเป็นแนวร่วมหรือทวนเข็มนาฬิกาหรือตามเข็มนาฬิกา
 
Begin val :=(by-ay)*(cx-bx)-(bx-ax)*(cy-by) if val =0 จากนั้นให้คืนค่า collinear อื่นถ้า val <0 แล้วคืนค่าทวนเข็มนาฬิกา ตามเข็มนาฬิกาสิ้นสุด
 

 isIntersect(l1, l2) 
 

 ป้อนข้อมูล: ส่วนของเส้นตรง 2 ส่วน แต่ละเส้นจะมีจุด p1 และ p2 สองจุด
 

 ผลลัพธ์: จริงอยู่ เมื่อพวกมันกำลังตัดกัน
 
เริ่มต้น dir1 =ทิศทาง (l1.p1, l1.p2, l2.p1); dir2 =ทิศทาง(l1.p1, l1.p2, l2.p2); dir3 =ทิศทาง(l2.p1, l2.p2, l1.p1); dir4 =ทิศทาง(l2.p1, l2.p2, l1.p2); ถ้า dir1 ≠ dir2 และ dir3 ≠ dir4 ให้คืนค่า จริง หาก dir1 =0 และ l2.p1 ในบรรทัด l1 ให้คืนค่า จริง หาก dir2 =0 และ l2.p2 ในบรรทัด l1 ให้คืนค่า จริง หาก dir3 =0 และ l1 .p1 บนบรรทัด l2 จากนั้นคืนค่า true ถ้า dir4 =0 และ l1.p2 บนบรรทัด l2 จากนั้นคืนค่า true return falseEnd
 
ตัวอย่าง
 
#includeใช้เนมสเปซ std;struct Point { int x, y;};struct line { Point p1, p2;};bool onLine (บรรทัด l1, Point p) {// ตรวจสอบว่า p อยู่บน บรรทัดหรือไม่ if(px <=max(l1.p1.x, l1.p2.x) &&px <=min(l1.p1.x, l1.p2.x) &&(py <=max(l1.p1 .y, l1.p2.y) &&py <=min(l1.p1.y, l1.p2.y))) คืนค่าจริง คืนค่าเท็จ} ทิศทาง int (จุด a จุด b จุด c) { int val =(b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y); ถ้า (val ==0) คืนค่า 0; //colinear else if(val <0) คืนค่า 2; // ทิศทางทวนเข็มนาฬิกากลับ 1; //ทิศทางตามเข็มนาฬิกา}บูล isIntersect (บรรทัด l1, บรรทัด l2) {// ทิศทางสี่ทิศทางสำหรับสองบรรทัดและจุดของบรรทัดอื่น int dir1 =ทิศทาง (l1.p1, l1.p2, l2.p1); int dir2 =ทิศทาง (l1.p1, l1.p2, l2.p2); int dir3 =ทิศทาง (l2.p1, l2.p2, l1.p1); int dir4 =ทิศทาง (l2.p1, l2.p2, l1.p2); if(dir1 !=dir2 &&dir3 !=dir4) คืนค่าจริง // พวกเขากำลังตัดกัน if(dir1==0 &&onLine(l1, l2.p1)) // เมื่อ p2 ของ line2 อยู่บน line1 คืนค่าจริง; if(dir2==0 &&onLine(l1, l2.p2)) // เมื่อ p1 ของ line2 อยู่ใน line1 จะคืนค่า true; if(dir3==0 &&onLine(l2, l1.p1)) // เมื่อ p2 ของ line1 อยู่ใน line2 จะคืนค่า true; if(dir4==0 &&onLine(l2, l1.p2)) // เมื่อ p1 ของ line1 อยู่ใน line2 จะคืนค่า true; return false;}int main() { บรรทัด l1 ={{0,0}, {5, 5}}; บรรทัด l2 ={{2,-10}, {3, 10}}; if(isIntersect(l1, l2)) cout <<"เส้นตัดกัน"; else cout <<"เส้นไม่ตัดกัน";}
 
ผลลัพธ์
 
เส้นกำลังตัดกัน