# How to find approximate neighbors ordered sequences in a long sequence of 2d coordinates

Say, We define B a neighbor of A, then Euclidean distance of (B, A) is inferior to a threshold. The order between sequences is irrelevant, but this should define an order within a sequence (preferably). Order within a sequence, is not an order of distances, but the one forming the shortest path traversing the whole sequence.

The case such path doesn't exist, a weak order need to be set, like:

A -> B -> C,D,E -> F -> G

Of course for two sequences (communities), there is no pair of points of distance =< the threshold

I constructed a Cartesian product of all pairs and applied euclidean distance, points of distances less than threshold, are a two neighbors communities, still this is a specific case and I obviously want to let communities grow as far as the threshold let.

If you don't mind, this is heavy math for me, a piece of code attaining the specific case is like:

combinations =list(zip(res.min_lon, res.min_lat))[0:100]
import itertools
def euc(coord1, coord2):
dist = sqrt((coord1[0]-coord2[0])**2 + (coord1[1]-coord2[1])**2)
return dist

distances = []
for pair in itertools.product(combinations, repeat=2):
distances.append(euc(*pair), pair)


Obviously, it doesn't do much. How to formalize this ? probably this is very basic problem in graph theory.

• You define $B$ to be a neighbor of $A$ and then say "The order between sequences is irrelevant, but this should define an order within a sequence (preferably). Order within a sequence, is not an order of distances, but the one forming the shortest path traversing the whole sequence." Do you think this is clear? – John Douma Jan 1 at 22:34
• I will try to re-express this, let $B$ a neighbor of $A$, then they belong to the same sequence $S1$, $C$ is a neighbor of $D$, belonging to $S2$. order(B,A) and order(C,D) need to be known, even weakly (B<A and A<B is impossible, but not(B>=A or A>=B) is possible, defining A ~ B) I hope this is more clear. While there is no order between $S1$ and $S2$. – Abderrahim ben Jan 1 at 22:42
• I cannot understand your English but what you are describing sounds like the traveling salesman problem. – Misha Lavrov Jan 2 at 1:21
• I do my best to formalize in English, @MishaLavrov the traveling salesman problem seem to be the right starter for searching for a solution. A little context is worth it: I want to classify rooftop images by orientation, using Deep learning, I have images themselves for train data, if ordered, this adds more learning value, I can use RNN because sequences are generally of little variations of orientations and something can be learned in addition to images themselves. Thank you for the link. I will invest some time, and come back with results. – Abderrahim ben Jan 2 at 10:26