[問題] 幾何圖形相交之最短路徑

作者: EdisonX (卡卡獸)   2017-04-04 17:17:04
標題有點爛,請見諒。
我先定義了一堆 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 或一些其他想法,請不吝提出,
再次感謝,謝謝。
作者: s89162504 (阿本)   2017-04-04 19:43:00
去修個計算幾何的課吧 關鍵字 凸包 掃描線
作者: FRAXIS (喔喔)   2017-04-04 20:41:00
(1) 你要找 collision detection 的 package(2) 從你的圖看起來外框不一定是 convex 所以要找有支援代數運算的計算幾何 package因為你的要求本質上就是 union(3) 在有 union 的情況下找最短距離 代數運算 package應該辦得到
作者: EdisonX (卡卡獸)   2017-04-04 20:56:00
謝謝 s 大與 F 大給的建議,我再 research, 感謝!
作者: kusork (少女.狗.椰子蟹)   2017-05-16 22:58:00
我是用 Bullet lib. 處理2D/3D的這些問題如果想知道理論概念 就像S大講的找計算幾何的東西來看

Links booklink

Contact Us: admin [ a t ] ucptt.com