1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – John Douma Jan 1 at 22:34
  • $\begingroup$ 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$. $\endgroup$ – Abderrahim ben Jan 1 at 22:42
  • $\begingroup$ I cannot understand your English but what you are describing sounds like the traveling salesman problem. $\endgroup$ – Misha Lavrov Jan 2 at 1:21
  • $\begingroup$ 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. $\endgroup$ – Abderrahim ben Jan 2 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.