检查点是否在椭圆内比 contains_point 方法更快

Question

我使用 matplotlib 1.15.1 并尝试生成这样的散点图：

椭圆的大小是固定的，用中心坐标、宽度、高度和角度（由外部提供）绘制：我不知道它们的方程是什么。

g_ell_center = (0.8882, 0.8882)
g_ell_width = 0.36401857095483
g_ell_height = 0.16928136341606
g_ellipse = patches.Ellipse(g_ell_center, g_ell_width, g_ell_height, angle=angle, fill=False, edgecolor='green', linewidth=2)

这个省略号应该在我的图上标记正常和半正常数据。然后，我有一个 ~500 点的数组，必须根据它们所属的椭圆进行着色。所以我尝试用 contains_point 方法检查每个点：

colors_array = []
colors_scheme = ['green', 'yellow', 'black']
for point in points_array:
    if g_ellipse.contains_point(point, radius=0):
        colors_array.append(0)
    elif y_ellipse.contains_point(point, radius=0):
        colors_array.append(1)
    else:
        colors_array.append(2)

最后画点：

plt.scatter(x_array, y_array, s=10, c=[colors_scheme[x] for x in colors_array], edgecolor="k", linewidths=0.3)

但是contains_point非常慢！它为 300 点散点图工作了 5 分钟，我必须并行生成数千个散点图。也许有更快的方法？ P.S。整个项目绑定到matplotlib，我不能使用其他库。

Answer 1

这种方法应该在给定椭圆的中心、宽度、高度和角度的情况下测试一个点是否在椭圆内。您找到该点相对于椭圆中心的 x 和 y 坐标，然后使用角度将其转换为沿长轴和短轴的坐标。最后，您找到该点与像元中心的归一化距离，其中椭圆上的距离为 1，小于 1 为内部，大于 1 为外部。

import matplotlib.pyplot as plt
import matplotlib.patches as patches
import numpy as np

fig,ax = plt.subplots(1)
ax.set_aspect('equal')

# Some test points
x = np.random.rand(500)*0.5+0.7
y = np.random.rand(500)*0.5+0.7

# The ellipse
g_ell_center = (0.8882, 0.8882)
g_ell_width = 0.36401857095483
g_ell_height = 0.16928136341606
angle = 30.

g_ellipse = patches.Ellipse(g_ell_center, g_ell_width, g_ell_height, angle=angle, fill=False, edgecolor='green', linewidth=2)
ax.add_patch(g_ellipse)

cos_angle = np.cos(np.radians(180.-angle))
sin_angle = np.sin(np.radians(180.-angle))

xc = x - g_ell_center[0]
yc = y - g_ell_center[1]

xct = xc * cos_angle - yc * sin_angle
yct = xc * sin_angle + yc * cos_angle 

rad_cc = (xct**2/(g_ell_width/2.)**2) + (yct**2/(g_ell_height/2.)**2)

# Set the colors. Black if outside the ellipse, green if inside
colors_array = np.array(['black'] * len(rad_cc))
colors_array[np.where(rad_cc <= 1.)[0]] = 'green'

ax.scatter(x,y,c=colors_array,linewidths=0.3)

plt.show()

请注意，整个脚本需要 0.6 秒才能运行并处理 500 个点。这包括创建和保存图形等。

使用上面的np.where方法设置colors_array的过程需要0.00007s 500点。

请注意，在下面显示的旧实现中，在循环中设置 colors_array 花费了 0.00016 秒：

colors_array = []

for r in rad_cc:
    if r <= 1.:
        # point in ellipse
        colors_array.append('green')
    else:
        # point not in ellipse
        colors_array.append('black')

Answer 2

您当前的实施应该只调用 contains_point 25,000 到 50,000 次，这不是很多。所以，我猜测 contains_point 的实施是针对精度而不是速度。

由于您的点分布中只有一小部分会出现在任何给定的椭圆中，因此大多数点很少会靠近任何给定的椭圆，因此您可以轻松地使用直角坐标作为快捷方式来找出该点是否足够接近椭圆值得调用 contains_point.

计算椭圆的左右x坐标和上下y坐标，可能用一点填充来解释渲染差异，然后检查该点是否在其中，例如以下伪代码:

if point.x >= ellipse_left and point.x <= ellipse_right and _
   point.y >= ellipse_top and point.y <= ellipse_bottom:
    if ellipse.contains_point(point, radius=0):
        ... use the contained point here

这种方法消除了大多数点的昂贵计算，允许简单比较而不是排除明显的不匹配，同时保持计算的准确性，因为点足够接近以至于它可能在椭圆中。如果例如只有 1% 的点位于给定椭圆附近，这种方法将消除 99% 的 contains_point 调用，取而代之的是更快的比较。

检查点是否在椭圆内比 contains_point 方法更快

Check if points are inside ellipse faster than contains_point method

python

python-3.x

matplotlib

ellipse