b***m
发帖数: 22 | 1 现在二维平面上有一个任意形状的封闭的弧（没有方程可以描述，就像一滴水掉到玻璃板
上上形成的样子）。如何找出在这个弧的边界上具有最大相对距离的两个点，不一定要确
切的最大，接近最大就可以了。
一种方法是，找出具有最小的x+y的那个点，以及具有最大x+y的那个点，认为它们之间的
距离最大，但是这种方法不见得对阿
苦闷，请问。 | n*******d
发帖数: 650 | 2
板
确
的
this is not even close.
the following is my quick thought, but it is not exact either:
1. take the mean(x1,x2...xn) and mean(y1,y2...yn).
2. draw a line through this point
3. rotate this line till the intersected length is largest
4. keep the line's orientation and translate the line in the direction
perpendicular to the line's orientation to find length even larger
5. goto 3 until ****
【在 b***m 的大作中提到】
: 现在二维平面上有一个任意形状的封闭的弧（没有方程可以描述，就像一滴水掉到玻璃板
: 上上形成的样子）。如何找出在这个弧的边界上具有最大相对距离的两个点，不一定要确
: 切的最大，接近最大就可以了。
: 一种方法是，找出具有最小的x+y的那个点，以及具有最大x+y的那个点，认为它们之间的
: 距离最大，但是这种方法不见得对阿
: 苦闷，请问。
| wh
发帖数: 141625 | 3 How about this:
1. pick any point p0; find p1 such that d(p0, p1) = max(d(p0,p));
2. p0 = p1; go to 1;
stop when you get back to the same point.
【在 b***m 的大作中提到】
: 现在二维平面上有一个任意形状的封闭的弧（没有方程可以描述，就像一滴水掉到玻璃板
: 上上形成的样子）。如何找出在这个弧的边界上具有最大相对距离的两个点，不一定要确
: 切的最大，接近最大就可以了。
: 一种方法是，找出具有最小的x+y的那个点，以及具有最大x+y的那个点，认为它们之间的
: 距离最大，但是这种方法不见得对阿
: 苦闷，请问。
| wh
发帖数: 141625 | 4
can someone show that it is guaranteed to converge to the global maxima?
【在 wh 的大作中提到】
: How about this:
: 1. pick any point p0; find p1 such that d(p0, p1) = max(d(p0,p));
: 2. p0 = p1; go to 1;
: stop when you get back to the same point.
| n*******d
发帖数: 650 | 5
i think u r right but i don't know how to prove it. /shy
【在 wh 的大作中提到】
:
: can someone show that it is guaranteed to converge to the global maxima?
| wh
发帖数: 141625 | 6 I've found a negative example. sigh.
consider this polygon:
A(0,0), B(0,1), C(1-epsilon, 1-epsilon), D(1,0). A->B->C->D->A.
If you start from p0 = A, you'll find p1=C as the furthest. then you'll come
back to A. dead loop.
The global maxima is BD, not AC.
【在 n*******d 的大作中提到】
:
: i think u r right but i don't know how to prove it. /shy
| n*******d
发帖数: 650 | 7 Let's combine the thoughts
1. take the meanX and meanY, call it O
2. find P on the curve where O-P is max
3. start from P then do ur algorithm
【在 wh 的大作中提到】
: I've found a negative example. sigh.
: consider this polygon:
: A(0,0), B(0,1), C(1-epsilon, 1-epsilon), D(1,0). A->B->C->D->A.
: If you start from p0 = A, you'll find p1=C as the furthest. then you'll come
: back to A. dead loop.
: The global maxima is BD, not AC.
|
|
