一个关于多边形(等距线)缓冲区的高难度算法问题 ( 积分: 300 )

多边形的缓冲区，即求多边形的等距线。

现在已经有比较成熟的算法，参考http://dev.csdn.net/develop/article/13/13811.shtm

已经讲述的比较明确。

我们知道，在多边形向内逐步增大距离d的等距线中，凸多边形有可能会减少边数，

也就是当相邻两个角的角平分线相交的时候，两个角之间的这个边，在等距线中

就没有了。在逐步增大d的过程中，最后所有的凸多边形都会收缩与一个点。



凹多边形在求等距线过程中，等距线有可能会分成多个多边形，当然只是有可能。

我的问题是这样的，像这个图所示http://www.martellelite.com/elitetouch5/cn/images/buffer.jpg

继续增大d，等距线将分成两个多边形，我想求任意凹多边形的这个临界值d,

就是任意凹多边形的等距线即将分解成两个或者多个多边形的临界距离d。

不知道我是不是有没说明白的地方，这个问题我觉得挺高难的，

找不到一个通用的算法。我现在用的算法是，用极小值逐步递增d求等距线，

判断等距线是否自交，如果自交，则根据当前d和上一个d,

用二分求解法求得这个临界值。算法感觉比较土

只求凹多边形的吗

谢谢menxin的回复，
只求凹多边形，因为凸多边形没有这个性质。
而且也不是所有的凹多边形都有这个性质。
只说算法思想就可以了。大家可以讨论一下。

如果把求d最大值这个问题转换成求f(大于180度的角顶点延该角的角分线的位移)最大值会不会有些思路?
你现在的算法相当于穷举吗?

我想了一下,如果转换成求最早消失优角移动的距离(延角分线)应该会简化一些

有一个例程免费的，你可以参考一下，好像叫MathImage什么来的。

我现在的算法是求当前多边形d0距离的等距线，
然后判断等距线是否自交，如果不自交，递增d0 += dt，
dt是一个很小的距离，然后算d0距离的等距线，
判断是否自交。如果自交，大概说明(d0-dt，d0)之间
有一个临界值，用二分求解法求这个临界值。
算法在理论上应该有漏洞，而且比较难看，但是好理解。

menxin的想法肯定是对的，只有大于180度的角顶点才会把
等距线分割成多个多边形。但是有难度的一点在于，当前
角平分线延伸的同时，对面的"即将要跟这个叫平分线相交"
的边也在变化，有可能会"错过"或者"擦肩而过"当前角平分线。

按照我给出的那个buffer.jpg的图片，求临界距离d应该是
把凹角的两个边延长，与对面的那个边相交，得到一个三角形，
求三角形的内心(角平分线交点)p,p点到边的距离既是我们要求的
d值。

但是我不知道怎样把这个规律应用于所有的凹多边形。




二分法的一段程序
double CBevelBuilder::GetSelfIntWidth(const vector<POINT2D> pPoints, double wmin, double wmax)
{
double w;
double EPS = 0.0000001f;
double w1 = wmin;
double w2 = wmax;

while(absv(w2-w1)>EPS)
{
w = (w1+w2)/2;
vector<POINT2D> bufpts;
GetBufPoints(bufpts, pPoints, w);//得到距离为w的等距线
if (SelfIntersect(bufpts)) //判断等距线是否自交
{
w2 = w;
}
else
{
w1 = w;
}
}
return w1;//返回较小的那个
}

你的图里只有一个优角,推广后就应该是计算该多边形内所有优角,没有什么问题

你的算法是二分后递归吧

但是我还是有一些问题想不清楚。
先说只有一个优角ab的任意多边形，则要求跟所有的非相邻边c的延长相交三角形，
三角形的顶点也有可能在c的延长线上。
但是，求得内心p的边距d，求d距离等距线，角ab并不一定会消失。
考虑一下，c在ab很很左边的情况，甚至c在ab角平分线延长方向下边的情况。
。。。。。

是的，二分后递归。

看过了帖子，我想，我们可以换一个角度来看这个问题：将一个随着d的不同而变化的二
维图像问题，转化为一个以d为Z坐标轴的三维问题——二维多边形的每一条边都变成三维空
间里的一个斜面（为了简化计算起见，可以将这些斜面的倾斜度归一化为45度）。在三维空
间这个大背景下，楼主的问题就演变成了三维空间中，两个以上的斜面相交汇的最低点。
思路就说这些了，近在集中精力搞研发，没精力细细琢磨了，还请见谅...

我的MSN: creation_zy ◎ sina.com

多人接受答案了。