Test whether points are inside ellipses, without using Matplotlib?

Question

I'm working on a Python-based data analysis. I have some x-y data points, and some ellipses, and I want to determine whether points are inside any of the ellipses. The way that I've been doing this works, but it's kludgy. As I think about distributing my software to other people, I find myself wanting a cleaner way.

Right now, I'm using matplotlib.patches.Ellipse objects. Matplotlib Ellipses have a useful method called contains_point(). You can work in data coordinates on a Matplotlib Axes object by calling Axes.transData.transform().

The catch is that I have to create a Figure and an Axes object to hold the Ellipses. And when my program runs, an annoying Matplotlib Figure object will get rendered, showing the Ellipses, which I don't actually need to see. I have tried several methods to suppress this output. I have succeeded in deleting the Ellipses from the Axes, using Axes.clear(), resulting in an empty graph. But I can't get Matplolib's pyplot.close(fig_number) to delete the Figure itself before calling pyplot.show().

Any advice is appreciated, thanks!

Answer 1

Inspired by how a carpenter draws an ellipse using two nails and a piece of string, here is a numpy-friendly implementation to test whether points lie inside given ellipses.

One of the definitions of an ellipse, is that the sum of the distances to the two foci is constant, equal to the width (or height if it would be larger) of the ellipse. The distance between the center and the foci is sqrt(a*a - b*b), where a and b are half of the width and height. Using that distance and rotation by the desired angle finds the locations of the foci. numpy.linalg.norm can be used to calculate the distances using numpy's efficient array operations.

After the calculations, a plot is generated to visually check whether everything went correct.

import numpy as np
from numpy.linalg import norm # calculate the length of a vector

x = np.random.uniform(0, 40, 20000)
y = np.random.uniform(0, 20, 20000)
xy = np.dstack((x, y))
el_cent = np.array([20, 10])
el_width = 28
el_height = 17
el_angle = 20

# distance between the center and the foci
foc_dist = np.sqrt(np.abs(el_height * el_height - el_width * el_width) / 4)
# vector from center to one of the foci
foc_vect = np.array([foc_dist * np.cos(el_angle * np.pi / 180), foc_dist * np.sin(el_angle * np.pi / 180)])
# the two foci
el_foc1 = el_cent + foc_vect
el_foc2 = el_cent - foc_vect

# for each x,y: calculate z as the sum of the distances to the foci;
# np.ravel is needed to change the array of arrays (of 1 element) into a single array
z = np.ravel(norm(xy - el_foc1, axis=-1) + norm(xy - el_foc2, axis=-1) )
# points are exactly on the ellipse when the sum of distances is equal to the width
# z = np.where(z <= max(el_width, el_height), 1, 0)

# now create a plot to check whether everything makes sense
from matplotlib import pyplot as plt
from matplotlib import patches as mpatches

fig, ax = plt.subplots()
# show the foci as red dots
plt.plot(*el_foc1, 'ro')
plt.plot(*el_foc2, 'ro')
# create a filter to separate the points inside the ellipse
filter = z <= max(el_width, el_height)
# draw all the points inside the ellipse with the plasma colormap
ax.scatter(x[filter], y[filter], s=5, c=z[filter], cmap='plasma')
# draw all the points outside with the cool colormap
ax.scatter(x[~filter], y[~filter], s=5, c=z[~filter], cmap='cool')
# add the original ellipse to verify that the boundaries match
ellipse = mpatches.Ellipse(xy=el_cent, width=el_width, height=el_height, angle=el_angle,
                           facecolor='None', edgecolor='black', linewidth=2,
                           transform=ax.transData)
ax.add_patch(ellipse)
ax.set_aspect('equal', 'box')
ax.autoscale(enable=True, axis='both', tight=True)
plt.show()

Answer 2

The simplest solution here is to use shapely.

If you have an array of shape Nx2 containing a set of vertices (xy) then it is trivial to construct the appropriate shapely.geometry.polygon object and check if an arbitrary point or set of points (points) is contained within -

import shapely.geometry as geom
ellipse = geom.Polygon(xy)
for p in points:
    if ellipse.contains(geom.Point(p)):
        # ...

Alternatively, if the ellipses are defined by their parameters (i.e. rotation angle, semimajor and semiminor axis) then the array containing the vertices must be constructed and then the same process applied. I would recommend using the polar form relative to center as this is the most compatible with how shapely constructs the polygons.

import shapely.geometry as geom
from shapely import affinity

n = 360
a = 2
b = 1
angle = 45

theta = np.linspace(0, np.pi*2, n)
r = a * b  / np.sqrt((b * np.cos(theta))**2 + (a * np.sin(theta))**2)
xy = np.stack([r * np.cos(theta), r * np.sin(theta)], 1)

ellipse = affinity.rotate(geom.Polygon(xy), angle, 'center')
for p in points:
    if ellipse.contains(geom.Point(p)):
        # ...

This method is advantageous because it supports any properly defined polygons - not just ellipses, it doesn't rely on matplotlib methods to perform the containment checking, and it produces a very readable code (which is often important when "distributing [one's] software to other people").

Here is a complete example (with added plotting to show it working)

import shapely.geometry as geom
from shapely import affinity
import matplotlib.pyplot as plt
import numpy as np

n = 360
theta = np.linspace(0, np.pi*2, n)

a = 2
b = 1
angle = 45.0

r = a * b  / np.sqrt((b * np.cos(theta))**2 + (a * np.sin(theta))**2)
xy = np.stack([r * np.cos(theta), r * np.sin(theta)], 1)

ellipse = affinity.rotate(geom.Polygon(xy), angle, 'center')
x, y = ellipse.exterior.xy
# Create a Nx2 array of points at grid coordinates throughout
# the ellipse extent
rnd = np.array([[i,j] for i in np.linspace(min(x),max(x),50) 
                      for j in np.linspace(min(y),max(y),50)])
# Filter for points which are contained in the ellipse
res = np.array([p for p in rnd if ellipse.contains(geom.Point(p))])

plt.plot(x, y, lw = 1, color='k')
plt.scatter(rnd[:,0], rnd[:,1], s = 50, color=(0.68, 0.78, 0.91)
plt.scatter(res[:,0], res[:,1], s = 15, color=(0.12, 0.67, 0.71))
plt.show()