ruby-on-rails - Ruby/C 逻辑来识别类似 Excel 的单元格位置是否重叠

Question

我正在 Rails 应用程序中使用它编写 ruby​​ 代码，我必须接受用户提供的 excel 单元格结构，并且我还必须验证这些单元格结构。

例如:

用户应能够通过用冒号分隔来指定单元格 block ，例如A1:B2应覆盖表单中的 A1、A2、B1、B2 单元格。

同样，用户可以输入许多位置，例如

A1:B1A2:C2A1:F1

但是当用户输入重叠位置时就会出现问题，例如:

A1:D5 和 A2:C3 还有 D1:E1 和 A1:F2。

在这种情况下，A2:C3 位于 A1:D5 block 内，因此用户应该收到一些错误消息(验证错误)，说明这些是重叠位置。

我想到的一个逻辑是将每个位置隐藏为一个唯一的整数值，并使用它我可以区分，但到目前为止我还没有得到任何逻辑来跟踪这种情况。

如果有人知道如何解决这个问题，请告诉我。

谢谢，院长

Answer 1

您想要做的是简单的盒子或矩形碰撞检测 - 这是游戏和图形编程中众所周知且长期解决的问题。

例如，请参阅此博文:

http://www.owenpellegrin.com/articles/vb-net/simple-collision-detection/

您需要将字母数字单元格名称(列 + 行)转换为整数 (x,y) 坐标，以使计算更容易。

因此，从 A1:D5、A2:C3 它们变成坐标:(1,1):(4,5) ，(1,2):(3,3)。

简单的盒子碰撞检测算法将能够确定点 (1,2) 和 (3,3) 都位于矩形内 (1,1):(4,5)，因此第二个矩形完全包含在第一个矩形内，即存在重叠。

就您而言，您还需要确保您的算法将“边缘”碰撞视为重叠。也就是说，A1:B2 在技术上与 B1:C2 重叠，因为它们共享相同的“边缘”(即两个单元格 B1:B2 >).

注意:将每个矩形与其他矩形进行比较以查看它们是否相交的“朴素”算法具有 O(n^2) 复杂度。如果您只处理几十个矩形，那么应该没问题。但是，如果您需要相互检查数千个矩形，那么您可能应该考虑动态构建两个区间树，每个轴一个。