确定点是否在旋转矩形内（仅限标准 Python 2.7 库）

Question

我有一个以这些坐标为顶点的旋转矩形：

   1   670273   4879507
   2   677241   4859302
   3   670388   4856938
   4   663420   4877144

---

---

我有这些坐标的点：

670831  4867989
675097  4869543

仅使用 Python 2.7 标准库，我想确定这些点是否落在旋转的矩形内。

• 我无法将其他 Python 库添加到我的 Jython 实现中

---

要做到这一点需要什么？

Answer 1

形式的直线方程ax+by+c==0可以由 2 个点构造。对于凸形状内的给定点，我们需要测试它是否位于形状边缘定义的每条线的同一侧。

在纯 Python 代码中，注意编写方程以避免除法，这可能如下：

def is_on_right_side(x, y, xy0, xy1):
    x0, y0 = xy0
    x1, y1 = xy1
    a = float(y1 - y0)
    b = float(x0 - x1)
    c = - a*x0 - b*y0
    return a*x + b*y + c >= 0

def test_point(x, y, vertices):
    num_vert = len(vertices)
    is_right = [is_on_right_side(x, y, vertices[i], vertices[(i + 1) % num_vert]) for i in range(num_vert)]
    all_left = not any(is_right)
    all_right = all(is_right)
    return all_left or all_right

vertices = [(670273, 4879507), (677241, 4859302), (670388, 4856938), (663420, 4877144)]

下图直观地测试了代码的几种形状。请注意，对于具有水平线和垂直线的形状，通常的线方程可能会导致被零除。

import matplotlib.pyplot as plt
import numpy as np

vertices1 = [(670273, 4879507), (677241, 4859302), (670388, 4856938), (663420, 4877144)]
vertices2 = [(680000, 4872000), (680000, 4879000), (690000, 4879000), (690000, 4872000)]
vertices3 = [(655000, 4857000), (655000, 4875000), (665000, 4857000)]
k = np.arange(6)
r = 8000
vertices4 = np.vstack([690000 + r * np.cos(k * 2 * np.pi / 6), 4863000 + r * np.sin(k * 2 * np.pi / 6)]).T
all_shapes = [vertices1, vertices2, vertices3, vertices4]

for vertices in all_shapes:
    plt.plot([x for x, y in vertices] + [vertices[0][0]], [y for x, y in vertices] + [vertices[0][1]], 'g-', lw=3)
for x, y in zip(np.random.randint(650000, 700000, 1000), np.random.randint(4855000, 4880000, 1000)):
    color = 'turquoise'
    for vertices in all_shapes:
        if test_point(x, y, vertices):
            color = 'tomato'
    plt.plot(x, y, '.', color=color)
plt.gca().set_aspect('equal')
plt.show()

PS：如果您运行的是 32 位版本的 numpy，对于这种大小的整数，可能需要将值转换为浮点数以避免溢出。

如果需要经常进行此计算，则a,b,c可以预先计算并存储这些值。如果边缘的方向已知，则仅需要all_left或之一。all_right

当形状固定后，可以生成该函数的文本版本：

def generate_test_function(vertices, is_clockwise=True, function_name='test_function'):
    ext_vert = list(vertices) + [vertices[0]]
    unequality_sign = '>=' if is_clockwise else '<='
    print(f'def {function_name}(x, y):')
    parts = []
    for (x0, y0), (x1, y1) in zip(ext_vert[:-1], ext_vert[1:]):
        a = float(y1 - y0)
        b = float(x0 - x1)
        c = a * x0 + b * y0
        parts.append(f'({a}*x + {b}*y {unequality_sign} {c})')
    print('    return', ' and '.join(parts))

vertices = [(670273, 4879507), (677241, 4859302), (670388, 4856938), (663420, 4877144)]
generate_test_function(vertices)

这将生成一个函数：

def test_function(x, y):
    return (-20205.0*x + -6968.0*y >= -47543270741.0) and (-2364.0*x + 6853.0*y >= 31699798882.0) and (20206.0*x + 6968.0*y >= 47389003912.0) and (2363.0*x + -6853.0*y >= -31855406372.0)

然后，Jython 编译器可以复制粘贴并优化该函数。请注意，形状不必是矩形。任何凸形都可以，允许使用更紧密的盒子。