基本上是这个问题,但相反:如何计算多边形的圆角?
我(至少)有一个由边缘组成的多边形,其中有圆角,我想完全消除所有圆角。
首先,设置:
我使用从左向右移动的垂直扫描线来处理多边形,所以我无法“展望未来”,因此我不知道我是否处于圆角,直到我消耗了所有有角度的边缘一条水平边和一条垂直边之间符合以下标准(其中一个是角的起点,另一个是圆角的终点)。
我已经想出了一个解决方案,但这是一个蛮力解决方案,所以我对此感觉不太好,而且可能很容易出错,所以我对实施它犹豫不决。
圆角以垂直或水平边缘开始,以水平或垂直边缘结束。其间有许多小角度边缘,给人一种“圆角”的错觉。
为了确定任何特定的有角度的边缘是否是用于构造圆角的有角度的边缘,我提出了以下标准:
我的想法是,每当我检测到第一个符合该法案的有角度的边缘时,我都会记住前一个边缘(水平或垂直),然后继续消耗有角度的边缘,直到其中任何一个有角度的边缘不符合标准并且它不是一个圆角,或者我找到另一个封闭圆角的垂直或水平边缘。我也记得那个边缘。
然后,我将删除多边形起始边和结束边之间消耗的所有有角度的边,并延伸开始圆角的垂直和水平边,直到它们在一点处相交。完成
这会拉直拐角,但正如我所说,我对这个解决方案感觉不太好,而且我真的觉得它会很慢,因为我要处理大量的边缘。另外,重要的是,我觉得这个解决方案很难不出现错误,并且可能会出现误报。
有什么想法吗?
实际上,你的想法听起来不错。作为后处理,运行整个多边形集应该花费线性时间。
不过,不要从“角候选”边缘开始处理。从每个“真实”水平或垂直边缘开始处理,并检查每个末端是否连接到可删除的圆角。
听起来您正在使用扫描线算法从线段构造多边形。在这种情况下,每次添加真正的水平或垂直边缘时,您都可以检查它是否连接到预先存在的可删除角。当添加其两个真实边缘中的较晚者时,每个圆角都将被删除。这样做的好处是只需检查每个角一次。
如果在找到所有多边形后将整个过程作为后处理运行,那么您可以找到所有真实的边缘,然后检查以顺时针方向远离它的圆角。这将再次仅检查每个角一次。