a**********s 发帖数: 588 | 1 如果是要求这个闭合曲线包含内环, 但是不超过外环(也就是在阴影区域的流型上面),
能否可以给一些
经典的求法资料。
另外,这个闭合曲线有什么有意思的几何性质?比如说,是不是曲率绝对值的积分最小
之类的?谢谢! |
i******t 发帖数: 370 | 2 You can check path planning literature in robotics. There's a book online:
http://planning.cs.uiuc.edu/
In general, I don't think there's a simple integral cost function...But as a
CS guy, why don't you triangulate the area and run shortest path?
,
【在 a**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果是要求这个闭合曲线包含内环, 但是不超过外环(也就是在阴影区域的流型上面), : 能否可以给一些 : 经典的求法资料。 : 另外,这个闭合曲线有什么有意思的几何性质?比如说,是不是曲率绝对值的积分最小 : 之类的?谢谢!
|
H*******g 发帖数: 1477 | 3 请问大虾还有什么普及的general的算法教材推荐啊?谢谢
a
【在 i******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : You can check path planning literature in robotics. There's a book online: : http://planning.cs.uiuc.edu/ : In general, I don't think there's a simple integral cost function...But as a : CS guy, why don't you triangulate the area and run shortest path? : : ,
|
a**********s 发帖数: 588 | 4 thanks. I could not find any related materials from that book. I was
thinking of triangulating the region and running a standard geodesic path
procedure, as a backup plan.
I am also interested in the geometric properties of this curve. It sounds
like \int_c|\kappa_c| is minimized, and the number of inflections is also
minimized. Yet to study further...
online:
as a
【在 i******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : You can check path planning literature in robotics. There's a book online: : http://planning.cs.uiuc.edu/ : In general, I don't think there's a simple integral cost function...But as a : CS guy, why don't you triangulate the area and run shortest path? : : ,
|
w**********s 发帖数: 291 | 5 如果是多边形的内外界,那么是有最优解法的。这个问题叫做obstacle-avoiding
shortest path。你可以搜搜看怎么扩展到曲线的情况。感觉曲线的情况不容易用cs的
语言描述 |
i******t 发帖数: 370 | 6 \int_c|\kappa_c| seems to have the right intuition, but how to encode the
constraint that the path is within the area is not easy...
btw: algo同学你不是要毕业了么,怎么还在倒腾这些问题
【在 a**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : thanks. I could not find any related materials from that book. I was : thinking of triangulating the region and running a standard geodesic path : procedure, as a backup plan. : I am also interested in the geometric properties of this curve. It sounds : like \int_c|\kappa_c| is minimized, and the number of inflections is also : minimized. Yet to study further... : : online: : as a
|
a**********s 发帖数: 588 | 7 嗯, 我也看到一个"relative convex hull"好像也能解决这个问题..
【在 w**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果是多边形的内外界,那么是有最优解法的。这个问题叫做obstacle-avoiding : shortest path。你可以搜搜看怎么扩展到曲线的情况。感觉曲线的情况不容易用cs的 : 语言描述
|
a**********s 发帖数: 588 | 8
the
应该是可以证明的
嗯哪, 一言难尽, 哭死
【在 i******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : \int_c|\kappa_c| seems to have the right intuition, but how to encode the : constraint that the path is within the area is not easy... : btw: algo同学你不是要毕业了么,怎么还在倒腾这些问题
|
k****g 发帖数: 67 | |
i******t 发帖数: 370 | 10 cmft. 到底咋回事?
【在 a**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : the : 应该是可以证明的 : 嗯哪, 一言难尽, 哭死
|
|
|
D****A 发帖数: 360 | 11 外行乱讲一下,这曲线就像把一根橡皮筋圈套到环形区域里,橡皮筋就是那个几乎处处
可微流形。如果内外环都是多边形,橡皮筋的曲率积分最小(0?),不过不应该是唯一最
小的,所有多边形曲线的曲率积分都是0吧。
那么假设如果橡皮筋的某段是处处可微并且曲率不为0,意味着这段跟环形边界重合并
且是凸的,要不然橡皮筋的长度就不是最短了。显然这种情况下把橡皮筋拉伸成折线,
曲率积分变0长度变长。。。。
所以楼主的结论显然不成立,哈哈哈哈
,
【在 a**********s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果是要求这个闭合曲线包含内环, 但是不超过外环(也就是在阴影区域的流型上面), : 能否可以给一些 : 经典的求法资料。 : 另外,这个闭合曲线有什么有意思的几何性质?比如说,是不是曲率绝对值的积分最小 : 之类的?谢谢!
|
a**********s 发帖数: 588 | 12 嗯,我说成曲线就是希望不要confusing。其实多边形的话,顶点上曲率为无穷
大,每个顶点的
邻接区间的勒贝格积分就是这个定点的拐角。
原来的帖子应该讲得更清楚:在所有包含内环并在外环之内的封闭曲线中,最短的那条
是不是曲率绝对
值的积分也是最小(是不唯一没有错,但是应该找不出更小的),不过我想上面的大伙
都看懂我说的是
这个意思了
【在 D****A 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 外行乱讲一下,这曲线就像把一根橡皮筋圈套到环形区域里,橡皮筋就是那个几乎处处 : 可微流形。如果内外环都是多边形,橡皮筋的曲率积分最小(0?),不过不应该是唯一最 : 小的,所有多边形曲线的曲率积分都是0吧。 : 那么假设如果橡皮筋的某段是处处可微并且曲率不为0,意味着这段跟环形边界重合并 : 且是凸的,要不然橡皮筋的长度就不是最短了。显然这种情况下把橡皮筋拉伸成折线, : 曲率积分变0长度变长。。。。 : 所以楼主的结论显然不成立,哈哈哈哈 : : ,
|
D****A 发帖数: 360 | 13 每个顶点的邻接区间的勒贝格积分就是这个定点的拐角。
如果把曲率想象成趋近无穷大的lebesgue可积曲线,fine
不过即便这样这个积分也可以是arbitrary的
另外不考虑无穷大曲率,就只要把多边形曲线的拐角钝化(曲率固定),积分要多小可
以有多小阿。。。 |
w***n 发帖数: 1084 | 14 The numerical solution is fairly simple. Just make an elastic string, which
tries to minimize its length and satisfy all the boundary constraints at the
same time. |
a**********s 发帖数: 588 | 15 Well, a linear solution exists for polygons.
which
the
【在 w***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : The numerical solution is fairly simple. Just make an elastic string, which : tries to minimize its length and satisfy all the boundary constraints at the : same time.
|