В данном уроке будет предоставлен пример реализации "Жадного алгоритма триангуляции" на Python.
Начнём с установки Tkinter. Вводим в терминале или просто в командной строке:
pip install tkinter
После установки можно приступить к написанию кода. Сперва импортируем всё, что нам понадобится для работы:
from tkinter import * from itertools import combinations from math import sqrt from collections import OrderedDict
Сперва мы импортировали всё содержимое графической библиотеки tkinter, затем функции combinations и sqrt из стандартных библиотек и наконец OrderDict - словарь, который помнит порядок (тоже из стандартной библиотеки).
Создадим холст, который будет появляться при запуске программы с размерами 800х600:
tk = Tk() canvas = Canvas(tk, height=800, width=800) canvas.pack()
Теперь мы готовы к работе и можно смело переходить к написанию функций. Первое, что нам понадобится - это функция, которая получает на вход координаты начала и конца отрезка, а затем вычисляет и возвращает длину отрезка:
def distance(x1, y1, x2, y2): """Считает длину отрезка по координатам начала и конца""" return sqrt((x2 - x1)**2 + (y2 - y1)**2)
Перейдём к написанию функции, которая определяет, пересекаются ли две прямые на плоскости. Стоит отметить важный момент, что случай, когда точка пересечения двух прямых является вершиной нашего многоугольника, является допустимым, поэтому мы проверяем его отдельно.
def is_intersect(x1, y1,x2, y2, x3, y3,x4, y4): """Проверяет, пересекаются ли прямые. Случай, когда точкой пересечения являются концы отрезков (одна из вершин многоугольника) пересечением не считаются.""" if min(x1,x2)<=max(x3,x4) and min(y3,y4)<=max(y1,y2) and min(x3,x4)<=max(x1,x2) and min(y1,y2)<=max(y3,y4): if ((x1==x3) and (y1==y3)) or ((x2==x4) and (y2==y4)) or ((x1==x4) and (y1==y4)) or ((x2==x3) and (y2==y3)): return False return True else: return False
Перед написанием главной функции нам необходимо сделать так, чтобы каждый клик по экрану оставлял после себя точку и её координаты сохранялись.
Каждая точка, которая получается в результате клика, является вершиной нашего многоугольника.
Помимо этого я предлагаю создать все необходимые для работы глобальные переменные.
Под созданием холста напишем следующие строки:
default = [] n = int(input("Введите количество точек многоугольника: ")) coordinates = [] loops = 0 canvas.bind("<Button-1>", save_cord)
В списке default будут храниться прямые, которые составляют "каркас" нашего многоугольника. n - переменная, которую мы введём из с клавиатуры. В списке coordinates будут храниться координаты всех кликов. Переменная loops считает, сколько точек многоугольника вы поставили, а последняя строка привязывает к ЛКМ функцию save_cord, которая будет вызываться после каждого клика.
Каркас многоугольника необязательно запоминать и наносить вручную, алгоритм итак с этим отлично справится. Здесь же это сделано, чтобы лишний раз "перестраховаться" и чтобы процесс стал ещё более понятным.
Перейдём функции save_cord event:
def save_cord(event): """Сохраняет координаты, проставленные при помощи ЛКМ.""" global loops, n coordinates.append((event.x, event.y)) canvas.create_rectangle(event.x, event.y, event.x+2, event.y+2, width=2) loops += 1 if loops == n: triangulate()
Который передаётся в функцию является тем кликом ЛКМ, и этот параметр является обязательным. Именно благодаря нему мы сможем получить координаты клика.
Сперва мы говорим, что будем работать с глобальными переменными nи loops. Затем добавляем в список координаты клика.
После этого мы рисуем точку на месте клика. В tkinter нет функции, которая бы проставляла точки, поэтому на её месте мы создаём маленький прямоугольник, по размерам близкий к точке. Этот многоугольник имеет толщину граней width=2. После этого мы увеличиваем количество проставленных точек на 1 и проверяем, все ли точки проставлены.
Если все точки проставлены, то есть loops == n, то мы вызываем функцию triangulate. К её написанию я и предлагаю перейти.
global coordinates #сохраняем рёбра многоугольника в список default for i in range(len(coordinates)-1): default.append(list(coordinates[i]) + list(coordinates[i+1]))
Сперва получим доступ к глобальной переменной coordinates, в которой хранятся координаты наших вершин.
Далее мы проходим по элементам coordinates, которые представляют собой кортежи (x,y) и последовательно "создаём" каркас нашего многоугольника. Каждая итерация в списке создаёт список ([x1,y1,x2,y2,x3,y3,x4,y4]), который хранит в себе координаты начала и конца ребра и добавляет его в список default.
default.append(list(coordinates[0])+list(coordinates[-1]))
Важно не забыть ребро, которое соединяет первую и последнюю вершины.
Затем при помощи функции combinations мы генерируем все возможные из наших точек прямые и сохраняем все это в список:
coordinates = list(combinations(coordinates, 2))
Элементы этого списка имеют следующий вид - ((x1,y1), (x2,y2)), поэтому предлагаю преобразовать их к виду (x1, y1, x2, y2):
for i in range(len(coordinates)): coordinates[i] = coordinates[i][0] + coordinates[i][1]
Отлично. Теперь нам нужны длины сторон. Для их хранения создадим словарь, в котором ключами будут координаты начала и конца отрезка, а значение будет хранить его длину и заполним его при помощи нашей функции distance:
dict_lenth = {} for i in coordinates: dict_lenth[i] = distance(*i)
Теперь, согласно алгоритму, нам нужно отсортировать данный словарь по длинам сторон, но как вы знаете, словари в Python не запоминают порядок, в котором были добавлены элементы. Поэтому если мы отсортируем его, то есть большой риск, что после сортировки мы по прежнему получим неотсортированный словарь.
Чтобы не потерять результаты нашей сортировки, мы импортировали специальный класс OrderedDict в самом начале, который представляет собой словарь, помнящий порядок, а это как раз то, что нам нужно.
Создадим новый словарь sorted_lenth, в котором всё будет отсортировано по длине:
sorted_lenth = OrderedDict(sorted(dict_lenth.items(), key=lambda x: x[1]))
Далее создадим список sorted_coord, в котором будут хранится координаты всех возможных сторон (отсортированные по длине этих самых сторон):
sorted_coord = list(sorted_lenth.keys())
Теперь удалим из этого списка координаты прямых, которые формируют каркас нашего многоугольника (их мы итак нанесём, и они не нуждаются в проверках):
for i in default: if tuple(i) in sorted_coord: sorted_coord.remove(tuple(i))
Далее создадим список inserted, в котором будут хранится все рёбра, удовлетворяющие условию алгоритма. То есть те, что не пересекаются с другими ранее вставленными отрезками. Сразу добавим в этот список самое короткое ребро, так как мы его точно нанесём (ведь внутри многоугольника точно будет хотя бы одна диагональ).
inserted = [] inserted.append(sorted_coord[0])
Перейдём к основному циклу программы, а затем разберёмся, что же там происходит:
for i in range(1, len(sorted_coord)): check = True for j in inserted: if is_intersect(*sorted_coord[i], *j): check = False break if check: inserted.append(sorted_coord[i])
Мы "бежим" по списку, который хранит в себе координаты прямых, отсортированных по длине. Для каждой прямой мы делаем проверку: пересекается ли она хотя бы с одной из прямых, которые были нанесены ранее? Если да, то флаг check переходит в False и цикл прерывается. Если же пересечений не найдено, то координаты данной прямой сохраняются в списке inserted .
Осталось нанести всё на холст:
for i in default: canvas.create_line(*i) for i in inserted: canvas.create_line(*i)
Как вы помните, в списке default хранятся все прямые, которые образуют каркас, а в списке inserted отрезки, внутри многоугольника. Мы передаём функции canvas.create_line координаты начала и конца каждого отрезка и она наносит их на холст.
Не забудьте поставить в конце программы tk.mainloop(), чтобы холст сразу не закрылся.
Перед нанесением точек на холст необходимо ввести их количество в консоль.
Код программы:
from tkinter import * from itertools import combinations from math import sqrt from collections import OrderedDict def distance(x1, y1, x2, y2): """Считает длину отрезка по координатам начала и конца""" return sqrt((x2 - x1)**2 + (y2 - y1)**2) def is_intersect(x1, y1,x2, y2, x3, y3,x4, y4): """Проверяет, пересекаются ли прямые. Случай, когда точкой пересечения являются концы отрезков (одна из вершин многоугольника) пересечением не считаются.""" if min(x1,x2)<=max(x3,x4) and min(y3,y4)<=max(y1,y2) and min(x3,x4)<=max(x1,x2) and min(y1,y2)<=max(y3,y4): if ((x1==x3) and (y1==y3)) or ((x2==x4) and (y2==y4)) or ((x1==x4) and (y1==y4)) or ((x2==x3) and (y2==y3)): return False return True else: return False def save_cord(event): """Сохраняет координаты, проставленные при помощи ЛКМ.""" global loops, n coordinates.append((event.x, event.y)) canvas.create_rectangle(event.x, event.y, event.x+2, event.y+2, width=2) loops += 1 if loops == n: triangulate() def triangulate(): global coordinates #сохраняем рёбра многоугольника в список default for i in range(len(coordinates)-1): default.append(list(coordinates[i]) + list(coordinates[i+1])) #ребро, соединяющее начало и конец default.append(list(coordinates[0])+list(coordinates[-1])) # Генерируем список всех возможных отрезков, соединяющих пары исходных точек. coordinates = list(combinations(coordinates, 2)) #Преобразовываем координаты начала и конца к виду (x1,y1, x2,y2,x3,y3,x4,y4) for i in range(len(coordinates)): coordinates[i] = coordinates[i][0] + coordinates[i][1] #создаём словарь, в котором ключами будут координаты начала и конца отрезка, а значение будет хранить его длину dict_lenth = {} for i in coordinates: dict_lenth[i] = distance(*i) sorted_lenth = OrderedDict(sorted(dict_lenth.items(), key=lambda x: x[1])) sorted_coord = list(sorted_lenth.keys()) #удаляем из всех возможных комбинаций те, которые уже использованы в каркасе for i in default: if tuple(i) in sorted_coord: sorted_coord.remove(tuple(i)) #тут хранятся все вставленные рёбра inserted = [] inserted.append(sorted_coord[0]) for i in range(1, len(sorted_coord)): check = True for j in inserted: if is_intersect(*sorted_coord[i], *j): check = False break if check: inserted.append(sorted_coord[i]) for i in default: canvas.create_line(*i) for i in inserted: canvas.create_line(*i) tk = Tk() canvas = Canvas(tk, height=800, width=800) canvas.pack() default = [] n = int(input("Введите количество точек многоугольника: ")) coordinates = [] loops = 0 canvas.bind("<Button-1>", save_cord) tk.mainloop()
Прикрепленный файл | Размер |
---|---|
gif.gif | 40.71 кб |
triang.rar | 1.48 кб |
photo_2022-01-15_15-20-07.jpg | 19.31 кб |