8

示例 http://xthlegion.co.uk/images/dividerectangle.png 示例 http://xthlegion.co.uk/images/dividerectangle2.png

如果您考虑上面的图像,您可以看到它们由一个大矩形组成,这些矩形通过用户定义的坐标对分解为较小的矩形(示例图像中的每一对都用不同的颜色标识)。

我要做的是仅通过定义连接来获取这些矩形的坐标。边被视为显式连接。顺序无所谓。

有谁知道执行此操作的算法的名称(我敢肯定有一个名字很花哨!)或者有一些示例 C# 代码?一段时间以来,我一直在努力尝试自己做这件事,但收效甚微。又一次数学完全失败!

更新:
只是想我会根据收到的评论快速更新这个问题。

  1. 线必须是直的,因此每对坐标将在一个轴上对齐
  2. 坐标必须从边或另一对的交点开始。第二个坐标必须以类似的方式结束。任何不开始/结束另一个加入的“孤儿”坐标都是非法的,我现在应该忽略它们,一旦我终于开始思考,应该可以进行捕捉。
  3. 尽管在这个例子中,所有的线对都或多或少地整齐地划分了矩形,但在实践中情况并非如此,并且可能有许多线创建了多种尺寸的矩形。

第二次更新 - 它有效:)
示例 http://xthlegion.co.uk/images/dividerectangle3.png

4

3 回答 3

5

您要计算的是已知的线段排列。(这不是一个特别好的名字,但它似乎是我们坚持使用的名字!)计算它:

  1. 找到一组交点(两条线段相交或相交的所有点)。这可以通过Bentley-Ottmann 算法来计算。如果有n 个线段和k个交叉点,则需要 O(( n + k ) log n )。(但如果你只有几条线段,最好使用简单的 O( n 2 ) 算法。)

  2. 通过一些额外的簿记,您可以记录在每个交叉点发生了哪些边,从而计算出与您的一组线段相对应的平面直线图(PSLG)。

  3. 将 PSLG 转换为四边数据结构。这需要两个步骤。首先,通过按角度对入射到每个顶点的边进行排序,找到数据结构中的边-边连接。

  4. 选择一条尚未连接到两个面的边,在未连接的一侧创建一个面,然后围绕该面的边界依次将其连接到每个边。重复直到每条边都连接到两个面。

通常,这会产生矩形以外的面(即使所有线段都是轴对齐的并且所有交点都具有整数坐标),但在您的应用程序中可能不会发生这种情况,或者您可以丢弃非矩形面。

于 2012-12-17T22:15:41.227 回答
2

答案假定以下规则,我认为在任何情况下都是必要的:

用户只能使用水平或垂直线细分现有矩形。

这意味着在您的第一个示例中,细分的顺序必须是:
棕色、黄色、蓝绿色。

对于您使用的任何矩形类,定义两个扩展方法:SubdivideHorizontaland SubdivideVertical,它将接受细分的坐标,并将返回细分的两个结果矩形。
对于您细分的每个矩形,将其替换为两个生成的细分矩形,并递归地重复所有细分。

于 2012-12-17T19:55:41.870 回答
-1

我会做以下事情。

  1. 在外 4 个角的每一个上创建一个点。
  2. 在每个用户定义的点上创建一个点。
  3. 每当一条线穿过一个空点时创建一个点。
  4. 遍历每个正方形并检查所有四个角上是否都有一个点。
于 2012-12-17T19:41:57.177 回答