0

我需要绘制一组相邻放置的矩形的封闭多边形。

让我们考虑与至少一个其他矩形共享至少一个边缘（或部分边缘）的文本字段。我可以得到矩形点的坐标，所以我基本上有我需要的关于它们的任何数据。

你能想出一个简单的算法/程序来围绕这些对象绘制一个多边形（连接的直线路径）。

这是不同潜在情况（A、B、C 等）的演示。在示例中，AI 还绘制了一个蓝色多边形，这是我需要绘制的路径，勾勒出矩形组。

所有不同的情况

我在这里读过关于凸包之类的东西，但实际上，这看起来是一个简单得多的问题。我想到的一个（开始）解决方案是，我实际需要绘制的点只是任何一对矩形都不共享的点，这意味着作为多个矩形顶点的点是多余的。我找不到的是我需要从一个到下一个画线的顺序。

我目前致力于目标 c，但任何其他语言或算法都会受到赞赏，包括伪。

谢谢！

4

2 回答 2

1

恕我直言，它应该是这样的。制作一个边缘列表，看看是否有一些重叠：如果矩形与 x,y 轴对齐，这应该很简单。您只需找到顶点在相同 x 或 y 上的边，而其他坐标需要介于两者之间。在此之后，剩余的边缘应形成轮廓。

找到共同边的另一种方法是沿您有顶点的每个 x 和 y 轴打破所有矩形。这应该看起来好像您正在将所有行都增长到无穷大。在此之后，所有公共边将具有公共顶点并且可以被消除。

于 2014-06-04T15:09:37.150 回答
1

您有两行和三个不同的值y。假设y0是事物的顶部，y2是底端，并y1标记了两行之间的中间。
每行都有一个最大和一个最小 x 值，假设顶行从x0_min到x0_max，底行从x2_min到x2_max。鉴于这些值，您只需围绕事物绘制：

(x0_min,y0)->
(x0_max,y0)->
(x0_max,y1)->
(x2_max,y1)->
(x2_max,y2)->
(x2_min,y2)->
(x2_min,y1)->
(x0_min,y1)->
(x0_min,y0)
于 2014-06-04T16:40:45.900 回答