Подсчет линий пересечений из списков в python

Question

Я только начинаю изучать python, и мне нужно решить эту проблему, но я застрял. Нам была предоставлена ​​функция (lSegInt), чтобы найти пересечения линий. Что мне нужно сделать, так это правильно форматировать данные, чтобы передать его через эту функцию, также найдите, сколько раз пересекаются две полилинии.

Вот данные:

pt1 = (1,1) 
pt2 = (5,1) 
pt3 = (5,5) 
pt4 = (1,5) 
pt5 = (2,2) 
pt6 = (2,3) 
pt7 = (4,6) 
pt8 = (6,3) 
pt9 = (3,1) 
pt10 = (1,4) 
pt11 = (3,6) 
pt12 = (4,3) 
pt13 = (7,4) 
l5 = [[pt1, pt5, pt6, pt7, pt8, pt9]] 
l6 = [[pt10, pt11, pt12, pt13]] 

Вот мой код:

def split(a): 
     lines = [] 
     for i in range(len(a[0]) - 1): 
     line = [] 
     for j in (i,i+1): 
     line.append(a[0][j]) 
     lines.append(line) 
     return lines 
    sl5 = split(l5) 
    sl6 = split(l6) + split(l6) 

Это где я застрял. Необходимо выяснить, сколько раз пересекаются полилинии. Я хотел использовать цикл zipped для sl5 и sl6, но он не будет проверять каждую строку одного списка по отношению к каждой строке другого, а списки имеют разную длину.

while i < len(sl5): 
    for x, in a,: 
     z = 1 
     fresults.append(lSegInt(x[0],x[1],sl6[0][0],sl6[1][0])) 
     fresults.append(lSegInt(x[0],x[1],sl6[1][0],sl6[1][1])) 
     fresults.append(lSegInt(x[0],x[1],sl6[2][0],sl6[2][1])) 
     i = i + 1 
print fresults 

Функция:

def lSegInt(s1, s2, t1, t2): 
'''Function to check the intersection of two line segments. Returns 
None if no intersection, or a coordinate indicating the intersection. 

An implementation from the NCGIA core curriculum. s1 and s2 are points 
(e.g.: 2-item tuples) marking the beginning and end of segment s. t1 
and t2 are points marking the beginning and end of segment t. Each point 
has an x and y coordinate: (1, 3). 
Variables are named following linear formula: y = a + bx.''' 
if s1[0] != s2[0]:    # if s is not vertical 
    b1 = (s2[1] - s1[1])/float(s2[0] - s1[0]) 
    if t1[0] != t2[0]:    # if t is not vertical 
     b2 = (t2[1] - t1[1])/float(t2[0] - t1[0]) 
     a1 = s1[1] - (b1 * s1[0]) 
     a2 = t1[1] - (b2 * t1[0]) 
     if b1 == b2:    # if lines are parallel (slopes match) 
      return(None) 
     xi = -(a1-a2)/float(b1-b2) # solve for intersection point 
     yi = a1 + (b1 * xi) 
    else: 
     xi = t1[0] 
     a1 = s1[1] - (b1 * s1[0]) 
     yi = a1 + (b1 * xi) 
else: 
    xi = s1[0] 
    if t1[0] != t2[0]:   # if t is not vertical 
     b2 = (t2[1] - t1[1])/float(t2[0] - t1[0]) 
     a2 = t1[1] - (b2 * t1[0]) 
     yi = a2 + (b2 * xi) 
    else: 
     return(None) 
# Here is the actual intersection test! 
if (s1[0]-xi)*(xi-s2[0]) >= 0 and \ 
(s1[1]-yi)*(yi-s2[1]) >= 0 and \ 
(t1[0]-xi)*(xi-t2[0]) >= 0 and \ 
(t1[1]-yi)*(yi-t2[1]) >= 0: 
    return((float(xi), float(yi))) # Return the intersection point. 
else: 
    return(None) 

Любая помощь по этому вопросу очень ценится. Извините за стену текста.

Answer 1

Я понятия не имею, для чего предназначена ваша функция split, но я не думаю, что она вам нужна. Я также не знаю, почему ваши полилинии списки списков, но здесь вы идете:

def count_intersections(polyline1, polyline2): 
    intersections= 0 

    # for each line in polyline1... 
    iter1= iter(polyline1) 
    point1= next(iter1) 
    while True: 
     try: 
      point2= next(iter1) 
     except StopIteration: 
      break 

     #...count the intersections with polyline2 
     iter2= iter(polyline2) 
     point3= next(iter2) 
     while True: 
      try: 
       point4= next(iter2) 
      except StopIteration: 
       break 

      if lSegInt(point1, point2, point3, point4): 
       intersections+= 1 

    return intersections 

print count_intersections(l5[0], l6[0]) 
# this prints "2". I didn't manually confirm if it's correct, but it doesn't look too bad. 

Не так много, чтобы объяснить здесь: Идея заключается в том, чтобы подсчитать, как часто любой линии polyline1 пересекает любой линии в polyline2, поэтому вам просто нужно перебирать обе полилинии и вызывать функцию lSegInt на каждой итерации.