python-2.7 - 确定点是否在旋转矩形内(仅限标准 Python 2.7 库)
问题描述
我有一个以这些坐标为顶点的旋转矩形:
1 670273 4879507
2 677241 4859302
3 670388 4856938
4 663420 4877144
我有这些坐标点:
670831 4867989
675097 4869543
仅使用 Python 2.7 标准库,我想确定这些点是否在旋转的矩形内。
- 我无法将其他 Python 库添加到我的 Jython 实现中
这样做需要什么?
解决方案
形式的线方程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 编译器复制粘贴和优化该函数。请注意,形状不需要是矩形。任何凸形都可以,允许使用更紧的盒子。
推荐阅读
- vue.js - 与 Pug 一起使用时 Vue 插件行为异常
- java - 在Java中彼此相邻打印ASCII行?
- python - 我正在尝试使用 python 的 pyodbc 库使用 OpenEdge 10.1B 驱动程序连接到进度数据库,但我收到错误 126 未找到指定模块
- database - 无法从 Hive 的 RDMS 导入表
- git - 使用 GitHub 网站进行 PR 的非快进合并,而不是 Git CLI
- python - 如何使用 Selenium 和 Python 获取更多关键字过滤的元素链接?
- git - 有没有办法比较 2 个未重新建立的 git 分支?
- r - 如何使用 set_name 函数确切知道数据集的正确顺序是什么?
- c# - 如何从字节流中获取 Vector3 数组?
- c++ - 在结构中定义常量