一种基于X轴平行线的孵化算法
一种基于X轴平行线的孵化算法
提问于 2018-06-14 13:53:58
我需要一个算法来孵化一个与X轴线平行的随机多边形.我开始写我认为是解决方案的东西。我的算法实现类似于这个(粗体步骤可能不正确)
- 使用多边形的minY和maxY确定直线的Y轴水平。
- 对于每一个Y轴水平，确定交叉点的X坐标.
- 对每个级别的过境点的x进行排序
- 在每一层为每对Xs绘制线。
这就是结果：结果，我需要一种方法来确定多边形内的是什么，什么不是，或者至少什么是算法。
(我知道这是一种现存的孤注一掷，但我在任何地方都找不到)
Stack Overflow用户
发布于 2018-06-14 14:55:47
为了防弹解决方案：
For all equally spaced Y in the range Ymin to Ymax:
Try all edges PiPj in turn (j is the successor of i):
if (Y >= Yi) != (Y >= Yj):
There is an intersection, compute and store the corresponding X
Sort the X's left to right
Draw all segments (X[2i], Y) to (X[2i+1], Y)一定要如上写交集条件，这将保证在所有情况下都是偶数。
对于多个边的多边形，这是相当低效的，因为你扫描整个多边形的每一个层次。一种更有效的方法是使用一种甜线方法:通过增加最低端点的纵坐标对边缘进行排序。然后，当你增加Y的时候，你会保持一个与当前Y相交的边缘列表。每次你增加Y的时候，你用一个较低的上端点删除边缘，并插入较低端点的边缘(如果一个边缘满足这两个条件，它只是被跳过)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50859201
复制相关文章
相似问题
腾讯云开发者
