TechQA.

Python: Remove intersecting line segments from graph until only the shortest of intersecting lines remains (remove dict from list of dicts)

141 views Asked by At

enter image description here

Starting with the graph on the left, I would like to compare all of the lines, and anywhere they intersect (not counting the corners), keep only the shortest of the intersecting lines. I have the data on the lines stored as a list of dictionaries (in descending order of line length), but I can change the data structures however I want.

As as example from the graph above, inside the polygon 0 - 7 - 10 - 4, the line 0 - 10 is the shortest of all the intersecting lines, thus it remains and all others are deleted.


#this is a list of dictionaries of information on line segments
#every line is stored once, there are no duplicates. the lineKey is always "smaller node - bigger node"
#the z coordinates are for distance calculations only, and can be ignored when comparing intersection

aList = [
    {
        "lineKey": "4 - 11",
        "systemDistance": 18530.79947007144,
        "system1Coor": {"x": 5803, "y": 19052, "z": -5},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "10 - 11",
        "systemDistance": 15094.74047474815,
        "system1Coor": {"x": 2695, "y": 16128, "z": -2},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "3 - 11",
        "systemDistance": 15087.677985694154,
        "system1Coor": {"x": 1022, "y": 16198, "z": 0},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "4 - 6",
        "systemDistance": 13941.484497714007,
        "system1Coor": {"x": 5803, "y": 19052, "z": -5},
        "system2Coor": {"x": 4606, "y": 5162, "z": 4},
    },
    {
        "lineKey": "4 - 5",
        "systemDistance": 13795.211959227014,
        "system1Coor": {"x": 5803, "y": 19052, "z": -5},
        "system2Coor": {"x": 6359, "y": 5268, "z": 4},
    },
    {
        "lineKey": "4 - 8",
        "systemDistance": 13656.901881466381,
        "system1Coor": {"x": 5803, "y": 19052, "z": -5},
        "system2Coor": {"x": 4625, "y": 5446, "z": 2},
    },
    {
        "lineKey": "0 - 11",
        "systemDistance": 13624.975009151392,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "1 - 4",
        "systemDistance": 13103.056246540347,
        "system1Coor": {"x": 6660, "y": 5977, "z": -2},
        "system2Coor": {"x": 5803, "y": 19052, "z": -5},
    },
    {
        "lineKey": "2 - 4",
        "systemDistance": 12588.223464810275,
        "system1Coor": {"x": 5878, "y": 6464, "z": -4},
        "system2Coor": {"x": 5803, "y": 19052, "z": -5},
    },
    {
        "lineKey": "3 - 5",
        "systemDistance": 12163.407622866218,
        "system1Coor": {"x": 1022, "y": 16198, "z": 0},
        "system2Coor": {"x": 6359, "y": 5268, "z": 4},
    },
    {
        "lineKey": "1 - 3",
        "systemDistance": 11672.869784247574,
        "system1Coor": {"x": 6660, "y": 5977, "z": -2},
        "system2Coor": {"x": 1022, "y": 16198, "z": 0},
    },
    {
        "lineKey": "3 - 6",
        "systemDistance": 11603.377439349286,
        "system1Coor": {"x": 1022, "y": 16198, "z": 0},
        "system2Coor": {"x": 4606, "y": 5162, "z": 4},
    },
    {
        "lineKey": "5 - 10",
        "systemDistance": 11461.436733673489,
        "system1Coor": {"x": 6359, "y": 5268, "z": 4},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "3 - 8",
        "systemDistance": 11339.625963849072,
        "system1Coor": {"x": 1022, "y": 16198, "z": 0},
        "system2Coor": {"x": 4625, "y": 5446, "z": 2},
    },
    {
        "lineKey": "6 - 10",
        "systemDistance": 11131.267358212182,
        "system1Coor": {"x": 4606, "y": 5162, "z": 4},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "1 - 10",
        "systemDistance": 10897.890896866238,
        "system1Coor": {"x": 6660, "y": 5977, "z": -2},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "2 - 3",
        "systemDistance": 10878.028681705155,
        "system1Coor": {"x": 5878, "y": 6464, "z": -4},
        "system2Coor": {"x": 1022, "y": 16198, "z": 0},
    },
    {
        "lineKey": "8 - 10",
        "systemDistance": 10854.954629108313,
        "system1Coor": {"x": 4625, "y": 5446, "z": 2},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "2 - 10",
        "systemDistance": 10174.693558038984,
        "system1Coor": {"x": 5878, "y": 6464, "z": -4},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "4 - 9",
        "systemDistance": 9463.07983692413,
        "system1Coor": {"x": 5803, "y": 19052, "z": -5},
        "system2Coor": {"x": 4479, "y": 9682, "z": -3},
    },
    {
        "lineKey": "4 - 7",
        "systemDistance": 9334.584511374891,
        "system1Coor": {"x": 5803, "y": 19052, "z": -5},
        "system2Coor": {"x": 4079, "y": 9878, "z": -1},
    },
    {
        "lineKey": "7 - 11",
        "systemDistance": 9238.597783213641,
        "system1Coor": {"x": 4079, "y": 9878, "z": -1},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "9 - 11",
        "systemDistance": 9189.37631180702,
        "system1Coor": {"x": 4479, "y": 9682, "z": -3},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "0 - 6",
        "systemDistance": 8592.218514446662,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 4606, "y": 5162, "z": 4},
    },
    {
        "lineKey": "0 - 8",
        "systemDistance": 8314.787670169335,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 4625, "y": 5446, "z": 2},
    },
    {
        "lineKey": "0 - 5",
        "systemDistance": 8160.395211017662,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 6359, "y": 5268, "z": 4},
    },
    {
        "lineKey": "0 - 1",
        "systemDistance": 7432.292109437034,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 6660, "y": 5977, "z": -2},
    },
    {
        "lineKey": "3 - 9",
        "systemDistance": 7376.253385018712,
        "system1Coor": {"x": 1022, "y": 16198, "z": 0},
        "system2Coor": {"x": 4479, "y": 9682, "z": -3},
    },
    {
        "lineKey": "1 - 11",
        "systemDistance": 7339.821659958776,
        "system1Coor": {"x": 6660, "y": 5977, "z": -2},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "2 - 11",
        "systemDistance": 7132.109014870706,
        "system1Coor": {"x": 5878, "y": 6464, "z": -4},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "0 - 2",
        "systemDistance": 7033.502896850189,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 5878, "y": 6464, "z": -4},
    },
    {
        "lineKey": "3 - 7",
        "systemDistance": 7020.516362775605,
        "system1Coor": {"x": 1022, "y": 16198, "z": 0},
        "system2Coor": {"x": 4079, "y": 9878, "z": -1},
    },
    {
        "lineKey": "9 - 10",
        "systemDistance": 6688.316155804838,
        "system1Coor": {"x": 4479, "y": 9682, "z": -3},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "5 - 11",
        "systemDistance": 6652.693740132639,
        "system1Coor": {"x": 6359, "y": 5268, "z": 4},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "0 - 3",
        "systemDistance": 6647.047690516444,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 1022, "y": 16198, "z": 0},
    },
    {
        "lineKey": "7 - 10",
        "systemDistance": 6401.402736900718,
        "system1Coor": {"x": 4079, "y": 9878, "z": -1},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "0 - 4",
        "systemDistance": 5789.121608672597,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 5803, "y": 19052, "z": -5},
    },
    {
        "lineKey": "3 - 4",
        "systemDistance": 5568.060883287825,
        "system1Coor": {"x": 1022, "y": 16198, "z": 0},
        "system2Coor": {"x": 5803, "y": 19052, "z": -5},
    },
    {
        "lineKey": "8 - 11",
        "systemDistance": 5546.51692506207,
        "system1Coor": {"x": 4625, "y": 5446, "z": 2},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "6 - 11",
        "systemDistance": 5315.179300832663,
        "system1Coor": {"x": 4606, "y": 5162, "z": 4},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "5 - 7",
        "systemDistance": 5143.00738867834,
        "system1Coor": {"x": 6359, "y": 5268, "z": 4},
        "system2Coor": {"x": 4079, "y": 9878, "z": -1},
    },
    {
        "lineKey": "0 - 10",
        "systemDistance": 5140.250772092739,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "5 - 9",
        "systemDistance": 4797.691632441585,
        "system1Coor": {"x": 6359, "y": 5268, "z": 4},
        "system2Coor": {"x": 4479, "y": 9682, "z": -3},
    },
    {
        "lineKey": "6 - 7",
        "systemDistance": 4745.356677848357,
        "system1Coor": {"x": 4606, "y": 5162, "z": 4},
        "system2Coor": {"x": 4079, "y": 9878, "z": -1},
    },
    {
        "lineKey": "1 - 7",
        "systemDistance": 4677.538134531882,
        "system1Coor": {"x": 6660, "y": 5977, "z": -2},
        "system2Coor": {"x": 4079, "y": 9878, "z": -1},
    },
    {
        "lineKey": "0 - 7",
        "systemDistance": 4607.626829507789,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 4079, "y": 9878, "z": -1},
    },
    {
        "lineKey": "6 - 9",
        "systemDistance": 4521.789247631959,
        "system1Coor": {"x": 4606, "y": 5162, "z": 4},
        "system2Coor": {"x": 4479, "y": 9682, "z": -3},
    },
    {
        "lineKey": "0 - 9",
        "systemDistance": 4520.097012233256,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 4479, "y": 9682, "z": -3},
    },
    {
        "lineKey": "7 - 8",
        "systemDistance": 4465.506578205882,
        "system1Coor": {"x": 4079, "y": 9878, "z": -1},
        "system2Coor": {"x": 4625, "y": 5446, "z": 2},
    },
    {
        "lineKey": "1 - 9",
        "systemDistance": 4299.277497440704,
        "system1Coor": {"x": 6660, "y": 5977, "z": -2},
        "system2Coor": {"x": 4479, "y": 9682, "z": -3},
    },
    {
        "lineKey": "4 - 10",
        "systemDistance": 4267.25309771989,
        "system1Coor": {"x": 5803, "y": 19052, "z": -5},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "8 - 9",
        "systemDistance": 4238.518255239677,
        "system1Coor": {"x": 4625, "y": 5446, "z": 2},
        "system2Coor": {"x": 4479, "y": 9682, "z": -3},
    },
    {
        "lineKey": "2 - 7",
        "systemDistance": 3858.9902824443598,
        "system1Coor": {"x": 5878, "y": 6464, "z": -4},
        "system2Coor": {"x": 4079, "y": 9878, "z": -1},
    },
    {
        "lineKey": "2 - 9",
        "systemDistance": 3508.9494154233685,
        "system1Coor": {"x": 5878, "y": 6464, "z": -4},
        "system2Coor": {"x": 4479, "y": 9682, "z": -3},
    },
    {
        "lineKey": "1 - 6",
        "systemDistance": 2209.7911666037585,
        "system1Coor": {"x": 6660, "y": 5977, "z": -2},
        "system2Coor": {"x": 4606, "y": 5162, "z": 4},
    },
    {
        "lineKey": "1 - 8",
        "systemDistance": 2103.140984337474,
        "system1Coor": {"x": 6660, "y": 5977, "z": -2},
        "system2Coor": {"x": 4625, "y": 5446, "z": 2},
    },
    {
        "lineKey": "2 - 6",
        "systemDistance": 1820.2340508846657,
        "system1Coor": {"x": 5878, "y": 6464, "z": -4},
        "system2Coor": {"x": 4606, "y": 5162, "z": 4},
    },
    {
        "lineKey": "5 - 6",
        "systemDistance": 1756.2018676678374,
        "system1Coor": {"x": 6359, "y": 5268, "z": 4},
        "system2Coor": {"x": 4606, "y": 5162, "z": 4},
    },
    {
        "lineKey": "5 - 8",
        "systemDistance": 1743.1133067015467,
        "system1Coor": {"x": 6359, "y": 5268, "z": 4},
        "system2Coor": {"x": 4625, "y": 5446, "z": 2},
    },
    {
        "lineKey": "3 - 10",
        "systemDistance": 1674.4649891831123,
        "system1Coor": {"x": 1022, "y": 16198, "z": 0},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "2 - 8",
        "systemDistance": 1614.4252847375749,
        "system1Coor": {"x": 5878, "y": 6464, "z": -4},
        "system2Coor": {"x": 4625, "y": 5446, "z": 2},
    },
    {
        "lineKey": "2 - 5",
        "systemDistance": 1289.1241212544276,
        "system1Coor": {"x": 5878, "y": 6464, "z": -4},
        "system2Coor": {"x": 6359, "y": 5268, "z": 4},
    },
    {
        "lineKey": "1 - 2",
        "systemDistance": 921.2475237415838,
        "system1Coor": {"x": 6660, "y": 5977, "z": -2},
        "system2Coor": {"x": 5878, "y": 6464, "z": -4},
    },
    {
        "lineKey": "1 - 5",
        "systemDistance": 770.2713807483698,
        "system1Coor": {"x": 6660, "y": 5977, "z": -2},
        "system2Coor": {"x": 6359, "y": 5268, "z": 4},
    },
    {
        "lineKey": "7 - 9",
        "systemDistance": 445.4435991233907,
        "system1Coor": {"x": 4079, "y": 9878, "z": -1},
        "system2Coor": {"x": 4479, "y": 9682, "z": -3},
    },
    {
        "lineKey": "6 - 8",
        "systemDistance": 284.6418802636042,
        "system1Coor": {"x": 4606, "y": 5162, "z": 4},
        "system2Coor": {"x": 4625, "y": 5446, "z": 2},
    },
]


