在平面上找出四个点是否构成一个矩形？

Question

在平面上找出四个点是否构成一个矩形？

calgorithmgeometry

62

请有人以C风格伪代码展示如何编写一个函数（无论您喜欢哪种表示点的方式），该函数返回true，如果4个点（作为函数参数）形成一个矩形，否则返回false？

我想出了一种解决方案，首先尝试找到两个具有相等x值的不同点对，然后对y轴做同样处理。但是代码相当冗长。只是好奇看看别人会想出什么。

- pete

2

你想出了解决方案吗？在哪里呢？你可以在这里展示它，我们可以帮助你让它更加简洁和清晰。 - Milan Babuškov

4

有趣的问题。我注意到您的解决方案只会在矩形与坐标轴平行时起作用。 - Christian Madsen

Gman - 无论顺序如何都可以。 Milan - 这是在面试中问我的，所以我没有我的代码（我不一定需要看到代码...一个算法也很好！）。 Christian - 很好的观点，关于它必须与轴平行。 - pete

11个回答

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

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

- Pedro Lopes · Answer 1

这是我的算法提议，用于Python中的轴对齐矩形测试。

思路是以第一个点作为枢轴，并且所有其他点必须符合相同的宽度和高度，并通过集合检查所有点是否不同，以解决如（1, 2），（1, 2），（10, 30），（10, 30）等情况。

from collections import namedtuple

Point = namedtuple('Point', ('x', 'y'))

def is_rectangle(p1, p2, p3, p4) -> bool:
    width = None
    height = None

    # All must be distinct
    if (len(set((p1, p2, p3, p4))) < 4):
        return False

    pivot = p1

    for point in (p2, p3, p4):
        candidate_width = point.x - pivot.x
        candidate_height = point.y - pivot.y

        if (candidate_width != 0):
            if (width is None):
                width = candidate_width
            elif (width != candidate_width):
                return False

        if (candidate_height != 0):
            if (height is None):
                height = candidate_height
            elif (height != candidate_height):
                return False

    return width is not None and height is not None

# Some Examples
print(is_rectangle(Point(10, 50), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(100, 50), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(10, 10), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(10, 30), Point(20, 30), Point(10, 30), Point(20, 30)))
print(is_rectangle(Point(10, 30), Point(10, 30), Point(10, 30), Point(10, 30)))
print(is_rectangle(Point(1, 2), Point(10, 30), Point(1, 2), Point(10, 30)))
print(is_rectangle(Point(10, 50), Point(80, 50), Point(10, 40), Point(80, 40)))