เนื้อหาของบทความนี้เป็นพื้นฐานมากสำหรับผู้เริ่มต้นอย่างฉันดังนั้นโปรดถามอัลกอริทึมทั้งหมดเพื่อดูอย่างรวดเร็ว
อ้าง
เป็นที่ทราบกันดีว่าส่วนบรรทัดที่ 1 (a, b) และส่วนบรรทัด 2 (c, d) โดยที่ ABCD เป็นจุดสิ้นสุดค้นหาจุดตัด P ของส่วนของเส้น (คู่ขนานหรือ collinear ถือว่าไม่ต่อเนื่องกัน)
อัลกอริทึม 1: ค้นหาจุดตัดของเส้นตรงที่สองส่วนของเส้นอยู่และจากนั้นพิจารณาว่าจุดตัดอยู่ในสองส่วนของเส้นหรือไม่
เมื่อค้นหาจุดตัดของเส้นตรงเราสามารถค้นหาได้ผ่านสมการทั่วไปของ AX+โดย+C = 0 ของเส้นตรง (ABC ในสมการเป็นค่าสัมประสิทธิ์ไม่ใช่จุดสิ้นสุดที่กล่าวถึงข้างต้น
จากนั้นขึ้นอยู่กับความสัมพันธ์ตำแหน่งระหว่างจุดตัดกับจุดสิ้นสุดของส่วนบรรทัดเราสามารถตัดสินได้ว่าจุดตัดอยู่ในส่วนของเส้นหรือไม่
สูตรมีดังนี้:
<code> ฟังก์ชัน SegmentsIntr (A, B, C, D) { /** 1 แก้ปัญหาระบบของสมการเชิงเส้นและค้นหาจุดตัดของส่วนบรรทัด **/ // ถ้าตัวหารคือ 0 มันเป็นแบบขนานหรือ collinear และไม่ได้ตัดกัน var dismonator = (โดย - ay)*(dx - cx) - (ขวาน - bx)*(cy - dy); if (dismonator == 0) {return false; } // พิกัดทางแยกของเส้นตรงที่ส่วนของเส้นอยู่ที่ (x, y) var x = ((bx - ax) * (dx - cx) * (cy - ay) + (โดย - ay) * (dx - cx) * ขวาน - (dy - cy) * (bx - ax) * cx) var y = - ((โดย - ay) * (dy - cy) * (cx - ax) + (bx - ax) * (dy - cy) * ay - (dx - cx) * (โดย - ay) * cy) / ตัวหาร; / ** 2 พิจารณาว่าจุดตัดอยู่ในสองเซ็กเมนต์ **/ ถ้า (// ทางแยกอยู่ในบรรทัดบรรทัด 1 (x - ax) * (x - bx) <= 0 && (y - ay) * (y - by) <= 0 // และจุดตัด) // กลับไปที่ทางแยก p return {x: x, y: y}}} // มิฉะนั้น, disjoint return false} </code>อัลกอริทึมแรกมีความคิดที่ชัดเจนและเข้าใจง่าย แต่ประสิทธิภาพของมันไม่สูง เพราะมันคำนวณทางแยกก่อนที่จะไม่แน่ใจว่าสี่แยกนั้นใช้ได้หรือไม่ (ในส่วนออนไลน์) ซึ่งต้องใช้เวลามาก
หากจุดตัดในที่สุดพบว่าไม่ถูกต้องการคำนวณก่อนหน้านี้จะไร้ประโยชน์ ยิ่งกว่านั้นกระบวนการคำนวณทั้งหมดก็ซับซ้อนมากเช่นกัน
ดังนั้นมีวิธีที่จะบอกได้ว่ามีจุดตัดที่มีประสิทธิภาพก่อนแล้วจึงคำนวณหรือไม่?
เห็นได้ชัดว่าคำตอบคือใช่ ดังนั้นจึงพบอัลกอริทึมบางอย่าง
อัลกอริทึม 2: พิจารณาว่าจุดสิ้นสุดทั้งสองของแต่ละส่วนของแต่ละบรรทัดอยู่ที่ทั้งสองด้านของส่วนบรรทัดอื่น ๆ หรือไม่ จากนั้นค้นหาจุดตัดของเส้นตรงที่มีสองส่วนของเส้นสองส่วนไม่เช่นนั้นพวกเขาจะไม่ตัดกัน
ขั้นตอนแรกคือการตรวจสอบว่าสองจุดอยู่ทั้งสองด้านของส่วนบรรทัดที่แน่นอนหรือไม่ วิธีการฉายสามารถใช้:
ค้นหาเวกเตอร์ปกติของส่วนบรรทัดจากนั้นฉายจุดลงบนเส้นปกติและในที่สุดก็ตัดสินความสัมพันธ์ระหว่างจุดและส่วนของเส้นตามตำแหน่งที่คาดการณ์ไว้
ดูภาพด้านล่าง
การฉายภาพบนซีเมนต์เซ็กเมนต์บรรทัดปกติของจุด A และจุด B แสดงในรูป ในเวลานี้เรายังต้องฉายซีดีเซ็กเมนต์บรรทัดบนบรรทัดปกติของเรา (เพียงเลือกหนึ่งในจุด C หรือจุด D)
ส่วนใหญ่ใช้สำหรับการอ้างอิง
ในรูปการฉายภาพของจุด A และจุด B จะถูกฉายในทั้งสองด้านของการคาดการณ์จุด C ซึ่งบ่งบอกถึงทั้งสองด้านของซีเมนต์เซ็กเมนต์บรรทัดของส่วนบรรทัด AB
ในทำนองเดียวกันเพียงแค่ตัดสินว่าซีดีอยู่ทั้งสองด้านของส่วนบรรทัด AB อีกครั้งหรือไม่
การค้นหาบรรทัดฐานการฉายภาพและสิ่งอื่น ๆ ฟังดูซับซ้อนมาก แต่ในความเป็นจริงมันค่อนข้างซับซ้อนสำหรับฉัน ฉันไม่รู้อะไรมากเกี่ยวกับความรู้เรขาคณิตเมื่อไม่กี่เดือนที่ผ่านมา (ฉันลืมความรู้เกี่ยวกับเรขาคณิตทั้งหมดเมื่อฉันเรียน: '()'
โชคดีที่การเรียนรู้และการใช้งานไม่ซับซ้อนและมีสูตรที่จะติดตาม
ค้นหาส่วนปกติของกลุ่ม AB:
var nx = by - ay, ny = ax - bx; var normalline = {x: nx, y: ny}; หมายเหตุ: ในกรณีที่ความหมายทางเรขาคณิตของ normalLine.x และ normalLine.y แสดงถึงทิศทางของเส้นปกติไม่ใช่พิกัด
ค้นหาตำแหน่งการฉายของจุด C บนบรรทัดปกติ:
var dist = normalline.x*cx + normalline.y*cy;
หมายเหตุ: "ตำแหน่งการฉาย" นี่คือสเกลาร์ซึ่งแสดงถึงระยะทางไปยังต้นกำเนิดของปกติไม่ใช่พิกัดของจุดฉาย
โดยปกติแล้วจะเพียงพอที่จะรู้ระยะทางนี้
หลังจากที่เราคำนวณการฉายภาพของจุด A (dista), จุด B (distb) และจุด C (distc) ในรูปเราสามารถตัดสินตำแหน่งสัมพัทธ์ได้อย่างง่ายดายตามขนาดที่เกี่ยวข้อง
เมื่อ dista == distb == distc ทั้งสองส่วนจะเป็น collinear
เมื่อ dista == distb! = distc สองส่วนของเส้นจะขนานกัน
เมื่อ DISTA และ DISTB อยู่ในด้านเดียวกันของ DISTC ส่วนสองบรรทัดจะไม่ตัดกัน
เมื่อ DISTA และ DISTB อยู่ฝั่งตรงข้ามของ Distc ไม่ว่าจะเป็นสองส่วนของเส้นที่ตัดกันจะต้องได้รับการตัดสินอีกครั้งว่าความสัมพันธ์ระหว่างจุด C และส่วนของเส้น AB หรือไม่
ขั้นตอนก่อนหน้านี้ใช้เฉพาะ "การตัดสินว่าส่วนบรรทัดตัดกัน" เมื่อผลลัพธ์เป็นจริงเราต้องค้นหาจุดตัดต่อไป
มาพูดคุยเกี่ยวกับกระบวนการค้นหาจุดตัดในภายหลัง ก่อนอื่นให้ดูที่การใช้งานอัลกอริทึมนี้อย่างสมบูรณ์:
ฟังก์ชัน SegmentsIntr (a, b, c, d) {// ปกติ n1 var nx1 = (โดย - ay), ny1 = (ax - bx); // ปกติ n2 var nx2 = (dy - cy), ny2 = (cx - dx); // สองบรรทัดฐานถูกคูณถ้าผลลัพธ์คือ 0 นั่นหมายความว่าส่วนของเส้น AB และเซ็กเมนต์ซีดีนั้นขนานกันหรือ collinear และไม่ตัดกัน VAR DINIONATOR = NX1*NY2 - NY1*NX2; if (dismonator == 0) {return false; } // การฉายภาพใน N2 ปกติ var distc_n2 = nx2 * cx + ny2 * cy; var dista_n2 = nx2 * ax + ny2 * ay-distc_n2; var distb_n2 = nx2 * bx + ny2 * by-distc_n2; // การฉายภาพของจุด A และจุด B อยู่ในด้านเดียวกันของการฉายจุด C (สำหรับกรณีในส่วนของบรรทัดตัวอย่างนี้ถือว่าเป็น disjoint); if (dista_n2*distb_n2> = 0) {return false; } // // ตัดสินความสัมพันธ์ระหว่างจุด C จุด D และส่วนบรรทัด AB หลักการนั้นเหมือนกับข้างต้น // // การฉายภาพบน N1 N1 var dista_n1 = nx1 * ax + ny1 * ay; var distc_n1 = nx1 * cx + ny1 * cy-dista_n1; var distd_n1 = nx1 * dx + ny1 * dy-dista_n1; if (distc_n1*distd_n1> = 0) {return false; } // คำนวณพิกัดทางแยก var fraction = dista_n2 / ส่วน; var dx = เศษส่วน * ny1, dy = -fraction * nx1; return {x: ax + dx, y: ay + dy}; -วิธีที่ใช้ในการค้นหาพิกัดของจุดตัดในตอนท้ายดูแปลก ๆ เล็กน้อยและรู้สึกว่ามันไม่เด่น
ในความเป็นจริงมันคล้ายกับอัลกอริทึมในอัลกอริทึม 1 ยกเว้นว่ามีการคำนวณเงื่อนไขการคำนวณจำนวนมากล่วงหน้า
กล่าวอีกนัยหนึ่งส่วนหนึ่งของอัลกอริทึมในการค้นหาพิกัดของจุดตัดในสองไมล์นั้นทำจากสมการเชิงเส้นของเส้นตรง
ตอนนี้ลองเปรียบเทียบอัลกอริทึมหนึ่งและอัลกอริทึมสองในวิธีที่เรียบง่ายและหยาบและไม่มีหลักวิทยาศาสตร์:
1. ในกรณีที่ดีที่สุดความซับซ้อนของอัลกอริทึมทั้งสองจะเหมือนกัน
2. ในกรณีที่เลวร้ายที่สุดจำนวนการคำนวณอัลกอริทึม 1 และอัลกอริทึม 2 เกือบจะเหมือนกัน
3. อย่างไรก็ตามอัลกอริทึม 2 ให้ "เงื่อนไขก่อนหน้า" เพิ่มเติมดังนั้นโดยเฉลี่ยอัลกอริทึม 2 ควรดีขึ้น
หลังจากการทดสอบจริงสถานการณ์จริงเป็นกรณี
อัลกอริทึมก่อนหน้านี้ทั้งสองนั้นเป็นเรื่องธรรมดาและสามารถรับมือกับสถานการณ์ส่วนใหญ่ได้ แต่ในความเป็นจริงมีอัลกอริทึมที่ดีกว่า
นี่คือสิ่งที่ฉันเพิ่งเรียนรู้เมื่อเร็ว ๆ นี้ (ฉันได้เรียนรู้ตอนนี้และขายตอนนี้ไม่รังเกียจ ... )
อัลกอริทึม 3: พิจารณาว่าจุดสิ้นสุดทั้งสองของแต่ละส่วนของแต่ละบรรทัดอยู่ที่ทั้งสองด้านของส่วนบรรทัดอื่น ๆ หรือไม่ หากคุณพบจุดตัดของเส้นตรงที่มีสองส่วนของเส้นสองส่วนไม่เช่นนั้นพวกเขาจะไม่ตัดกัน
(ฮะ? ทำไมมันถึงรู้สึกเหมือนกับอัลกอริทึม 2? อย่าสงสัยเลยว่ามันเหมือนกัน ... )
อัลกอริทึมที่เรียกว่า 3 เป็นเพียงการปรับปรุงอัลกอริทึม 2 การปรับปรุงหลักคือ:
ความสัมพันธ์ตำแหน่งระหว่างคะแนนและส่วนของสายไม่ได้ถูกตัดสินโดยการคาดการณ์ปกติ แต่โดยพื้นที่ของสามเหลี่ยมที่ประกอบด้วยคะแนนและส่วนของเส้น
มาทบทวนสูตรพื้นที่สามเหลี่ยมก่อน: เป็นที่ทราบกันดีว่าสามคะแนน A (x, y) b (x, y) c (x, y) ของพื้นที่สามเหลี่ยมคือ:
<code> var triarea = ((ขวาน - cx) * (โดย - cy) - (Ay - cy) * (bx - cx)) /2; </code>
เนื่องจากพื้นที่ของสี่เหลี่ยมด้านขนาน (เวกเตอร์สองตัวอยู่ติดกัน) ประกอบด้วยเวกเตอร์สองตัวที่ฟอร์ก == เวกเตอร์สองตัวสูตรข้างต้นจึงไม่ยากที่จะเข้าใจ
ยิ่งไปกว่านั้นเนื่องจากเวกเตอร์มีทิศทางพื้นที่ก็มีทิศทางเช่นกัน โดยปกติเราจะใช้ทวนเข็มนาฬิกาเป็นบวกและตามเข็มนาฬิกาเป็นลบ
ประเด็นสำคัญของอัลกอริทึมที่ได้รับการปรับปรุงคือ:
หากสัญญาณบวกและลบของพื้นที่สามเหลี่ยมที่เกิดขึ้นจาก "ส่วนของเส้น AB และจุด C" นั้นแตกต่างจากพื้นที่สามเหลี่ยมที่เกิดจาก "ส่วนของเส้น AB และจุด D"
จากนั้น Point C และ Point D จะอยู่ที่ทั้งสองด้านของส่วนบรรทัด AB
ดังที่แสดงในรูปด้านล่าง:
สามเหลี่ยมที่แสดงโดยเส้นประในรูปมีทิศทางที่คดเคี้ยวแตกต่างกัน (ลำดับของคำจำกัดความของทั้งสามด้าน) ดังนั้นสัญลักษณ์เชิงบวกและลบของพื้นที่จึงแตกต่างกัน
มาดูรหัสก่อน:
เนื่องจากเราจำเป็นต้องตัดสินสัญลักษณ์เท่านั้นเราไม่จำเป็นต้องแบ่งสิ่งต่อไปนี้ด้วย 2 ในสูตรพื้นที่สามเหลี่ยมก่อนหน้านี้
ฟังก์ชัน SegmentsIntr (A, B, C, D) {// 2 เท่าของพื้นที่ของรูปสามเหลี่ยม ABC VAR AREAGE_ABC = (AX - CX) * (โดย - Cy) - (Ay - Cy) * (Bx - Cx); // 2 เท่าพื้นที่ของสามเหลี่ยม ABD VAR AREAGE_ABD = (AX - DX) * (โดย - DY) - (AY - DY) * (BX - DX); // ถ้าสัญลักษณ์พื้นที่เหมือนกันจุดสองจุดจะไม่ตัดกันในด้านเดียวกัน (ในกรณีของจุดบนส่วนบรรทัดตัวอย่างนี้จะถือว่าเป็น disjoint); if (area_abc*area_abd> = 0) {return false; } // 2 เท่าของพื้นที่ของรูปสามเหลี่ยม CDA VAR AREAGE_CDA = (CX - AX) * (DY - AY) - (CY - AY) * (DX - AX); // 2 เท่าพื้นที่ของสามเหลี่ยม CDB // หมายเหตุ: มีการเพิ่มประสิทธิภาพเล็กน้อยที่นี่ ไม่จำเป็นต้องคำนวณพื้นที่ด้วยสูตร แต่ได้มาจากการเพิ่มและลบพื้นที่ที่รู้จักทั้งสาม var area_cdb = aream_cda + area_abc - พื้นที่ lea_abd; if (seaale_cda * area_cdb> = 0) {return false; } // คำนวณพิกัดทางแยก var t = area_cda / (aream_abd- area_abc); var dx = t*(bx - ax), dy = t*(โดย - ay); return {x: ax + dx, y: ay + dy}; -ในที่สุดส่วนที่คำนวณพิกัดทางแยกนั้นเหมือนกับอัลกอริทึม
จากอัลกอริทึม 2 อัลกอริทึม 3 จะทำให้ขั้นตอนการคำนวณง่ายขึ้นอย่างมากและรหัสนั้นมีความคล่องตัวมากขึ้น อาจกล่าวได้ว่ามันเป็นสิ่งที่ดีที่สุดในสามอัลกอริทึม เช่นเดียวกับผลการทดสอบจริง
แน่นอนว่าเราต้องซื่อสัตย์ใน JavaScript ความซับซ้อนของเวลาของอัลกอริทึมทั้งสามนั้นคล้ายคลึงกันสำหรับการคำนวณทั่วไป (โดยเฉพาะภายใต้เครื่องยนต์ V8)
ในกรณีทดสอบของฉันฉันยังทำการทดสอบทางแยกส่วนหนึ่งล้านระดับผิดปกติเพื่อขยายช่องว่างระหว่างอัลกอริทึมทั้งสาม
สรุป
อย่างไรก็ตามด้วยทัศนคติของการดิ้นรนเพื่อความเป็นเลิศและการเรียนรู้การใฝ่ฝันอัลกอริทึมที่ดีกว่ามักจะมีความสำคัญในเชิงบวกเสมอ ข้างต้นเป็นอัลกอริทึมหลายอย่างที่ใช้ JS เพื่อให้ได้จุดแยกส่วนของเส้น เนื้อหาไม่ลึกซึ้งมาก ฉันหวังว่ามันจะเป็นประโยชน์สำหรับทุกคนในการเรียนรู้ JS