我有一组定义多边形的 (x,y) 值。多边形是根据点的位置 * 铅笔大小绘制的。问题是我想绘制这种形状的边框,忽略内部顶点。看这个例子,黑色的顶点是我感兴趣的,我想去掉黄色的。
我想把 X 放在另一个数组中,顺时针排列。一直在考虑评估每个点以查看是否有邻居以及在哪里(北、南、东、西),但检查每个顶点似乎过于繁琐,我相信必须是另一种经过验证且更优雅的算法。
任何提示?
通常,多边形由轮廓定义。这是一种不幸的格式,你必须在那里处理。
如果它们是这样布局的(在具有相同 y 坐标的行中),那么您可以对数组进行排序,首先按 x,然后按 y,然后取第一个点,y 的任何变化周围的两个点,然后最后一点来形成你的大纲。
如果事情的真实状态有点混乱,那么您可能想要研究“阿尔法形状”。一些链接:http ://biogeometry.duke.edu/software/alphashapes/,http : //cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html
由于您的“点”只是小方块,因此听起来您的内部点(那些对形状边界没有贡献的点)只是那些(x-1,y)
, (x+1,y)
, (x,y-1)
, 和(x,y+1)
也是所有点的点。
您可以通过将所有点放入哈希表(或许多其他索引结构之一)中来快速进行该测试。
顺时针订购只需要走边界。你必须决定你想对漏洞做什么,如果有的话。
制作精灵边框,将其放置在每个正方形的相同位置并在后面排序 oderlayout