ในทางเรขาคณิตโครงร่างเส้นตรงเป็นวิธีการแสดงรูปหลายเหลี่ยมด้วยโครงร่างเชิงโทโพโลยีมีลักษณะคล้ายกับแกนกลาง ในบางแง่ แต่แตกต่างกันตรงที่โครงร่างประกอบด้วยส่วนของเส้นตรง ในขณะที่แกนกลางของรูปหลายเหลี่ยมอาจเกี่ยวข้องกับเส้นโค้งพาราโบลา อย่างไรก็ตาม ทั้งสองอย่างมีความสมมูลกันในเชิงโฮโมโทปีกับรูปหลายเหลี่ยมพื้นฐาน^{[ 1 ]}

โครงร่างเส้นตรงได้รับการกำหนดครั้งแรกสำหรับรูปหลายเหลี่ยมแบบง่ายโดยAichholzer et al. (1995) [ ^{2 ]}และขยายไปสู่กราฟเส้นตรงระนาบ (PSLG) โดยAichholzer & Aurenhammer (1996) [ ^{3 ] ใน} การตีความว่าเป็นการฉายภาพของพื้นผิวหลังคา โครงร่างเหล่านี้ได้รับการกล่าวถึงอย่างกว้างขวางโดย GA Peschka ⁽ 1877 ) ^{[ 4 ]}

โครงร่างเส้นตรงของรูปหลายเหลี่ยมถูกกำหนดโดยกระบวนการหดตัวอย่างต่อเนื่อง ซึ่งขอบของรูปหลายเหลี่ยมจะเคลื่อนที่เข้าด้านในขนานกับตัวเองด้วยความเร็วคงที่ ขณะที่ขอบเคลื่อนที่ในลักษณะนี้ จุดยอดที่ขอบคู่หนึ่งมาบรรจบกันก็จะเคลื่อนที่ไปด้วย โดยความเร็วจะขึ้นอยู่กับมุมของจุดยอดนั้น หากจุดยอดที่เคลื่อนที่เหล่านี้ชนกับขอบที่ไม่ติดกัน รูปหลายเหลี่ยมจะถูกแบ่งออกเป็นสองส่วนโดยการชน และกระบวนการจะดำเนินต่อไปในแต่ละส่วน โครงร่างเส้นตรงคือชุดของเส้นโค้งที่เกิดจากการเคลื่อนที่ของจุดยอดในกระบวนการนี้ ในภาพประกอบ รูปด้านบนแสดงกระบวนการหดตัว และรูปตรงกลางแสดงโครงร่างเส้นตรงเป็นสีน้ำเงิน

โครงร่างเส้นตรงสามารถคำนวณได้โดยการจำลองกระบวนการหดตัวซึ่งเป็นกระบวนการที่กำหนดไว้ มีการเสนออัลกอริธึมหลายแบบสำหรับการคำนวณโครงร่างเส้นตรง โดยแต่ละแบบแตกต่างกันในข้อสมมติฐานที่ใช้กับข้อมูลป้อนเข้าและโครงสร้างข้อมูลที่ใช้ในการตรวจจับการเปลี่ยนแปลงเชิงการจัดเรียงของรูปหลายเหลี่ยมที่ป้อนเข้าขณะที่มันหดตัว

อัลกอริทึมต่อไปนี้พิจารณาอินพุตที่เป็นรูปหลายเหลี่ยมรูปหลายเหลี่ยมที่มีรูหรือ PSLG สำหรับอินพุตที่เป็นรูปหลายเหลี่ยม เราจะใช้สัญลักษณ์n แทนจำนวนจุดยอด และ rแทนจำนวนจุดยอดสะท้อน (เว้า กล่าวคือ มุมมากกว่าπ ) หากอินพุตเป็น PSLG เราจะพิจารณาโครงสร้างหน้าคลื่นเริ่มต้น ซึ่งก่อตัวเป็นเซตของรูปหลายเหลี่ยม และอีกครั้ง เราจะใช้สัญลักษณ์n แทน จำนวนจุดยอด และr แทน จำนวนจุดยอดสะท้อนเทียบกับทิศทางการแพร่กระจาย อัลกอริทึมส่วนใหญ่ที่ระบุไว้ในที่นี้ได้รับการออกแบบและวิเคราะห์ในแบบจำลองการคำนวณ RAM จริง

