作者DRLai (蘇打)
看板C_and_CPP
標題[問題] 線條組合是否有比較推薦的結構？
時間Fri Apr 17 13:50:47 2009
最近在解一個問題，關於線段的合併
我找不到一個比較好的結構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
1F：推 ledia:先把所有線段排序, 比大小的方式, 先斜率, 再 x, 再 y 04/17 13:52
2F：→ ledia:同斜率才會接起來, 因為不覆蓋, 所以同斜率中只有 04/17 13:53
3F：→ ledia:以 x (或 y) 座標來看相鄰的點才有可能接起來 04/17 13:53
4F：→ karcher:可以先取一點為參考中心，然後取得所有以該參考點為出發點 04/17 14:11
5F：→ karcher:的向量集合。然後用計算determinant的方式將集合分類 04/17 14:13
6F：推 snowlike:x=k(常數),排序y;y=k,排序x;陣列{0,1,1,5}重複出現就幹掉 04/17 15:03
7F：推 Ebergies:那這樣 {0,5} 是啥意思 XD 04/17 15:04
8F：→ snowlike:線段0-5，不排序也沒關係輸出再排就好了 04/17 15:05
9F：推 maplefog:給每個線段一個element number，建立connection matrix 04/17 15:49
10F：→ DRLai:感謝樓上幾位@@我最後是使用s大說得陣列方式解決m(_ _)m 04/18 02:48