algorithm - 判断一组点是否互为镜像

Question

我想知道解决这个问题的最佳算法是什么？给定一组点，判断它们是否沿着平行于 y 轴的直线形成镜像。例如。给定 (1,3) (3,3) (5,3) (7,3) (0,7) (8,7) (-1,4) (9,4)，它们沿着 x = 4

线形成镜像

(1,3) | (7,3)
(3,3) | (5,3)
(0,7) | (8,7)
(-1,4)| (9,4)

我认为最好的方法是将点放在一个 HashMap 中，键作为 y 坐标，值作为 x 坐标。遍历键集并确保每个键具有偶数个值并取它们的平均值。所有的平均值应该相同？

Answer 1

我会这样做:

1. 找到最左边的点。
2. 找到最右边的点。
3. 假设这些点形成镜像。反射轴必须正好在最左边和最右边的点之间。
4. 遍历这些点。在可能的反射轴上反射每一个。如果任何反射点不在点集合中，则该集合不会与自身形成镜像。如果所有反射点都在点集合中，则该集合确实形成镜像。

示例 Python 实现:

def is_reflected(points):
    points = set(points) #sets have more efficient membership testing than lists
    left = min(p[0] for p in points)
    right = max(p[0] for p in points)

    possible_axis = (left + right) / 2.0

    for p in points:
        reflected_x = possible_axis - (p[0] - possible_axis) 
        reflection = (reflected_x, p[1])
        if reflection not in points:
            return False
    return True

points = [(1,3), (3,3), (5,3), (7,3), (0,7), (8,7), (-1,4), (9,4)]
print is_reflected(points)