从坐标/点数组中创建矩形

Question

http://img853.imageshack.us/img853/2475/picture1eu.jpg

我有一个点/坐标的ArrayList表示一个直线多边形.我现在想要使用ArrayList中存储的Points将这个形状分解为矩形.

我已经开始了一个算法,但我无法完成它,我觉得必须有一个更简单的方法:

ArrayList称为"allCoordinates".
ArrayList"xMatch"和"yMatch"是allCoordinates的子集.

算法:

ArrayList yMatch = All matching Coordinates in respect to 'y'

所以在上图的情况下:(
设置1 = [x1,y1] - [x8,y8],
Set2 = [x7,y7] - [x2,y2],
Set3 = [x4,y4] [x5,x5 ],
Set4 = [x3,y3] [x6,x6])

ArrayList xMatch = All matching Coordinates in respect to 'x'

所以在上图的情况下:(
Set 1 = [x1,y1] - [x2,y2],
Set2 = [x3,y3] - [x4,y4],
Set3 = [x5,y5] [x6,x6 ],
Set4 = [x7,y7] [x8,x8])

所以现在我有两个arrayLists,所有垂直边缘和所有水平边缘.现在我需要一些方法来检查它们是否全部连接在一起？就像我说的那样,必须有一个更简单的方法......？

编辑:

我可以澄清一下,必须使用在现有坐标上开始和结束的相交线来形成矩形.例如,可以从(x6,y6)水平绘制一条线,并在边缘(x1,y1) - (x8,y8)上完成.此行将从现有坐标开始,但不会在现有坐标上完成.因此该行无效.

Answer 1

你可能已经注意到了,我一直在回到这个问题.部分是因为我喜欢弄清楚这些问题,但也因为它让我有点生气,我找不到一个优雅的算法,看起来很容易.

好吧,不要被愚弄,这不是一个简单的问题,你可以通过一些简单的点操作来解决,虽然它看起来确实如此.造成这种情况的部分原因是,尽管您认为自己只使用点,但您也隐含地操纵线段和它们所包围的区域,这些区域也有自己的约束(即段应始终形成一个或更多的闭链,除了在我们用它们定义的顶点之外不能相交.

此外,您的算法必须适用于您提供的任何类型的输入.也就是说,不允许产生任何答案或错误的答案只是因为你喂它的多边形是以你的算法不喜欢的方式定向的.
但是,您可以做的是限制算法接受的输入类型.因此,要求输入多边形仅包含轴对齐的段是完全有效的.
("定向错误的方式"和"仅有轴对齐的段"之间的区别在于,第一个是模糊的标准,如果不对算法进行测试就无法确定 - 而第二个要求可以).

概括地说,我们正在寻找一种方法将任何直线多边形(即仅由轴对齐的线段组成)水平分割成矩形.

直线多边形的示例

这是计划:

1. 选择我们的积木
2. 允许额外的顶点
3. 在网格上对齐.
4. 使用不等大小的网格单元.
5. 你的多边形里面有哪些细胞？
6. 构造矩形.

选择我们的积木

尽管这些都是实现细节,但事先明确这一点可能有助于您更好地了解算法的工作原理.

在代码中,我们将使用以下类型的对象作为基本构建块来表示我们的多边形:

• 点,由x和y坐标组成.(例如使用Point2D.Double)
• 段,由起点和终点组成(例如使用Line2D.Double)
• 多边形,由一段封闭的Segments链组成(例如,使用Line2D.Double的ArrayList),其中一个段在与下一个段的起始点相同的点上结束.

此外,我们将使用网格,可以将其建模为二维数组.

允许额外的顶点.

你说" 矩形必须使用在现有坐标上开始和结束的相交线形成. " 但是,观察到大多数直线多边形不能仅通过使用现有顶点来划分为矩形 - 请参阅上面的示例(以及您之前提供的大篷车示例).

因此,这种约束必须要进行 - 即使我们实际上不会明确地创建新的顶点.

在网格上对齐.

思想实验:如果你的多边形只存在长度为10,20,30或40的(轴对齐)段,即10的倍数怎么办？然后我们可以在网格上投影多边形,并使用位于多边形内部的网格单元来组成矩形.此外,确定这些矩形的尺寸将是轻而易举的:只计算位于多边形内的水平连续单元格的数量并乘以10; 那是你的宽度.

网格对齐的多边形

好主意,除了:

• 多边形不仅包含相同或多个长度的段
• 我们如何确定哪些网格单元位于多边形内？

接下来我们将解决这些问题.

使用不等大小的网格单元.

如果你考虑一下,所有网格单元都没有真正的原因可以具有相同的宽度和高度.因此,我们可以设计一个网格,其间隔方式使我们的多边形完美地对齐它.

要获得网格水平轴的宽度:

• 收集构成多边形的顶点的所有x坐标.
• 对重复值进行重复和排序.
• 然后,两个后续值之间的差异定义该列的宽度.

网格与多边形对齐

显然,细胞的高度可以用同样的方法确定.您应该确定这些宽度和高度,并将它们分别存储在两个名为gridWidths和的数组中gridHeights.

现在我们知道了单元格的数量及其尺寸,我们可以开始对网格内容进行建模.

你的多边形里面有哪些细胞？

请记住,我们的多边形存储为一系列线段.要确定网格单元格是否位于此多边形内部,我们可以使用奇偶规则:构造从外部*多边形到我们要测试的单元格中心的线段,并计算此线段与之间的交叉点数量多边形的片段(即使用Line2D.Double的intersectsLine()方法).如果数字是偶数,它位于多边形之外,如果它是奇数,则它在多边形内.

* - 最好只构建单元格中心之间的水平线段(如示例所示),这样您就不会冒险与段端点相交 - 这可能会计为0或2个交叉点,从而弄乱您的计数总数.

因此,我们将这个网格建模为grid一个二维的布尔数组.以这种方式处理网格的每个单元格,并将相应的点标记grid为true(内部多边形)或false(外部多边形).

基于偶数规则的内部(T)或外部(F)

构造矩形.

现在我们已经有了多边形的网格表示,以及每个单元格的实际宽度和高度,我们可以开始构造矩形.我假设您只对每个矩形的宽度和高度感兴趣,而不是对形成矩形的实际顶点坐标感兴趣(尽管现在也很容易).

Foreach row in grid
  run_start = null
  Foreach cell C in row
    if C is marked as true and run_start = null
      //Found the start of a new run
      run_start = C
    else if C is marked as false and run_start != null
      //Found the end of a run
      The cells [run_start...C] form a horizontal rectangle.
      Use the gridWidths and gridHeights arrays to determine the 
      dimensions, and report this rectangle as a result

      //Prepare for the next run
      run_start = null

多边形,分为矩形.

请注意,左上角的两个矩形共享相同的起始和结束x坐标,因此可以视为一个矩形.如果需要,可以实现合并这些类型矩形的附加传递.

结论

通过将直线多边形映射到网格上,我们可以轻松地将其水平分割为矩形,而无需借助更高级的几何数据结构.
请注意,有一些优化可以使这个算法运行得更快,但我认为这对当前的输入大小并不重要,而且会使实现更加困难.