CODEWITHSUNDEEP
c#arraysalgorithmsortinggis
kittyhawk
kittyhawk

Reputation: 698

Draw continous line from unordered points

I have sets of lat/long coordinates that comprise of several polylines. Each set of coordinates is a continuous line. For example,

Set 1 = 29.61357,-95.64925 29.61204,-95.65259,-95.65886 29.60898,-95.66032 29.60838,-95.66032
Set 2 = 29.61991,-95.63519 29.61957,-95.63648 29.61918,-95.63766 29.61795,-95.64047 29.61644,-95.6436 29.61465,-95.64699 29.61357,-95.64925

I want to merge the sets together to form a continuous line but, as represented by the coordinates above, the coordinates are not necessarily in the same order to make a continuous line (they both have the same start coordinate so one line would have to be reversed).

The end point on one set should always equal the start point on another set.

What is the most efficient method of traversing through the points (or lines), determining which lines need to be reversed, and then reversing them appropriately?

Upvotes: 1

Views: 651

Answers (1)

Spektre
Spektre

Reputation: 51845

As your two polylines are polylines (points are ordered) its just matter of finding what to reverse and where to append. As the join point is exactly the same in both polylines its easy:

  1. definitions

    let call the polylines p[n] and q[m] where n,m are the number of points. and lets new polyline is called r[N] N=m+n-1

  2. joint point

    simply detect which one of the 4 scenarios is true:

    p[  0]==q[  0] // a
p[  0]==q[m-1] // b
p[n-1]==q[m-1] // c
p[n-1]==q[  0] // d

  3. merge scenario a

    r[  i]=p[n-1-i]; i={0,1,2,...n-1} // reverse p[]
r[n+i]=q[i+1];   i={0,1,2,...m-2} // copy q[]

  4. merge scenario b

    r[  i]=q[i];   i={0,1,2,...m-1} // copy q[]
r[m+i]=p[i+1]; i={0,1,2,...n-2} // copy p[]

  5. merge scenario c

    r[  i]=p[i];     i={0,1,2,...n-1} // copy p[]
r[n+i]=q[m-2-i]; i={0,1,2,...m-2} // reverse q[]

  6. merge scenario d

    r[  i]=p[i];     i={0,1,2,...n-1} // copy p[]
r[n+i]=q[i+1];   i={0,1,2,...m-2} // copy q[]

Beware that p[i] is whole point (so both long,lat) so if your array is 1D you need to change the indexes and ranges a bit accordingly. Hope I did not make some silly mistake with the indexes but you should see the point how to do this even if I did...

Of coarse if your points are floating point its safer to compare with some margin of error so instead of

p[i] == q[j]

you should do something like:

|p[i]-q[j]| <= threshold

where threshold is some small value like 1e-10 ...

Upvotes: 2

Related Questions