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 回答