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 的大作中提到】
: 如果是要求这个闭合曲线包含内环, 但是不超过外环(也就是在阴影区域的流型上面),
: 能否可以给一些
: 经典的求法资料。
: 另外，这个闭合曲线有什么有意思的几何性质？比如说，是不是曲率绝对值的积分最小
: 之类的？谢谢！
|
H*******g
发帖数: 1477 | 3 请问大虾还有什么普及的general的算法教材推荐啊？谢谢
a
【在 i******t 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 如果是多边形的内外界，那么是有最优解法的。这个问题叫做obstacle-avoiding
: shortest path。你可以搜搜看怎么扩展到曲线的情况。感觉曲线的情况不容易用cs的
: 语言描述
|
a**********s
发帖数: 588 | 8
the
应该是可以证明的
嗯哪, 一言难尽, 哭死
【在 i******t 的大作中提到】
: \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 的大作中提到】
:
: the
: 应该是可以证明的
: 嗯哪, 一言难尽, 哭死
|
|
|
D****A
发帖数: 360 | 11 外行乱讲一下，这曲线就像把一根橡皮筋圈套到环形区域里，橡皮筋就是那个几乎处处
可微流形。如果内外环都是多边形，橡皮筋的曲率积分最小(0?)，不过不应该是唯一最
小的，所有多边形曲线的曲率积分都是0吧。
那么假设如果橡皮筋的某段是处处可微并且曲率不为0，意味着这段跟环形边界重合并
且是凸的，要不然橡皮筋的长度就不是最短了。显然这种情况下把橡皮筋拉伸成折线，
曲率积分变0长度变长。。。。
所以楼主的结论显然不成立，哈哈哈哈
,
【在 a**********s 的大作中提到】
: 如果是要求这个闭合曲线包含内环, 但是不超过外环(也就是在阴影区域的流型上面),
: 能否可以给一些
: 经典的求法资料。
: 另外，这个闭合曲线有什么有意思的几何性质？比如说，是不是曲率绝对值的积分最小
: 之类的？谢谢！
|
a**********s
发帖数: 588 | 12 嗯，我说成曲线就是希望不要confusing。其实多边形的话，顶点上曲率为无穷
大，每个顶点的
邻接区间的勒贝格积分就是这个定点的拐角。
原来的帖子应该讲得更清楚：在所有包含内环并在外环之内的封闭曲线中，最短的那条
是不是曲率绝对
值的积分也是最小（是不唯一没有错，但是应该找不出更小的），不过我想上面的大伙
都看懂我说的是
这个意思了
【在 D****A 的大作中提到】
: 外行乱讲一下，这曲线就像把一根橡皮筋圈套到环形区域里，橡皮筋就是那个几乎处处
: 可微流形。如果内外环都是多边形，橡皮筋的曲率积分最小(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 的大作中提到】
: 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.
|
