作者EdisonX (卡卡獸)
看板Prob_Solve
標題[問題] 幾何圖形相交之最短路徑
時間Tue Apr 4 17:17:04 2017
標題有點爛，請見諒。
我先定義了一堆 Shape, 包含了
Line , Circle , Poly , Arc , Ellipse , ... etc，約數十種，
座標系暫採 2D X-Y 浮點數，這些形狀都會有容器管理，如
Array<Line> vLine ;
Array<Circle> vCircle ;
Array<Poly> vPoly ;
Array<Arc> vArc ;
Array<Ellipse> vEllipse ;
這些最後我將它畫在 GUI 上，勢必有些會重疊、相交，故衍生了三個問題，
不否認每個問題都可能再衍生其他問題。
(1) 判斷所有相交點
(2) 若要勾勒出最外框，是否有什麼方法可做到？或是用什麼方式做表達？
< 最外框示意圖：
http://imgur.com/a/x0sF8 >
(3) 先定義移動距離：上述的勾勒出來的外框，本身是一個距離，
若有二個不相交的 group，移動也需要距離，如下圖紅色部份
http://imgur.com/a/mFbko ，請教整張圖的最短離動距離該如何求 ?
第三個問題並不要求最佳解，可接受解即可，惱人的是針對這三個問題沒有太多概念
與想法。第一個問題要解我想到的是暴力、公式解，但也寫得亂七八糟。
可接受 3rd-library，如 cvCanny，
若各位版友有 keyword 或一些其他想法，請不吝提出，
再次感謝，謝謝。
--
就算把新鮮的肝拿回去，還是一樣寫碼到禿頭，加班到天亮，
永遠當老闆的傀儡 你是不是想這麼做？
是的話你就拿回去~ 拿啊！！
九世宅男 : 下輩子不要再讓我幹工程師了 ~
< Kuso 星爺語錄 >
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.72.2
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1491297430.A.865.html
※ 編輯: EdisonX (180.177.72.2), 04/04/2017 17:20:23
1F：推 s89162504: 去修個計算幾何的課吧 關鍵字 凸包 掃描線 04/04 19:43
2F：推 FRAXIS: (1) 你要找 collision detection 的 package 04/04 20:41
3F：→ FRAXIS: (2) 從你的圖看起來外框不一定是 convex 所以要找有支援 04/04 20:43
4F：→ FRAXIS: 代數運算的計算幾何 package 04/04 20:43
5F：→ FRAXIS: 因為你的要求本質上就是 union 04/04 20:44
6F：→ FRAXIS: (3) 在有 union 的情況下找最短距離 代數運算 package 04/04 20:45
7F：→ FRAXIS: 應該辦得到 04/04 20:45
8F：→ EdisonX: 謝謝 s 大與 F 大給的建議，我再 research, 感謝！ 04/04 20:56
9F：推 kusork: 我是用 Bullet lib. 處理2D/3D的這些問題 05/16 22:58
10F：→ kusork: 如果想知道理論概念 就像S大講的找計算幾何的東西來看 05/16 22:59