[问题] 几何图形相交之最短路径

楼主: 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