Algoritmo para agrupar puntos por segmentos de recta mediante listas Python

Si Uds buscan en Processing de QGIS se darán cuenta que no encontrarán una aplicación para dividir rectas mediante puntos. La aplicación que aparece es la de dividir rectas con rectas, que funciona como se desea, pero hay que generar manualmente las rectas que cortan (o dividen) a la recta en los puntos deseados.

Tratando de indagar el porqué de esta carencia me di cuenta que el algoritmo para dividir mediante puntos no era tan sencillo como esperaba. En principio, se trata de posicionar estos puntos sobre la recta en las zonas de corte y mientras mayor sea el número de partes en las cuales se desee dividir mayor será la cantidad de éstos a posicionar.

Obviamente, hay que considerar e incluir los vértices de la recta que se agrupan por pares conformando segmentos. Dependiendo del número de partes a dividir, en los segmentos habrá diferente cantidad de puntos dependiendo de la longitud del mismo. Estos segmentos tienen un identificador que depende de la forma como se ha digitalizado la recta. Asumiendo que la digitalización es en sentido antihorario, los puntos se van a colocar según las distancias determinadas con el método interpolate del módulo python shapely. Para averiguar en que segmento se han posicionado se va a usar el azimuth correspondiente lo que va a permitir identificar el id del segmento de recta.

Dependiendo del número de partes a dividir, existirán segmentos sin puntos y algunos muy poblados. No obstante, el número de puntos rara vez coincidirá con el número de segmentos. A efecto de identificación y ubicación, cada punto se genera con el id del segmento al que pertenece. Sin embargo, para facilitar la insersión correcta del punto en el segmento correspondiente hay que crear una lista de puntos con un id común.

En el código a continuación, se coloca al inicio la lista que contiene 35 puntos, con sus respectivos identificadores, obtenidos para una división en 36 partes iguales de una recta. Se denomina idxs. El algoritmo se encargará de agruparlos como corresponde. Para ello se requiere determinar la lista de ids no repetidos y la suma de puntos para cada uno de ellos. El producto final será una nueva lista denominada new_idxs y que contiene los puntos agrupados por ids.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

idxs = [[0, (399627.98380842514, 4447690.000532368)], [0, (399726.129224838, 4447711.191020003)], [0, (399824.2746412509, 4447732.381507638)], [0, (399922.42005766375, 4447753.571995272)], [1, (400019.6016838289, 4447754.85689403)], [1, (400115.2408041235, 4447724.283732625)], [1, (400210.8799244181, 4447693.710571219)], [2, (400305.927880995, 4447670.787606682)], [2, (400395.7346047034, 4447715.690968536)], [2, (400485.5413284117, 4447760.59433039)], [2, (400575.3480521201, 4447805.497692244)], [2, (400665.15477582853, 4447850.401054098)], [3, (400755.8784949291, 4447814.827621558)], [3, (400846.6850742136, 4447771.982263727)], [3, (400937.4916534981, 4447729.136905896)], [3, (401028.2982327825, 4447686.291548064)], [4, (401109.8466944636, 4447735.311155579)], [4, (401190.27820913127, 4447795.413825881)], [4, (401270.709723799, 4447855.5164961815)], [5, (401370.72465425404, 4447856.696073572)], [5, (401471.1316237783, 4447856.696073572)], [5, (401571.5385933026, 4447856.696073572)], [6, (401649.87548048154, 4447908.904739781)], [7, (401732.516067399, 4447933.967661815)], [7, (401829.2191216142, 4447906.947690784)], [8, (401920.8696502545, 4447928.629810404)], [8, (402009.96669797687, 4447974.9253352005)], [8, (402099.0637456992, 4448021.220859998)], [9, (402196.2592031545, 4448032.611411393)], [9, (402296.63903199177, 4448030.276996769)], [9, (402397.0188608291, 4448027.942582144)], [9, (402497.3986896664, 4448025.608167521)], [9, (402597.77851850376, 4448023.273752896)], [9, (402698.1583473411, 4448020.939338272)], [9, (402798.5381761784, 4448018.604923648)]] values = [] for item in idxs: if item[0] not in values: values.append(item[0]) new_idxs = [ [] for i in range(len(values)) ] list = [ 1 for i in range(len(values)) ] for i, item in enumerate(idxs): try: if idxs[i][0]== idxs[i+1][0]: list[idxs[i][0]] += 1 except IndexError: pass k = 0 for i, item in enumerate(list): new_idxs[i].append(idxs[k][0]) for j in range(item): new_idxs[i].append(idxs[k][1]) k +=1 print new_idxs print values print list

Después de ejecutado el código anterior se obtiene la lista de puntos agrupados por segmento; denominada new_idxs. Al final, con fines de corroboración, se imprime la lista de valores no repetidos; indicando que la recta tiene por lo menos 10 segmentos. Se observa, además (última lista), que existen 4 puntos en el primer segmento, 3 en el segundo y así sucesivamente.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

[[0, (399627.98380842514, 4447690.000532368), (399726.129224838, 4447711.191020003), (399824.2746412509, 4447732.381507638), (399922.42005766375, 4447753.571995272)], [1, (400019.6016838289, 4447754.85689403), (400115.2408041235, 4447724.283732625), (400210.8799244181, 4447693.710571219)], [2, (400305.927880995, 4447670.787606682), (400395.7346047034, 4447715.690968536), (400485.5413284117, 4447760.59433039), (400575.3480521201, 4447805.497692244), (400665.15477582853, 4447850.401054098)], [3, (400755.8784949291, 4447814.827621558), (400846.6850742136, 4447771.982263727), (400937.4916534981, 4447729.136905896), (401028.2982327825, 4447686.291548064)], [4, (401109.8466944636, 4447735.311155579), (401190.27820913127, 4447795.413825881), (401270.709723799, 4447855.5164961815)], [5, (401370.72465425404, 4447856.696073572), (401471.1316237783, 4447856.696073572), (401571.5385933026, 4447856.696073572)], [6, (401649.87548048154, 4447908.904739781)], [7, (401732.516067399, 4447933.967661815), (401829.2191216142, 4447906.947690784)], [8, (401920.8696502545, 4447928.629810404), (402009.96669797687, 4447974.9253352005), (402099.0637456992, 4448021.220859998)], [9, (402196.2592031545, 4448032.611411393), (402296.63903199177, 4448030.276996769), (402397.0188608291, 4448027.942582144), (402497.3986896664, 4448025.608167521), (402597.77851850376, 4448023.273752896), (402698.1583473411, 4448020.939338272), (402798.5381761784, 4448018.604923648)]] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [4, 3, 5, 4, 3, 3, 1, 2, 3, 7]