#expected output
[
    {
        "lineKey": "3 - 11",
        "systemDistance": 15087.677985694154,
        "system1Coor": {"x": 1022, "y": 16198, "z": 0},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "7 - 11",
        "systemDistance": 9238.597783213641,
        "system1Coor": {"x": 4079, "y": 9878, "z": -1},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "0 - 1",
        "systemDistance": 7432.292109437034,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 6660, "y": 5977, "z": -2},
    },
    {
        "lineKey": "3 - 7",
        "systemDistance": 7020.516362775605,
        "system1Coor": {"x": 1022, "y": 16198, "z": 0},
        "system2Coor": {"x": 4079, "y": 9878, "z": -1},
    },
    {
        "lineKey": "5 - 11",
        "systemDistance": 6652.693740132639,
        "system1Coor": {"x": 6359, "y": 5268, "z": 4},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "7 - 10",
        "systemDistance": 6401.402736900718,
        "system1Coor": {"x": 4079, "y": 9878, "z": -1},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "0 - 4",
        "systemDistance": 5789.121608672597,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 5803, "y": 19052, "z": -5},
    },
    {
        "lineKey": "3 - 4",
        "systemDistance": 5568.060883287825,
        "system1Coor": {"x": 1022, "y": 16198, "z": 0},
        "system2Coor": {"x": 5803, "y": 19052, "z": -5},
    },
    {
        "lineKey": "6 - 11",
        "systemDistance": 5315.179300832663,
        "system1Coor": {"x": 4606, "y": 5162, "z": 4},
        "system2Coor": {"x": 1165, "y": 1111, "z": -3},
    },
    {
        "lineKey": "0 - 10",
        "systemDistance": 5140.250772092739,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "6 - 7",
        "systemDistance": 4745.356677848357,
        "system1Coor": {"x": 4606, "y": 5162, "z": 4},
        "system2Coor": {"x": 4079, "y": 9878, "z": -1},
    },
    {
        "lineKey": "0 - 7",
        "systemDistance": 4607.626829507789,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 4079, "y": 9878, "z": -1},
    },
    {
        "lineKey": "0 - 9",
        "systemDistance": 4520.097012233256,
        "system1Coor": {"x": 7051, "y": 13399, "z": -1},
        "system2Coor": {"x": 4479, "y": 9682, "z": -3},
    },
    {
        "lineKey": "7 - 8",
        "systemDistance": 4465.506578205882,
        "system1Coor": {"x": 4079, "y": 9878, "z": -1},
        "system2Coor": {"x": 4625, "y": 5446, "z": 2},
    },
    {
        "lineKey": "1 - 9",
        "systemDistance": 4299.277497440704,
        "system1Coor": {"x": 6660, "y": 5977, "z": -2},
        "system2Coor": {"x": 4479, "y": 9682, "z": -3},
    },
    {
        "lineKey": "4 - 10",
        "systemDistance": 4267.25309771989,
        "system1Coor": {"x": 5803, "y": 19052, "z": -5},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "2 - 7",
        "systemDistance": 3858.9902824443598,
        "system1Coor": {"x": 5878, "y": 6464, "z": -4},
        "system2Coor": {"x": 4079, "y": 9878, "z": -1},
    },
    {
        "lineKey": "2 - 9",
        "systemDistance": 3508.9494154233685,
        "system1Coor": {"x": 5878, "y": 6464, "z": -4},
        "system2Coor": {"x": 4479, "y": 9682, "z": -3},
    },
    {
        "lineKey": "5 - 6",
        "systemDistance": 1756.2018676678374,
        "system1Coor": {"x": 6359, "y": 5268, "z": 4},
        "system2Coor": {"x": 4606, "y": 5162, "z": 4},
    },
    {
        "lineKey": "5 - 8",
        "systemDistance": 1743.1133067015467,
        "system1Coor": {"x": 6359, "y": 5268, "z": 4},
        "system2Coor": {"x": 4625, "y": 5446, "z": 2},
    },
    {
        "lineKey": "3 - 10",
        "systemDistance": 1674.4649891831123,
        "system1Coor": {"x": 1022, "y": 16198, "z": 0},
        "system2Coor": {"x": 2695, "y": 16128, "z": -2},
    },
    {
        "lineKey": "2 - 8",
        "systemDistance": 1614.4252847375749,
        "system1Coor": {"x": 5878, "y": 6464, "z": -4},
        "system2Coor": {"x": 4625, "y": 5446, "z": 2},
    },
    {
        "lineKey": "2 - 5",
        "systemDistance": 1289.1241212544276,
        "system1Coor": {"x": 5878, "y": 6464, "z": -4},
        "system2Coor": {"x": 6359, "y": 5268, "z": 4},
    },
    {
        "lineKey": "1 - 2",
        "systemDistance": 921.2475237415838,
        "system1Coor": {"x": 6660, "y": 5977, "z": -2},
        "system2Coor": {"x": 5878, "y": 6464, "z": -4},
    },
    {
        "lineKey": "1 - 5",
        "systemDistance": 770.2713807483698,
        "system1Coor": {"x": 6660, "y": 5977, "z": -2},
        "system2Coor": {"x": 6359, "y": 5268, "z": 4},
    },
    {
        "lineKey": "7 - 9",
        "systemDistance": 445.4435991233907,
        "system1Coor": {"x": 4079, "y": 9878, "z": -1},
        "system2Coor": {"x": 4479, "y": 9682, "z": -3},
    },
    {
        "lineKey": "6 - 8",
        "systemDistance": 284.6418802636042,
        "system1Coor": {"x": 4606, "y": 5162, "z": 4},
        "system2Coor": {"x": 4625, "y": 5446, "z": 2},
    },
]

