Home > Back-end >  group polylines in R
group polylines in R

Time:11-16

I'm trying to find the best way to group polylines similar to the image below. My issue is that I don't know how to group the lower lines together in a way that the lower lines aren't grouped with the upper lines. This is just a small example so I'd like to stay away from manually identifying the groupings. To reiterate, i'm not concerned with the grouping sizes, i just want to make sure the lower lines and upper lines are not grouped together.

enter image description here

example data:

lines<- structure(list(id = 1:80, geometry = structure(list(structure(c(1320292.69747812, 
1321285.88985455, 261241.476630851, 260831.032628618), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1322727.26279757, 
1323070.86823758, 269202.165722504, 268878.759945711), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1307984.56092642, 
1309351.22772654, 285387.749790353, 280958.616693192), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1309327.72736193, 
1311061.97878009, 284733.733509469, 278925.800381181), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1329629.79278094, 
1331158.57627695, 275657.561020343, 270551.94624691), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1329139.92741162, 
1330565.96111526, 275445.895954009, 270472.591379894), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1322105.85487443, 
1324401.66659021, 262400.977150438, 254785.933319394), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1322808.19710091, 
1325129.73139202, 262588.289760743, 254944.746623024), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1323565.86534896, 
1325834.65786787, 262806.022499948, 255296.015776597), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1324320.329743, 
1326569.5211352, 263027.339985797, 255429.531348851), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1324994.48002948, 
1327258.19759066, 263221.330763837, 255674.865640976), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1325684.0959807, 
1327990.78140831, 263419.334517577, 255771.949743826), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1322520.60047668, 
1324743.07603181, 262505.199177644, 254968.584682057), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1323176.18446536, 
1325459.27635493, 262695.083212582, 255101.644315764), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1323884.31901499, 
1326109.02157104, 262900.757841442, 255415.2338953), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1311757.59240242, 
1313995.14098693, 275977.900173034, 268466.634273695), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1324676.03168787, 
1326892.49451308, 263126.584619448, 255600.85596869), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1325322.26078313, 
1327626.26126181, 263316.295907714, 255646.984684324), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1326048.70964287, 
1328224.82452016, 263402.286842692, 256152.406935272), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1326457.03566363, 
1328632.9763865, 263648.411462916, 256409.46996017), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1327149.49480362, 
1329377.58414048, 263857.435476825, 256390.350553785), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1327817.3941289, 
1330050.07275291, 264051.340122589, 256660.856244889), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1328586.01394194, 
1330904.78321849, 264331.342762194, 256593.355954703), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1329273.15750101, 
1331620.76586668, 264500.2370116, 256733.827430276), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1329507.73490663, 
1332262.93453593, 266326.234130977, 257101.982096502), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1329239.538397, 
1332743.93890305, 269961.083741141, 258238.302343622), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1329935.21716447, 
1333369.26609651, 270159.329043129, 258525.984199953), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1319406.43623962, 
1322231.25154073, 272042.165357295, 262633.249605243), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1320164.57209091, 
1322980.09083108, 272230.721658333, 262828.919535042), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1320876.30584885, 
1323755.74876144, 272542.021977056, 263076.200167043), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1321671.41457859, 
1324529.12626445, 272746.028924429, 263287.036416714), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1322419.69095888, 
1325240.10106502, 272956.256976583, 263503.729828039), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1323142.06771282, 
1325994.37318429, 273209.596759861, 263732.364410279), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1326847.46612727, 
1329069.86608868, 263591.918946778, 256099.199743925), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1327483.74073892, 
1329792.51062114, 263941.649225438, 256221.580545954), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1328195.02569996, 
1330430.76835872, 264143.850158056, 256491.29804469), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1319765.24510116, 
1322606.04955521, 272137.796075428, 262714.706556074), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1320489.09073701, 
1323351.35438769, 272463.930308005, 262928.508659958), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1321278.56880664, 
1324077.22855963, 272642.310968827, 263309.366657034), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1322085.18649593, 
1324850.85290976, 272751.926312415, 263374.574989374), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1322775.9643605, 
1325632.79471899, 273161.093709651, 263618.404924199), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1323583.07214335, 
1326362.67780918, 273248.911135509, 263824.637425455), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1309757.52883843, 
1312698.45538606, 286491.150839504, 276611.009050636), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1310584.51409501, 
1313478.16015204, 286648.313008673, 276668.838794794), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1311294.46802509, 
1314275.64469114, 286890.213527778, 276901.859217186), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1312438.61608674, 
1315239.64475516, 286643.217553606, 277200.603270518), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1312975.46066495, 
1316009.36787239, 287518.377196221, 277422.108733275), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1313644.33335126, 
1316748.23279612, 287923.236445802, 277632.002465895), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1309490.85501514, 
1312318.28276388, 285906.180949639, 276362.043954575), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1310284.36394243, 
1313137.4677097, 286168.161487386, 276599.171640036), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1311095.47880857, 
1313950.50570095, 286339.538537197, 276832.538777845), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1312054.49723571, 
1314816.15444077, 286572.562435151, 277078.051617926), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1312717.01508108, 
1315585.8823936, 286984.537831443, 277299.547114519), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1313563.76491234, 
1316405.11102784, 286956.535800917, 277533.117547202), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1330001.66169503, 
1331441.61857632, 275724.480989415, 270693.269299901), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1329117.30888478, 
1330602.95021805, 275481.78054417, 270488.017772382), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1328955.99870681, 
1331233.86569408, 264350.862512819, 256768.507958292), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1328157.37620357, 
1331897.50796516, 269651.922859418, 257016.999528129), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1312771.47977731, 
1314919.22399641, 276274.064628688, 269161.302213245), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1314397.06693238, 
1316577.63442736, 276762.63467374, 269454.086334993), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1312378.65738438, 
1314537.48112216, 276170.448884872, 268977.820080693), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1313214.18754803, 
1315276.36088868, 276236.825370232, 269468.019549378), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1313572.17044336, 
1315742.06956973, 276503.499425652, 269245.641988892), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1314062.77399764, 
1316027.9645161, 276412.749755266, 269809.24815042), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1315142.50655836, 
1317804.20358522, 276958.077640558, 268218.759998332), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1316001.75930472, 
1318589.01093446, 277210.75744261, 268469.78117331), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1316796.27507705, 
1319344.38997062, 277436.489701821, 268782.042552629), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1314793.07122514, 
1317351.29936363, 276862.706626571, 268288.48358177), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1315562.88757254, 
1318083.27051157, 277080.562201545, 268807.715701547), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1316406.75163206, 
1319010.30723804, 277325.618763129, 268421.194411531), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1307295.08447983, 
1310096.04403608, 285201.000956178, 275699.820129863), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1308314.57551543, 
1310908.87092878, 284827.248632782, 275944.028824226), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1308880.8592541, 
1311703.19280556, 285644.744366046, 276180.554897238), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1307722.28366584, 
1310494.68354048, 285156.066780807, 275821.745264618), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1308616.52872537, 
1311243.19896378, 285092.604971004, 276293.880336344), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1328893.16712357, 
1332718.29560953, 269865.641920638, 257068.91082682), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1329551.85937756, 
1333401.01982575, 270048.454637588, 257299.672908603), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1307315.77730024, 
1310117.64943266, 285248.801689659, 275707.592695735), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1308200.93822492, 
1310843.35996928, 285174.200608979, 276088.176879588), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg")), structure(c(1309023.34200458, 
1311678.47793656, 285123.684043029, 276172.71049477), .Dim = c(2L, 
2L), class = c("XY", "LINESTRING", "sfg"))), n_empty = 0L, crs = structure(list(
    input = "NAD83 / New Mexico East (ftUS)", wkt = "PROJCRS[\"NAD83 / New Mexico East (ftUS)\",\n    BASEGEOGCRS[\"NAD83\",\n        DATUM[\"North American Datum 1983\",\n            ELLIPSOID[\"GRS 1980\",6378137,298.257222101,\n                LENGTHUNIT[\"metre\",1]]],\n        PRIMEM[\"Greenwich\",0,\n            ANGLEUNIT[\"degree\",0.0174532925199433]],\n        ID[\"EPSG\",4269]],\n    CONVERSION[\"SPCS83 New Mexico East zone (US Survey feet)\",\n        METHOD[\"Transverse Mercator\",\n            ID[\"EPSG\",9807]],\n        PARAMETER[\"Latitude of natural origin\",31,\n            ANGLEUNIT[\"degree\",0.0174532925199433],\n            ID[\"EPSG\",8801]],\n        PARAMETER[\"Longitude of natural origin\",-104.333333333333,\n            ANGLEUNIT[\"degree\",0.0174532925199433],\n            ID[\"EPSG\",8802]],\n        PARAMETER[\"Scale factor at natural origin\",0.999909091,\n            SCALEUNIT[\"unity\",1],\n            ID[\"EPSG\",8805]],\n        PARAMETER[\"False easting\",541337.5,\n            LENGTHUNIT[\"US survey foot\",0.304800609601219],\n            ID[\"EPSG\",8806]],\n        PARAMETER[\"False northing\",0,\n            LENGTHUNIT[\"US survey foot\",0.304800609601219],\n            ID[\"EPSG\",8807]]],\n    CS[Cartesian,2],\n        AXIS[\"easting (X)\",east,\n            ORDER[1],\n            LENGTHUNIT[\"US survey foot\",0.304800609601219]],\n        AXIS[\"northing (Y)\",north,\n            ORDER[2],\n            LENGTHUNIT[\"US survey foot\",0.304800609601219]],\n    USAGE[\n        SCOPE[\"Engineering survey, topographic mapping.\"],\n        AREA[\"United States (USA) - New Mexico - counties of Chaves; Colfax; Curry; De Baca; Eddy; Guadalupe; Harding; Lea; Mora; Quay; Roosevelt; San Miguel; Union.\"],\n        BBOX[32,-105.72,37,-102.99]],\n    ID[\"EPSG\",2257]]"), class = "crs"), class = c("sfc_LINESTRING", 
"sfc"), precision = 0, bbox = structure(c(xmin = 1307295.08447983, 
ymin = 254785.933319394, xmax = 1333401.01982575, ymax = 287923.236445802
), class = "bbox"))), row.names = c(NA, -80L), sf_column = "geometry", agr = structure(c(id = NA_integer_), .Label = c("constant", 
"aggregate", "identity"), class = "factor"), class = c("sf", 
"tbl_df", "tbl", "data.frame"))

CodePudding user response:

Just an idea if you want to cluster the lines into an "upper" and a "lower" group:

  1. Compute the center of each lines (maybe with sf::st_centroid())
  2. Extract the coordinates of the centers with sf::st_coordinates()
  3. build a nx2-matrix containing the center coordinates
  4. Apply the k-means algorithm (with e.g., kmeans) specifying that you have only to cluster (check the example in the help of the function kmeans())
  5. The kmeans() function returns the cluster ID of the lines (1 or 2).
  • Related