Нарисуйте непрерывную линию из неупорядоченных точек

Question

У меня есть наборы широт / длинных координат, которые состоят из нескольких полилиний. Каждый набор координат представляет собой непрерывную линию. Например,

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

Я хочу объединить наборы вместе в непрерывную линию, но, как показано выше, координаты необязательно находятся в одном и том же порядке, чтобы образовать непрерывную линию (у них обоих одинаковая начальная координата, поэтому одна линия будет должен быть обратным).

Конечная точка в одном наборе всегда должна быть равна начальной точке в другом наборе.

Каков наиболее эффективный метод обхода точек (или линий), определения линий, которые необходимо повернуть, и последующего их правильного обращения?

Answer 1

Поскольку ваши две полилинии являются полилиниями (точки упорядочены), нужно просто найти, что нужно повернуть вспять и куда добавить. Поскольку точка соединения одинакова в обеих полилиниях, ее легко:

1. Определения

   позвольте назвать полилинии p[n] и q[m], где n,m - количество точек. и позволяет новой полилинии называется r[N] N=m+n-1

2. точка соединения

   просто определите, какой из 4 сценариев верен:

   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. сценарий объединения 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. сценарий объединения 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. сценарий объединения 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. сценарий объединения 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[]
   

Остерегайтесь, что p[i] - это целая точка (т.е. long, lat), поэтому, если ваш массив 1D, вам нужно изменить индексы и диапазоны соответственно. Надеюсь, я не совершил глупую ошибку с индексами, но вы должны понять, как это сделать, даже если я ...

Грубо, если ваши точки с плавающей точкой, безопаснее сравнивать с некоторой погрешностью, поэтому вместо

p[i] == q[j]

вы должны сделать что-то вроде:

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

где порог - это небольшое значение, например 1e-10 ...