#this is a function that determines if two of the line segments intersect
def lineIntersection(self, line1, line2):
    x1,y1,z1 = line1['system1Coor'].values()
    x2,y2,z2 = line1['system2Coor'].values()
    x3,y3,z3 = line2['system1Coor'].values()
    x4,y4,z4 = line2['system2Coor'].values()
    denom = (y4-y3)*(x2-x1) - (x4-x3)*(y2-y1)
    if denom == 0: # parallel
        return False
    ua = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / denom
    if (ua < 0 or ua > 1): # out of range
        return False
    ub = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / denom
    if (ub < 0 or ub > 1): # out of range
        return False
    
    return True

#this is a loop to compare all combinations of lines in the list and remove the longest line
#loop through once
for lineKey1 in aList:
    #loop through again
    for lineKey2 in aList:
        
        #check that the loop is not comparing the line to itself
        if lineKey1 != lineKey2:
            
            #check the loop is not comparing two lines that intersect at their corners
            if len(list(set(lineKey1['lineKey'].split(' - ')) & set(lineKey2['lineKey'].split(' - ')))) == 0:
            
                #check if the lines intersect
                if lineIntersection(lineKey1, lineKey2):
                
                    #get the larger of the two lines
                    maxSystemDistance = max(lineKey1['systemDistance'], lineKey2['systemDistance'])
                    
                    #get the value to remove from the list
                    if maxSystemDistance == lineKey1['systemDistance']:
                        lineValueToRemove = lineKey1
                    
                    #get the value to remove from the list
                    elif maxSystemDistance == lineKey2['systemDistance']:
                        lineValueToRemove = lineKey2
                    
                    #check if the value is in the list and remove it
                    if lineValueToRemove in aList:
                        aList.remove(lineValueToRemove)

