如何检查笛卡尔坐标是否有效地构成了矩形？

发布于 2024-11-07 19:49:12 字数 520 浏览 0 评论 0原文

情况如下：

有N个数组。
在每个数组（0..N-1）中存储了（x，y）元组（笛卡尔坐标）
每个数组的长度可以不同

我想提取构成完整数组的坐标组合的子集大小为 N 的矩形。换句话说；所有笛卡尔坐标都彼此相邻。

示例：

findRectangles({
    {*(1,1), (3,5), (6,9)}, 
    {(9,4), *(2,2), (5,5)}, 
    {(5,1)},
    {*(1,2), (3,6)}, 
    {*(2,1), (3,3)}
})

产生以下结果：

[(1,1),(1,2),(2,1),(2,2)],
..., 
...(other solutions)...

没有两个点可以来自同一集合。

我首先只是计算了笛卡尔积，但这很快就变得不可行（目前我的用例有 18 个点数组，每个数组大致包含 10 个不同的坐标）。

原文

The situation is as follows:

There are N arrays.
In each array (0..N-1) there are (x,y) tuples (cartesian coordinates) stored
The length of each array can be different

I want to extract the subset of coordinate combinations which make up a complete
retangle of size N. In other words; all the cartesian coordinates are adjacent to each other.

Example:

findRectangles({
    {*(1,1), (3,5), (6,9)}, 
    {(9,4), *(2,2), (5,5)}, 
    {(5,1)},
    {*(1,2), (3,6)}, 
    {*(2,1), (3,3)}
})

yields the following:

[(1,1),(1,2),(2,1),(2,2)],
..., 
...(other solutions)...

No two points can come from the same set.

I first just calculated the cartesian product, but this quickly becomes infeasible (my use-case at the moment has 18 arrays of points with each array roughly containing 10 different coordinates).

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

青瓷清茶倾城歌 2024-11-14 19:49:12

您可以使用散列来达到很好的效果：

hash each point (keeping track of which list it is in)
for each pair of points (a,b) and (c,d):
    if (a,d) exists in another list, and (c,b) exists in yet another list:
        yield rectangle(...)

当我说存在时，我的意思是做类似的事情：

hashesToPoints = {}
for p in points:
    hashesToPoints.setdefault(hash(p),set()).add(p)
for p1 in points:
    for p2 in points:
        p3,p4 = mixCoordinates(p1,p2)
        if p3 in hashesToPoints[hash(p3)] and {{p3 doesn't share a bin with p1,p2}}:
            if p4 in hashesToPoints[hash(p4)] and {{p4 doesn't share a bin with p1,p2,p3}}:
                yield Rectangle(p1,p2)

这是O(#bins^2 * items_per_bin^2)< /code>~30000，在 18 个数组和 10 个 items_per_bin 的情况下速度非常快——比外部乘积方法要好得多，而外部乘积方法...更糟糕O(items_per_bin^#bins)~3万亿。 =)

小旁注：

您可以通过多次“修剪”来减少计算中的底数和指数。例如，

remove each point that is not corectilinear with another point in the X or Y direction
then maybe remove each point that is not corectilinear with 2 other points, in both X and Y direction

您可以通过根据 X 坐标排序，然后对 Y 坐标重复排序来完成此操作，在 O(P log(P)) 时间内（根据点数）。您也可以在进行哈希处理的同时执行此操作。如果坏人正在安排您的输入，他可以使此优化根本不起作用。但根据您的发行版，您可能会看到显着的加速。

You can use hashing to great effect:

hash each point (keeping track of which list it is in)
for each pair of points (a,b) and (c,d):
    if (a,d) exists in another list, and (c,b) exists in yet another list:
        yield rectangle(...)

When I say exists, I mean do something like:

hashesToPoints = {}
for p in points:
    hashesToPoints.setdefault(hash(p),set()).add(p)
for p1 in points:
    for p2 in points:
        p3,p4 = mixCoordinates(p1,p2)
        if p3 in hashesToPoints[hash(p3)] and {{p3 doesn't share a bin with p1,p2}}:
            if p4 in hashesToPoints[hash(p4)] and {{p4 doesn't share a bin with p1,p2,p3}}:
                yield Rectangle(p1,p2)

This is O(#bins^2 * items_per_bin^2)~30000, which is downright speedy in your case of 18 arrays and 10 items_per_bin -- much better than the outer product approach which is... much worse with O(items_per_bin^#bins)~3trillion. =)

minor sidenote:

You can reduce both the base and exponent in your computation by making multiple passes of "pruning". e.g.

remove each point that is not corectilinear with another point in the X or Y direction
then maybe remove each point that is not corectilinear with 2 other points, in both X and Y direction

You can do this by sorting according to the X-coordinate, repeat for the Y-coordinate, in O(P log(P)) time in terms of number of points. You may be able to do this at the same time as the hashing too. If a bad guy is arranging your input, he can make this optimization not work at all. But depending on your distribution you may see significant speedup.

回复收藏 0 原文

澜川若宁 2024-11-14 19:49:12

让 XY 成为您的数组集。构造两个新集合 X 和 Y，其中 X 等于 XY，所有数组按 x 坐标排序，Y 等于 XY，所有数组按 y 坐标排序。

对于 X 中任何数组中的每个点 (x0,y0)：在 X 的其余数组中找到具有相同 x 坐标和不同 y 坐标的每个点 (x0,y1)
对于每个这样的点对（如果它存在）：在 Y 中搜索点 (x1,y0) 和 (x1,y1)

令 C 为最大数组的大小。然后对所有集合进行排序需要时间 O(N*C*log(C))。在步骤 1 中，找到单个匹配点需要花费 O(N*log(C)) 时间，因为 X 中的所有数组都已排序。找到所有这些点的时间复杂度为 O(C*N)，因为总共最多有 C*N 个点。由于 Y 已排序，因此第 2 步花费的时间为 O(N*log(C))。

因此，总体渐近运行时间为 O(C * N^2 * log(C)^2)。

对于 C==10 和 N==18，您将获得大约 10,000 次操作。将其乘以 2，因为我由于大 O 表示法而放弃了该因子。

该解决方案的另一个好处是实施起来极其简单。您所需要的只是数组、排序和二分搜索，其中前两个很可能已经内置到语言中，并且二分搜索非常简单。

另请注意，这是所有矩形均从同一 x 坐标开始的最坏情况下的运行时。在一般情况下，你可能会做得比这好得多。