• Aichholzer et al. ^{[ 2 ] [ 3 ]}แสดงให้เห็นวิธีการคำนวณโครงร่างตรงของ PSLG ในเวลา O( n ³  log  n ) หรือแม่นยำกว่านั้นคือเวลา O(( n ² + f ) log  n ) โดยที่nคือจำนวนจุดยอดของรูปหลายเหลี่ยมที่ป้อนเข้ามา และfคือจำนวนเหตุการณ์พลิกระหว่างการสร้าง ขอบเขตที่ดีที่สุดที่ทราบสำหรับfคือ O( n ³ )
•  Huber และ Held ( 2010 , 2011 ) ได้นำเสนอ อัลกอริทึมที่มีเวลาทำงานกรณีเลวร้ายที่สุดใน O( nr  log n) หรือเพียงแค่ O( n ² log n) โดย พวกเขาโต้แย้งว่าแนวทางของพวกเขาน่าจะทำงานได้ในเวลาใกล้เคียงกับเชิงเส้นสำหรับอินพุตจำนวนมาก^{[ 5 ] [ 6 ]}
• Petr Felkel และ Štěpán Obdržálek ออกแบบอัลกอริทึมสำหรับรูปหลายเหลี่ยมแบบง่ายซึ่งกล่าวกันว่ามีประสิทธิภาพ O( nr + n log r ) ^{[ 7 ] [ 8 ]}อย่างไรก็ตาม ได้มีการแสดงให้เห็นแล้วว่าอัลกอริทึมของพวกเขานั้นไม่ถูกต้อง^{[ 9 ] [ 10 ]}
• โดยใช้โครงสร้างข้อมูลสำหรับปัญหาคู่ที่ใกล้ที่สุดแบบสองสีEppsteinและ Erickson ได้แสดงวิธีการสร้างปัญหาโครงร่างตรงโดยใช้การอัปเดตโครงสร้างข้อมูลคู่ที่ใกล้ที่สุดจำนวนเชิงเส้น โครงสร้างข้อมูลคู่ที่ใกล้ที่สุดที่อิงตามควอดทรีให้ขั้นตอนวิธีเวลา O( nr  +  n  log  n ) หรือโครงสร้างข้อมูลที่ซับซ้อนกว่ามากนำไปสู่ขอบเขตเวลาเชิงอะซิมโทติกที่ดีกว่าO( n ^{1 + ε} + n ^{8/11 + ε} r ^{9/11 + ε} )หรืออย่างง่ายO( n ^{17/11 + ε} )โดยที่ ε เป็นค่าคงที่ใดๆ ที่มากกว่าศูนย์^{[ 11 ]}นี่ยังคงเป็นขอบเขตเวลากรณีเลวร้ายที่สุดที่ดีที่สุดที่รู้จักสำหรับการสร้างโครงร่างตรงด้วยอินพุตที่ไม่จำกัด แต่มีความซับซ้อนและยังไม่ได้นำไปใช้
• สำหรับรูปหลายเหลี่ยมแบบง่ายที่อยู่ในตำแหน่งทั่วไปปัญหาการสร้างโครงร่างเส้นตรงนั้นง่ายกว่า Cheng, Mencel และ Vigneron ได้แสดงวิธีการคำนวณโครงร่างเส้นตรงของรูปหลายเหลี่ยมแบบง่ายในเวลา O( n log n log r + r ^{4/3 + ε} ) ^{[ 12 ]} ในกรณีที่เลวร้ายที่สุดrอาจอยู่ในลำดับของnซึ่งในกรณีนี้ขอบเขตเวลานี้อาจลดรูปเหลือ O( n ^4/3+ε ) หากจุดยอดของรูปหลายเหลี่ยมที่ป้อนเข้ามามีพิกัดเชิงตรรกะ O(log n) บิต อัลกอริทึมของพวกเขาสามารถปรับปรุงให้ทำงานได้ในเวลา O( n  log  n ) แม้ว่ารูปหลายเหลี่ยมที่ป้อนเข้ามาจะไม่ได้อยู่ในตำแหน่งทั่วไปก็ตาม
• รูปหลายเหลี่ยมโมโนโทนเมื่อเทียบกับเส้นตรงLคือรูปหลายเหลี่ยมที่มีคุณสมบัติว่าเส้นตรงทุกเส้นที่ตั้งฉากกับLจะตัดกับรูปหลายเหลี่ยมในช่วงเวลาเดียว เมื่ออินพุตเป็นรูปหลายเหลี่ยมโมโนโทน โครงร่างเส้นตรงของมันสามารถสร้างได้ในเวลา O( n  log ²  n ) ^{[ 13 ]}

