作者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/cn.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