PTT數位生活區 / C_and_CPP (C/C++)

[問題] 線條組合是否有比較推薦的結構？

看板C_and_CPP (C/C++)作者 (蘇打)時間16年前 (2009/04/17 13:50), 編輯推噓4(4推 0噓 6→)
留言10則, 6人參與, 最新討論串1/1
最近在解一個問題，關於線段的合併 我找不到一個比較好的結構or演算法來達成 假設我有下列資料 0,0 0,1 0,1 0,5 1,1 0,1 一行表示一條線段，例如第一行表示從座標(0,0)到(0,1)的線段 現在的問題是，我想進行線段合併 亦即範例中的第一行跟第二行可以合併為(0,0)到(0,5)的線段 目前我的作法是將所有線段存在list中 然後跑兩層迴圈一個一個比對 但是這樣的作法感覺有點沒效率@@而且要寫得很複雜 請問有比較好的方式嗎？ 題目不會有線段壓線段的問題 亦即當我有(0,0) - (0,1)這條線段時 就不可能會有另一條線段覆蓋過他，如(0,0) - (0,2) 線段只有分為水平跟垂直兩種，不會有其他類型的轉彎 (如(0,0) - (1,1)這種線段不會出現) 最好的作法就是跑兩層迴圈嗎@@" 煩請高手指導：） -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.138.145.212
推
04/17 13:52, , 1F
先把所有線段排序, 比大小的方式, 先斜率, 再 x, 再 y
04/17 13:52, 1F
→
04/17 13:53, , 2F
同斜率才會接起來, 因為不覆蓋, 所以同斜率中只有
04/17 13:53, 2F
→
04/17 13:53, , 3F
以 x (或 y) 座標來看相鄰的點才有可能接起來
04/17 13:53, 3F
→
04/17 14:11, , 4F
可以先取一點為參考中心，然後取得所有以該參考點為出發點
04/17 14:11, 4F
→
04/17 14:13, , 5F
的向量集合。然後用計算determinant的方式將集合分類
04/17 14:13, 5F
推
04/17 15:03, , 6F
x=k(常數),排序y;y=k,排序x;陣列{0,1,1,5}重複出現就幹掉
04/17 15:03, 6F
推
04/17 15:04, , 7F
那這樣 {0,5} 是啥意思 XD
04/17 15:04, 7F
→
04/17 15:05, , 8F
線段0-5，不排序也沒關係輸出再排就好了
04/17 15:05, 8F
推
04/17 15:49, , 9F
給每個線段一個element number，建立connection matrix
04/17 15:49, 9F
→
04/18 02:48, , 10F
感謝樓上幾位@@我最後是使用s大說得陣列方式解決m(_ _)m
04/18 02:48, 10F
‣ 更多 DRLai 的文章
文章代碼(AID): #19w1Yv7I (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 DRLai 的文章
文章代碼(AID): #19w1Yv7I (C_and_CPP)