The loop I have above removes most of the intersecting lines, but not all of them.

python dictionary graph planar-graph
Original Q&A
1

There are 1 answers

0
MT0 On

  1. Sort the lines in order of length.

  2. For each line:

    a. Check if the line intersects with any shorter lines (note: it will never intersect with any adjacent lines).

    b. If it does, remove it.

  3. Repeat #2 for the next longest line.

Note: your intersection algorithm will return that lines intersect if they touch at the end-points; you do not want this and need to change the final test with ua and ub to not match intersections when they equal 0 or 1.

from math import sqrt

class coord:
    def __init__(self,index,x,y,z):
        self.index = index
        self.x = x
        self.y = y
        self.z = z

class line:
    def __init__(self, coord1, coord2):
        self.coord1 = coord1
        self.coord2 = coord2
    
    def length(self):
        dx = self.coord1.x - self.coord2.x
        dy = self.coord1.y - self.coord2.y
        return sqrt(dx*dx + dy*dy)
    
    def intersects(self, line):
        x1, y1 = self.coord1.x, self.coord1.y
        x2, y2 = self.coord2.x, self.coord2.y
        x3, y3 = line.coord1.x, line.coord1.y
        x4, y4 = line.coord2.x, line.coord2.y

        denom = (y4-y3)*(x2-x1) - (x4-x3)*(y2-y1)
        if denom == 0: # parallel
            return False
        ua = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / denom
        ub = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / denom
        return 0 < ua < 1 and 0 < ub < 1
    
    def __str__(self):
        return f"{self.coord1.index} - {self.coord2.index}"
    
    def __repr__(self):
        return self.__str__();

