Подсчет пересекающихся линий

Чтобы воспользоваться уже разработанными функциями оптимизации, нам необходимо представить решение в виде списка чисел. К счастью, для этой задачи найти такое представление совсем просто. У каждого узла есть координаты x и y, поэтому достаточно поместить координаты всех узлов в один длинный список:

sol=[120,200,250,125 … Здесь Чарли (Charlie) помещен в точку с координатами (120, 200), Август (Augustus) – в точку (250, 125) и т. д.

Наша целевая функция должна подсчитать количество пересекающихся отрезков. Вывод формулы, определяющей точку пересечения двух прямолинейных отрезков, выходит за рамки данной статьи, но

основная идея в том, чтобы вычислить, какую часть один отрезок перекрывает на другом. Если эта величина заключена между 0 (один конец отрезка) и 1 (другой конец), то отрезки пересекаются, в противном случае не пересекаются.

Следующая функция перебирает все пары соединительных отрезков и, зная координаты их концов, определяет, пересекаются ли они. Если да, к общей стоимости добавляется 1. Добавьте в файл socialnetwork.py функцию crosscount: def crosscount(v):

#       Преобразовать список чисел в словарь человека: координаты (x,y) loc=dict([(people[i],(v[i*2],v[i*2+1])) for i in range(0,len(people))]) total=0

#       Перебрать все пары отрезков for i in range(len(links)):

for j in range(i+1,len(links)):

# Получить координаты концов (x1,y1),(x2,y2)=loc[links[i][0]],loc[links[i][1]] (x3,y3),(x4,y4)=loc[links[j][0]],loc[links[]][1]]

den=(y4-y3)*(x2-x1)-(x4-x3)*(y2-y1)

# den==0, если прямые параллельны if den==0: continue

# В противном случае ua и ub – доли, содаваемые на каждом отрезке

# точкой их пересечения ua=((x4-x3)*(y1-y3)-(y4-y3)*(x1-x3))/den ub=((x2-x1)*(y1-y3)-(y2-y1)*(x1-x3))/den

# Если для обоих отрезков доля оказалась между 0 и 1, то они

# пересекаются

if ua>0 and ua<1 and ub>0 and ub<1: total+=1 return total

Областью определения в данном случае является диапазон изменения каждой координаты. Если сеть нужно уместить на картинке размером 400×400 пикселей, то область определения должна быть чуть меньше, чтобы осталось место для полей. Добавьте в файл socialnetwork.py такую строку:

domain=[(10,370)]*(len(people)*2) Теперь попробуйте прогнать какие-нибудь алгоритмы оптимизации и найти решения с небольшим числом пересекающихся линий:

>>> import socialnetwork >>> import optimization

>>> sol=optimization.randomoptimize(socialnetwork.domain,

socialnetwork.crosscount) >>> socialnetwork.crosscount(sol)

>>> sol=optimization.annealingoptimize(socialnetwork.domain,

socialnetwork.crosscount,step=50,cool=0.99) >>> socialnetwork.crosscount(sol)

>>> sol

[324, 190, 241, 329, 298, 237, 117, 181, 88, 106, 56, 10, 296, 370, 11, 312] Алгоритм имитации отжига, скорее всего, сможет найти решение с очень малым количеством пересечений, но интерпретировать список координат тяжело. В следующем разделе мы покажем, как автоматически нарисовать сеть.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100