แต่ละจุดภายในรูปหลายเหลี่ยมที่ป้อนเข้าสามารถยกขึ้นสู่พื้นที่สามมิติได้โดยใช้เวลาที่กระบวนการหดตัวไปถึงจุดนั้นเป็นพิกัด z ของจุดนั้น พื้นผิวสามมิติที่ได้จะมีระดับความสูงคงที่ที่ขอบของรูปหลายเหลี่ยม และมีความลาดชันคงที่จากขอบเหล่านั้น ยกเว้นจุดของโครงร่างตรงเอง ซึ่งเป็นจุดที่ส่วนของพื้นผิวที่ทำมุมต่างกันมาบรรจบกัน ด้วยวิธีนี้ โครงร่างตรงสามารถใช้เป็นชุดของเส้นสันหลังคาของอาคาร โดยอิงจากผนังในรูปทรงของรูปหลายเหลี่ยมเริ่มต้น^{[ 2 ] [ 14 ]}รูปด้านล่างในภาพประกอบแสดงพื้นผิวที่เกิดจากโครงร่างตรงในลักษณะนี้

Demaine, Demaine และ Lubiw ใช้โครงร่างตรงเป็นส่วนหนึ่งของเทคนิคการพับกระดาษเพื่อให้สามารถตัดรูปหลายเหลี่ยมที่กำหนดได้ด้วยการตัดตรงเพียงครั้งเดียว ( ทฤษฎีการพับและตัด ) และปัญหาการออกแบบโอริกา มิที่เกี่ยวข้อง ^{[ 15 ]}

Barequet และคณะใช้โครงกระดูกตรงในอัลกอริทึมเพื่อค้นหาพื้นผิวสามมิติที่แทรกระหว่างโซ่รูปหลายเหลี่ยม สอง โซ่ ที่กำหนด ^{[ 16 ]}

Tănase และ Veltkamp เสนอให้แยกรูปหลายเหลี่ยมเว้าออกเป็นส่วนรวมของบริเวณนูนโดยใช้โครงร่างตรงเป็นขั้นตอนการประมวลผลล่วงหน้าสำหรับการจับคู่รูปร่างในการประมวลผลภาพ^{[ 17 ]}

Bagheri และ Razzazi ใช้โครงร่างตรงเพื่อนำทางการวางจุดยอดใน อัลกอริทึม การวาดกราฟซึ่งการวาดกราฟถูกจำกัดให้อยู่ภายในขอบเขตรูปหลายเหลี่ยม^{[ 18 ]}

โครงร่างตรงยังสามารถใช้สร้างเส้นโค้งออฟเซ็ตของรูปหลายเหลี่ยมที่มีมุมตัดเฉียงได้ คล้ายกับการสร้างเส้นโค้งออฟเซ็ตที่มีมุมโค้งมนที่เกิดจากแกนกลาง Tomoeda และ Sugihara ใช้แนวคิดนี้ในการออกแบบป้ายที่มองเห็นได้จากมุมกว้าง โดยมีลักษณะเหมือนมีความลึก^{[ 19 ]}ในทำนองเดียวกัน Asente และ Carr ใช้โครงร่างตรงในการออกแบบการไล่ระดับสีที่เข้ากับโครงร่างตัวอักษรหรือรูปทรงอื่นๆ^{[ 20 ]}