coords = [
    coord( 0,  7051, 13399, -1),
    coord( 1,  6660,  5977, -2),
    coord( 2,  5878,  6464, -4),
    coord( 3,  1022, 16198,  0),
    coord( 4,  5803, 19052, -5),
    coord( 5,  6359,  5268,  4),
    coord( 6,  4606,  5162,  4),
    coord( 7,  4079,  9878, -1),
    coord( 8,  4625,  5446,  2),
    coord( 9,  4479,  9682, -3),
    coord(10,  2695, 16128, -2),
    coord(11,  1165,  1111, -3),
]

lines = [
    line(coords[ 4], coords[11]),
    line(coords[10], coords[11]),
    line(coords[ 3], coords[11]),
    line(coords[ 4], coords[ 6]),
    line(coords[ 4], coords[ 5]),
    line(coords[ 4], coords[ 8]),
    line(coords[ 0], coords[11]),
    line(coords[ 1], coords[ 4]),
    line(coords[ 2], coords[ 4]),
    line(coords[ 3], coords[ 5]),
    line(coords[ 1], coords[ 3]),
    line(coords[ 3], coords[ 6]),
    line(coords[ 5], coords[10]),
    line(coords[ 3], coords[ 8]),
    line(coords[ 6], coords[10]),
    line(coords[ 1], coords[10]),
    line(coords[ 2], coords[ 3]),
    line(coords[ 8], coords[10]),
    line(coords[ 2], coords[10]),
    line(coords[ 4], coords[ 9]),
    line(coords[ 4], coords[ 7]),
    line(coords[ 7], coords[11]),
    line(coords[ 9], coords[11]),
    line(coords[ 0], coords[ 6]),
    line(coords[ 0], coords[ 8]),
    line(coords[ 0], coords[ 5]),
    line(coords[ 0], coords[ 1]),
    line(coords[ 3], coords[ 9]),
    line(coords[ 1], coords[11]),
    line(coords[ 2], coords[11]),
    line(coords[ 0], coords[ 2]),
    line(coords[ 3], coords[ 7]),
    line(coords[ 9], coords[10]),
    line(coords[ 5], coords[11]),
    line(coords[ 0], coords[ 3]),
    line(coords[ 7], coords[10]),
    line(coords[ 0], coords[ 4]),
    line(coords[ 3], coords[ 4]),
    line(coords[ 8], coords[11]),
    line(coords[ 6], coords[11]),
    line(coords[ 5], coords[ 7]),
    line(coords[ 0], coords[10]),
    line(coords[ 5], coords[ 9]),
    line(coords[ 6], coords[ 7]),
    line(coords[ 1], coords[ 7]),
    line(coords[ 0], coords[ 7]),
    line(coords[ 6], coords[ 9]),
    line(coords[ 0], coords[ 9]),
    line(coords[ 7], coords[ 8]),
    line(coords[ 1], coords[ 9]),
    line(coords[ 4], coords[10]),
    line(coords[ 8], coords[ 9]),
    line(coords[ 2], coords[ 7]),
    line(coords[ 2], coords[ 9]),
    line(coords[ 1], coords[ 6]),
    line(coords[ 1], coords[ 8]),
    line(coords[ 2], coords[ 6]),
    line(coords[ 5], coords[ 6]),
    line(coords[ 5], coords[ 8]),
    line(coords[ 3], coords[10]),
    line(coords[ 2], coords[ 8]),
    line(coords[ 2], coords[ 5]),
    line(coords[ 1], coords[ 2]),
    line(coords[ 1], coords[ 5]),
    line(coords[ 7], coords[ 9]),
    line(coords[ 6], coords[ 8]),
]
    
