从一组二维点中找到最大的矩形网格图案。

Question

从一组二维点中找到最大的矩形网格图案。

4

我一直在努力解决找到最长算术子序列的2D版本。

给定一个包含整数的2D点集，是否存在一种有效的算法来查找这些点中组成NxM矩形网格（例如7x3、4x4、1x3、2x1、1x1）的最大子集，其中网格大小是由NxM计算得出的？注意，网格模式可以沿X和Y方向具有不同的步长。此外，单行（1xM）、单列（Nx1）和单元素（1x1）也被视为特殊的矩形网格模式。

对于图中所示的点，该算法应返回红色的9个大小的3x3矩形网格模式

非常感谢所有建议和参考资料！

- Radiotracer

1

需要更多信息。例如，7x3网格是否允许？如何计算网格的大小？像（点）线（点）线（点）线（点）这样的线条有多大？坐标是整数吗？ - Nikxp

第一个想法：您可以按X坐标对点进行分组并删除那些单独存在于其组中的点（没有任何一对可以形成矩形）。然后，您可以按Y坐标将剩余点分组并再次减少点数。然后再用X重复此操作...直到您可以删除点为止。如果点是随机的，则我认为它可以显着减少点的数量。 - Nikxp

感谢您的建议。我已根据我的理解编辑了问题，尽管我不太明白“哪个大小有一条线，例如（点）线（点）线（点）线（点）？”的意思。 - Radiotracer

顺便提一下，单行（1xM）、单列（Nx1）和单元素（1x1）也被视为特殊的矩形网格模式。 - Radiotracer

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nikxp · Accepted Answer

O(n^4) - （仅适用于小点集）解决方案：您可以使用这个idea，将所有点对都尝试作为最小元素的差。对于(x1, y1)和(x2, y2)这一对，您应该在以(x1, y1)为左上角的最大矩形网格中构建一个小矩形，width = (x2 - x1)，height = (y2 - y1)。有O(n^2)个这样的点对。

要构建最大的矩形网格，您可以针对每个可能的（1xK）水平线，以(x1, y1)为左上角，尝试向下扩展，直到不能再扩展为止。在最坏的情况下，这也是O(n^2)。但如果点集中没有长行，情况就不会那么糟糕。我认为，如果解决方案太长，这里可能存在一些优化提示，因为在此算法中，您会多次检查每个单元格。

如果单行和单列具有非零大小，则无法使用删除没有垂直或水平对的点的建议。