Using a csv file of points in a 3D space, this algorithm will determine the linear sections of the point trajectory. It can be assumed the points are move in one direction, no loops (think of car only moving forward).
Ideally, once the linear section is determined, the trajectory is optimized by removing points that are not the beginning or end point.
As of now, I parse the csv file and remove points in the 3D space that are not a minimum distance apart, current threshold is 300. I use the distance formula in a 3D space for this calculation. For a sense of the data, the max distance apart is 377 and the min is 0.1. The number of points before this step is 2400 and after is 1400.
Next, I parse through this new list of data points. Every 10th point (row in code because it is a row of x,y,z coords) I check collinearity. This is done by grabbing the point in the i+5 and i+10 position to minimize the data "noise". In other words, in a practical application of this algorithm, there is a larger chance of error if adjacent points are used.
I have tried two different methods of determining collinearity. The approaches are shown below. I have tested them in theoretical scenarios.
Now the output of both the collinear checks is close to zero if the points are collinear. Therefore, I have created a figure to give a sense of the output so far. I have the actual trajectory of points and it seems to resemble it, but I would like to make it more accurate. In addition, there are some inevitable errors so I would also like to mitigate that.
In essence, how can I optimize my algorithm to reduce error in a practical approach? Assume the trajectory is not known.
Below is the implementation of both collinear checks.
def check_collinear(p1, p2, p3):
'''check if three points are collinear'''
global MAX_DIFF
global MIN_DIFF
# get largest length between the three points
largest_length = max(
get_distance(p1, p2),
get_distance(p1, p3),
get_distance(p2, p3)
)
'''
The largest length will equal, within a range for practical applications, the sum of the lengths
between the other two points. For example, if the length between p1 and p2 is the largest, then
the sum of the lengths from p1 to p2 and from p2 to p3 will equal the length from p1 to p2. Three
cases must be analyzed, this is represented by the three if statements.
'''
if largest_length == get_distance(p1, p2):
# calculates the difference between the largest length and sum of the other two lengths
diff = abs(largest_length - (
get_distance(p2, p3) + get_distance(p1, p3)
))
elif largest_length == get_distance(p1, p3):
diff = abs(largest_length - (
get_distance(p1, p2) + get_distance(p2, p3)
))
elif largest_length == get_distance(p2, p3):
diff = abs(largest_length - (
get_distance(p1, p2) + get_distance(p1, p3)
))
# record minimum and maximum differences
if diff > MAX_DIFF:
MAX_DIFF = diff
elif diff < MIN_DIFF:
MIN_DIFF = diff
# return whether this difference is less than the established threshold
collinear = bool(diff < MIN_DIFF_THRESHOLD)
# record all the differences calculated
DIFFERENCES.append(diff)
return collinear
Here is the second approach which I prefer because the range of "differences" is smaller. In other words, the range of between non-collinear and collinear is smaller. Assume a low difference is collinear, as mentioned previously because it is close to zero.
def check_collinear_Herons(p1, p2, p3):
'''check collinear using Heron's formula'''
global MAX_DIFF
global MIN_DIFF
# calculate sides of a triangle as a, b, and c
a = math.sqrt((p2[0]-p1[0]) ** 2 + (p2[1]-p1[1]) ** 2 + (p2[2]-p1[2]) ** 2)
b = math.sqrt((p3[0]-p1[0]) ** 2 + (p3[1]-p1[1]) ** 2 + (p3[2]-p1[2]) ** 2)
c = math.sqrt((p3[0]-p2[0]) ** 2 + (p3[1]-p2[1]) ** 2 + (p3[2]-p2[2]) ** 2)
p = (a+b+c)/2 # half the perimeter of the triangle
'''
Heron's formula tests that area is zero, for practical purposes the area will never be zero.
Therefore, testing for any of the values in the area calculation to be less than a minimum
threshold, which would yield zero if the area was calculated. The minimum of the differences
between half the perimeter subtracted by one side of the triangle is used to compare to the
minimum difference threshold. Heron's formula for area is as follows:
math.sqrt(p*(p-a)*(p-b)*(p-c))
'''
diff = min(p-a, p-b, p-c)
# return whether this difference is less than the established threshold
collinear = bool(diff < MIN_DIFF_THRESHOLD)
'''
record minimum and maximum differences of the minimum of differences between half the perimeter
subtracted by one side of the triangle
'''
if diff < MIN_DIFF:
MIN_DIFF = diff
if diff > MAX_DIFF:
MAX_DIFF = diff
# record all the differences calculated
DIFFERENCES.append(diff)
return collinear
This is the loop used to go through the processed data.
for i in range(0, len(processed_data)-10):
curr_row = processed_data.iloc[i] # row i
# check collinear if theres three points in front of current point
if i % 10 == 0:
second_row = processed_data.iloc[i+5] # row i + 5
third_row = processed_data.iloc[i+10]
# collinear = check_collinear(curr_row, second_row, third_row)
collinear = check_collinear_Herons(curr_row, second_row, third_row)
# print(collinear)
Here is a graph of the difference values, green is collinear, and red is not. The threshold is the 25th percentile.
plot of collinear confidence
Here is an image of the actual trajectory. It appears to be 2D, but there are 3D coordinates. trajectory
Please let me know if you need any more information or if you have some insight. I hope this is enough detail!