Temporal linking of point identities based on minimal distances

Question

Linked to a previous question where I asked more generally to find optimal unique neighbour pairs based on closest distance, I am now trying to adapt this to the more specific case where I need to link point identities over time.

Question: How can I optimally link point identities over time based on their minimum distance?

From tracking, I acquire the x and y coordinates of a range of objects (my situation ~2-10) over time. As objects move small steps, relative to distance between objects, it should be possible to link the identities of the objects over time with quite high certainty based on closest distance between points at the current and previous timestep.

Data looks like the following:

prevdat = {'id': [0, 1, 2], 'loc': [(300, 200), (425, 400), (400, 300)]}
currlocs = [(435, 390), (405, 295), (440, 330), (290, 215)]`

Some considerations:

1. Multiple points may not be allocated to the same identity
2. If two points are closest to one previous point, their absolute distance should be taken into account
3. Points sometimes have the same distance to closest previous neighbour (but very unlikely to 2nd, 3rd nearest-neighbours etc.)
4. Sometimes the number of current and previous points is not equal
5. A treshold variable provides the maximum nr of identities possible. If that is exceeded, additional points left after allocating to previous identities should be nan

In the example above, the currlocs should be given identities [1,2,3,0] or [1,2,nan,0] in case maxidentities = 3.

This problem would be similar if two datasets were not temporally linked in time, but pts are for example categorised in two different groups where pairs should be created of pts from each group.

Potentially an extension of the above that could improve linking further is to take further measures into account, such as the average vector between a number of previous timesteps of all pt identities and the current point. The data would look like:

from collections import deque
prevdat = {0: {'id': 0, 'loc': deque([(200,300),(210,305),(220,305),(225,310)])}, 
           1: {'id': 1, 'loc': deque([(350,250),(340,255),(335,260),(330,260)])},
           2: {'id': 2, 'loc': deque([(250,250),(240,250),(230,250)])},
           3: {'id': 3, 'loc': deque([(500,50),(480,70),(470,80),(450,85)])}}
currlocs = [(325,265),(430,90),(230,310),(220,255)]

Sounding

Sorry, I now more explicitly state my question – Sounding

Hi @crazjo. Could you please include some example data with multiple steps? – Pipes

Hi Bob, I updated my question yesterday with some example data with multiple steps. Thanks – Sounding

It is good but the cost function is not defined. Given a solution how do you calculate the cost? (I will ask you one thing at a time to avoid confusions). Also don't be surprised if your question is closed closed if one more close vote is received (one more close vote will do that). Probably because it needs more focus, details or clarity. – Pipes

Sorry but I don't follow. I don't know what a cost function is nor why I need one. Points should be linked based on the closest distance such that optimally all points can be linked to a list of previous points with identities. I also saw the votes to close the question but again I don't see how I can provide more focus or clarity. I would like to as I am really stuck and need the help you and others here can provide. Thanks for your understanding! – Sounding

@Pipes let me know if you need further information. Thanks! – Sounding