如何表示带孔的多边形？

Question

通常使用顶点在向量中排序为CW或CCW的多边形（2 * 1或1 * 2矩阵）。但是，如何声明向量中带有孔的多边形？

我将对这些多边形应用各种过程，所以我想要一种表达方式，使我可以轻松或有效地工作（即如何在我的程序中声明这种多边形以便简化算法？）

多边形是2D的，我在MATLAB中编程。

编辑1：我要计算这些多边形（带或不带孔）的visibility graph。

Answer 1

正如其他人所提到的，带孔的多边形可以表示为外部边界，再加上零个或多个内部边界，所有这些边界都不相互重叠*。如果使用非零值winding number来确定内/外，一定要指定你的interio r的边界与外部边界相反（逆时针方向为外部，顺时针方向为内部，反之亦然），这样孔内的轮廓积分为零。

仅供参考，这种定义/表示已经在OpenGIS Simple Features Specification（PDF）中正式化。

至于表示：

我可能会在细胞中的K NX2矩阵，其中所述单元阵列中的第一个元素是外部边界，并且其余元件的单元阵列（如果有的话）数组是内部边界。我会使用单元格数组，因为每个边界上的点数可能不相同。

*不重叠=除了在各个点上，例如，一个正方形内钻石：

Answer 2

一个多边形，加上一个多边形孔的列表。只要确保各个多边形不相交。

你打算怎么处理这件事？

Answer 3

听起来像每个洞只是多边形本身内的一个多边形。也许你可以存储一个向量，就像你为外部多边形描述的那样，然后是一个更多的多边形矢量向量。

Answer 4

你在“可见度图”下的含义是什么？

两个“完整”poligons，可能有两种状态，+1或-1。

如果你代表的是一个洞，你有一个状态为+1，另一个状态为-1，表示一个洞，导致状态为0.
如果你有重叠的多边形，最终状态> 1。然后你可以计算一个新的多边形的边界。
如果你有两个带有相交孔的多边形，那么首先计算一个新的多边形的状态，该多边形由两个旧的多边形的外边框组成，然后处理孔。

无论如何，...我认为你得到了一般原则。

不知道如何在matlab中做到这一点，目前为止我只使用它，甚至对于非常简单的事情。

Answer 5

你可以将一个带有孔的多边形分解为两个没有孔的形状。当你在一个复杂的平面上进行轮廓集成时，可以从多边形的一个边缘创建一个“切口”，将其引导至孔的边缘;围绕孔的一侧并返回;然后围绕第二个多边形的另一边进行遍历。最后，每个剪辑之间会有两个路径积分相互抵消。

“可见性图” - 是否用于带阴影的辐射视图因子计算？还是光线追踪图形算法？

Answer 6

假如你想让这个结构尽可能通用（即多边形的多边形孔内有多边形，里面有孔，...），你可能想要有一个树形结构。 Matlab不是很高效地表示树结构，但这里有一个想法...

有一个多边形结构数组。

每个多边形都是一个带有两个字段的结构，'corner'和'children'。

“角”字段包含角（x，y）坐标矩阵，以“data {polyIdx} .corners（：，cornerIdx）”的形式访问。“儿童”字段是多边形的结构数组。

下面是一些代码示例，以与假的孩子，是孔三角形（他们是不是真的有效，但因为他们很可能会重叠：

polygon = struct; 
npoints = 3; 
polygon.corners = rand(2,npoints); 
polygon.children = struct; 
nchildren = 5; 
for c=1:nchildren 
    polygon.children(c).corners = rand(2,npoints); 
    polygon.children(c).children = struct; 
end 

你可以继续递归定义的孩子，备用在创建孔和填充它们之间