เช่นเดียวกับโครงกระดูกประเภทอื่นๆ เช่นแกนกลางโครงกระดูกตรงสามารถใช้เพื่อยุบพื้นที่สองมิติให้เหลือเพียงการแสดงพื้นที่แบบหนึ่งมิติที่เรียบง่าย ตัวอย่างเช่น Haunert และ Sester อธิบายการประยุกต์ใช้โครงกระดูกตรงประเภทนี้ในระบบสารสนเทศทางภูมิศาสตร์ในการค้นหาเส้นศูนย์กลางของถนน^{[ 21 ] [ 22 ]}

ใน การสร้างตาข่าย ด้วยวิธีไฟไนต์เอเลเมนต์ (FEM) แนวคิดโครงกระดูกตรงและการหดตัวตามชั้นถูกนำมาใช้เพื่อแยกโดเมนทางเรขาคณิตที่ซับซ้อนสำหรับการสร้างแบบจำลองอุทกพลศาสตร์และน้ำตื้น โดยการวิเคราะห์ชั้นการแพร่กระจายของหน้าคลื่น อัลกอริทึมสามารถแปลงตาข่ายสามเหลี่ยมที่ไม่มีโครงสร้างให้เป็นตารางสี่เหลี่ยมและตารางองค์ประกอบผสมที่จัดเรียงโดยอัตโนมัติในขณะที่สอดคล้องกับฟังก์ชันขนาดทางเรขาคณิตพื้นฐาน^{[ 23 ]}

ต้นไม้ทุก ต้น ที่ไม่มี จุดยอดที่มี ดีกรี -2 สามารถสร้างเป็นโครงร่างตรงของรูปหลายเหลี่ยมนูนได้^{[ 24 ]}โครงร่างนูนของรูปทรงหลังคาที่สอดคล้องกับโครงร่างตรงนี้ก่อให้เกิดการสร้างแบบ Steinitzของกราฟ Halinที่สร้างขึ้นจากต้นไม้โดยการเชื่อมต่อใบของมันในวงจร

Barequet และคณะได้กำหนดโครงร่างแบบตรงสำหรับรูปทรงหลาย เหลี่ยมสามมิติ อธิบายอัลกอริธึมสำหรับการคำนวณ และวิเคราะห์ความซับซ้อนของโครงร่างดังกล่าวบนรูปทรงหลายเหลี่ยมหลายประเภท^{[ 25 ]}

Huber และคณะได้ตรวจสอบพื้นที่เมตริกซึ่งแผนภาพ Voronoiและโครงร่างเส้นตรงที่สอดคล้องกันจะตรงกัน สำหรับสองมิติ ลักษณะเฉพาะของพื้นที่เมตริกดังกล่าวมีความสมบูรณ์ สำหรับมิติที่สูงกว่า วิธีนี้สามารถตีความได้ว่าเป็นการวางนัยทั่วไปของโครงร่างเส้นตรงของรูปร่างอินพุตบางอย่างไปยังมิติใดๆ โดยใช้แผนภาพ Voronoi ^{[ 26 ]}

• เอริคสัน, เจฟฟ์. "โครงร่างตรงของรูปหลายเหลี่ยมอย่างง่าย "
• โครงกระดูกตรง 2 มิติในCGALซึ่งเป็นไลบรารีอัลกอริทึมเรขาคณิตเชิงคำนวณ
• โครงร่างตรงสำหรับรูปหลายเหลี่ยมที่มีรู เครื่องมือสร้างโครงร่างตรงที่เขียนด้วยภาษา Java
• Amit Parnerkar, Sarnath Ramnath. " การออกแบบอัลกอริทึมที่มีประสิทธิภาพเพื่อค้นหาโครงร่างเส้นตรงของรูปหลายเหลี่ยมอย่างง่ายในเวลาO(n log n) "
• STALGO : "STALGO คือซอฟต์แวร์ C++ ระดับสูงสำหรับการคำนวณโครงร่างเส้นตรงและเส้นโค้งออฟเซ็ตแบบตัดเฉียง" โดย Stefan Huber