sortedLines = sorted(
    lines,
    key=lambda line: line.length()
)

filteredLines = [
    line
    for index, line
    in enumerate(sortedLines)
    if not any(map(lambda l:line.intersects(l), sortedLines[:index]))
]

print(filteredLines)

Outputs:

[6 - 8, 7 - 9, 1 - 5, 1 - 2, 2 - 5, 2 - 8, 3 - 10, 5 - 8, 5 - 6, 2 - 9, 2 - 7, 4 - 10, 1 - 9, 7 - 8, 0 - 9, 0 - 7, 6 - 7, 0 - 10, 6 - 11, 3 - 4, 0 - 4, 7 - 10, 5 - 11, 3 - 7, 0 - 1, 7 - 11, 3 - 11]

Or, for your input (rather than de-duplicating the information into classes):

def lineIntersection(line1, line2):
    x1,y1,z1 = line1['system1Coor'].values()
    x2,y2,z2 = line1['system2Coor'].values()
    x3,y3,z3 = line2['system1Coor'].values()
    x4,y4,z4 = line2['system2Coor'].values()
    denom = (y4-y3)*(x2-x1) - (x4-x3)*(y2-y1)
    if denom == 0: # parallel
        return False
    ua = ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / denom
    if (ua <= 0 or ua >= 1): # out of range
        return False
    ub = ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / denom
    if (ub <= 0 or ub >= 1): # out of range
        return False
    
    return True

sortedLines = sorted(
    aList,
    key=lambda line: line['systemDistance']
)

filteredLines = [
    line
    for index, line
    in enumerate(sortedLines)
    if not any(map(lambda l:lineIntersection(line, l), sortedLines[:index]))
]

print(filteredLines)

Related Questions in PYTHON

Related Questions in DICTIONARY

Related Questions in GRAPH

Related Questions in PLANAR-GRAPH

Popular Questions

Popular Tags

javascript python java c# php android html jquery c++ css ios sql mysql r reactjs

Trending Questions