Search code examples
python-3.xcomputational-geometry

How to check when a vector has made one turns in python

I am actually working on data that represents a (roughly) noisy circle in a 2d space. i acquire data one point at a time and the goal is know when the points have made a circle.

To do so, i considered each successive points as only one vector that has turned a bit. And to know when one turn has been made (meaning when the circle is formed), I check when both x and y coordinate has change there sign twice (meaning the vector has made 2*0.5 turn = 1 turn). then i wait one more half turn to compensate the starting error. Indeed, depending on where it has started in the quarter of the space it was at first, it may have not do a whole turn.

I don't need to be extremely precise. So this is kind of fine for me, but i wonder if there is another method thas is more efficient and that tells the real number of turns. This could speed up a bit the process as the points arrives quit slowly (avoiding me to wait one more useless half turn)

One important point is that i can only use Numpy.

EDIT : more precision, the distance between each point is NOT regular. At first, the circle starts to be formed slowly and it then speed up. So, at the beginning the points are more dense than at the end. Another thing is that the (0,0) point may even not be contained in the circle. Finally, i said roughly circular shaped because it tends to be ellipsis shaped, but not badly formed, just noisy.

And sorry but i can't provide data, at least for now. I'll tell you if it is possible during the week.

Solution

  • You can monitor the distance of each point to the first point and when this distance reaches a minimum it means the circle has closed. The following shows a plot of point distances to the first point along the circle:

    Distances

    This is the relevant code for the algorithm:

    distances = []
points = [next_point()]
while True:  # break below
    points.append(next_point())
    distances.append(np.linalg.norm(points[-1] - points[0]))
    if len(distances) >= 3:
        left = distances[-2] - distances[-3]
        right = distances[-1] - distances[-2]
        if left < 0 and right > 0:  # minimum detected
            break
del points[-1], distances[-1]  # optionally delete the last point in order to leave the circle open

    Testing on a data set which varies both the angle difference and the radius the following result is obtained:

    Example

    This is the full example code:

    from math import pi
import random

import matplotlib.pyplot as plt
import numpy as np


def generate():
    angle = pi/4
    angle_upper_lim = 0.002
    while True:
        angle += 2*pi * random.uniform(0.001, angle_upper_lim)
        # radius = random.uniform(0.95, 1.05)
        radius = 1
        yield np.array([3 + radius*np.cos(angle), 5 + radius*np.sin(angle)])
        angle_upper_lim *= 1.03  # make the circle fill faster


generator = generate()


def next_point(n=1):
    """n: number of points per group"""
    return sum(next(generator) for __ in range(n)) / n


distances = []
points = [next_point()]
while True:  # break below
    points.append(next_point())
    distances.append(np.linalg.norm(points[-1] - points[0]))
    if len(distances) >= 3:
        left = distances[-2] - distances[-3]
        right = distances[-1] - distances[-2]
        if left < 0 and right > 0:  # minimum detected
            break
del points[-1], distances[-1]  # optionally delete the last point in order to leave the circle open

fig, (ax1, ax2) = plt.subplots(ncols=2, figsize=(10.8, 4.8))
plt.subplots_adjust(wspace=0.11)
ax1.set_title('Data points')
ax1.scatter(*np.stack(points, axis=1), s=5, c=np.arange(len(points)))
ax1.plot(*points[ 0], 's', ms=8, label='First point', color='#2ca02c')
ax1.plot(*points[-1], '*', ms=12, label='Last point', color='#ff7f0e')
ax1.legend(loc='center')

ax2.set(title='Distance of circle points to first point', xlabel='Point #', ylabel='Distance')
ax2.yaxis.tick_right()
ax2.yaxis.set_label_position('right')
ax2.plot(distances, '-o', ms=4)
ax2.plot(len(distances)-1, distances[-1], '*', ms=10, label='circle closed')
ax2.legend()

plt.show()

    Varying radius

    In case the radius of data points varies as well it is important to choose a window of sufficient size which will group and average consecutive data points for greater stability. The function next_point can be adjusted by using n=5 for example. The following result is obtained by uncommenting the radius variation in the above code and using a window size of n=5:

    Example varying radius