how to find all non-conflict line segments from a lot of 2D segments?

user_8829913 0
Viewed 44

I met a geometry/algorithm problem.

With help of a function, I can know if 2 segments intersect with each other, like

def intersect(P,Q):
 return True if P,Q intersect

based on this function, I want get something more.

I have around 100 segments, and wondering how can I get the quantity of classes of all non-conflict/intersect combinations (add: if you know a term in traffic management, I want to find something like PHASE)

for example, the following img link: I got 4 segments A, B, C and D.

example: 4 segments

A intersect with B,C C intersect with D

possible non-conflict/intersect combinations could be:

[A D], [B C], the class number is 2

or

[B D], [A], [C], the class number is 3

Is there anyway to get those combination list and the corresponding class number?

Any answer would be much appreciated!

intersection geometry python
1 Answers

If you are interested in getting all non-intersecting pairs of segments you can do something like in the code below.

First of all you need to retrieve all segment coordinates from an external source (text file, json file, etc) and then store these coordinates into a data structure (e.g. a dictionary, but it could be another data structure). For the sake of simplicity, I am just hardcoding the coordinates in the script.

Then, I get all possible pairs of segment without repetitions, so ["line_a", "line_b"] is the same as ["line_b", "line_a"].

Then, check if the two segments intersect, using for instance the shapely library, or your custom function and, if they don't, add the pair to the non_intersecting_segment_pairs list.

import itertools
from pprint import pprint

import matplotlib.pyplot as plt
from shapely.geometry import LineString

# Get segment coordinates from, for instance, json file and stored them into a data structure.

label_to_segment = {
    "segment_a": LineString([(0, 0), (0, 1)]),
    "segment_b": LineString([(0, -1), (1, 0)]),
    "segment_c": LineString([(-2, 3), (1, -8)]),
    "segment_d": LineString([(-1, 0), (-4, 3)]),
}

for label, segment in label_to_segment.items():
    plt.plot(*segment.xy, label=label)
plt.legend()
plt.show()

segment_pairs = list(itertools.combinations(label_to_segment.keys(), 2))

non_intersecting_segment_pairs = []
for pairs in segment_pairs:
    segment_i = label_to_segment[pairs[0]]
    segment_j = label_to_segment[pairs[1]]
    if segment_i.intersection(segment_j).wkt == "LINESTRING EMPTY":
        non_intersecting_segment_pairs.append(pairs)
        
pprint(non_intersecting_segment_pairs)

>>> pprint(non_intersecting_segment_pairs)
[('segment_a', 'segment_b'),
 ('segment_a', 'segment_c'),
 ('segment_a', 'segment_d'),
 ('segment_b', 'segment_c'),
 ('segment_b', 'segment_d')]

enter image description here

user_149528560
Related