Алгоритм кируса бека реализация python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

💫 Drawing cool circles, squares and other tricks on the computer.

shlyapos/bmstu_cg

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

2nd course, IU7 Bauman Moscow State Technical University 

Лабы лучше не делать на ткинтере (кроме может быть первых двух)

Спасибо Winterpuma и Panda-Lewandowski за вдохновение на выполнение лаб

✅ Лр #1 Геометрическая задача

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

Реализация (Python Tkinter)

✅ Лр #2 Преобразование изображений

Реализовать операции перемещения, поворота и масштабирования изображения птички.

Реализация (Python Tkinter)

⛔ Лр #3 Алгоритмы разложения отрезка в растр

Проблемы с реализацией (сделана хорошо только обёртка библиотечной функции (лол) и может быть ЦДА)

Реализация (лучше не надо)(Python Tkinter)

⁉️ Лр #4 Алгоритмы разложения эллипсов в растр

Что-то может правильно, что-то может неправильно

Реализация (Python Tkinter)

✅ Лр #5 Алгоритмы заполнения сплошных областей

Алгоритм заполнения по рёбрам.

Реализация (C++ Qt)

✅ Лр #6 Алгоритм построчного затравочного заполнения сплошных областей

Реализация (C++ Qt)

✅ Лр #7 Алгоритмы отсечения отрезка регулярным отсекателем

Простой алгоритм (о нет)

Реализация (C# Windows Forms)

Источник

Алгоритм Кирусе-Бека

Доброго времени суток всем. Вообщем реализовываю алгоритм Кируса-Бека( тут), и по неизвестной мне причине, он не работает, никак не могу найти ошибку. Помогите пожалуйста, то ли глаз замылился, то ли мозги заплыли.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

mult = lambda a, b: a.x * b.x + a.y * b.y class Point(object): def __init__(self, x, y): self.x = float(x) self.y = float(y) class Line(object): def __init__(self, begin, end): self.begin = begin self.end = end @property def direction(self): return Point(self.end.x - self.begin.x, self.end.y - self.begin.y) @property def normal(self): return Point(self.end.y - self.begin.y, self.begin.x - self.end.x) class Polygon(object): def __init__(self, points): self.count = len(points) self.edges = [] for i in xrange(self.count-1): self.edges.append(Line(points[i], points[i+1])) self.edges.append(Line(points[-1], points[1])) # сам алгоритм!! def cyruse_beck(self, l): t_begin = 0.0 t_end = 1.0 dirL = l.direction for edge in self.edges: dir_edg = edge.direction Q = Point(l.begin.x - dir_edg.x, l.begin.y - dir_edg.y) N = edge.normal Pn = mult(dirL, N) Qn = mult(Q, N) if Pn == 0: if Qn  0: return False else: t = -Qn / Pn if Pn  0: if t  t_begin: return False t_end = min(t_end, t) else: if t > t_end: return False t_begin = max(t_begin, t) if t_end > t_begin: if t_begin > 0: l.begin = Point(l.begin.x + t_begin * dirL.x, l.begin.y + t_begin * dirL.y) if t_end  1: l.end = Point(l.begin.x + t_end * dirL.x, l.begin.y + t_end * dirL.y) else: return False return True

Источник

Алгоритмы отсечения

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

Этот пост посвящён разбору нескольких алгоритмов, направленных на одну и ту же задачу, задачу отсечения отрезков. При генерации изображений могут получаться фигуры произвольной формы и размеров. Зачастую мониторы не могут отобразить сгенерированные изображения целиком. Также иногда возникают ситуации, когда необходимо задать область изображения на экране и выводить изображения только внутри этой области. Для решения этих задач и придуманы алгоритмы отсечения.

Отсечение отрезков

Самой простой задачей отсечения является задача отсечения отрезков. Сформулируем её на конкретном примере. Будем считать, что область вывода задаётся прямоугольником ABCD. Рассмотрим пример, и в качестве отсекаемой фигуры возьмём треугольник PRQ.

Процесс отсечения должен выполняться полностью автоматически. Т.е. для отрисовки треугольника PRQ должны выполниться только команды отрисовки отрезков PQ;PP’;Q’ Q. При этом координаты точек P’;Q’ заранее не известны.
На практике возможно большое количество взаимных расположений точек отрезка и области вывода. Это разнообразие делает операцию отсечения весьма нетривиальной с алгоритмической точки зрения. Для решения этих задач созданы алгоритмы отсечения.

Алгоритм Сазерленда-Коэна

Весьма интересен алгоритм отсечения, предложенный Сазерлендом и Коэном. Суть алгоритма заключается в том, что концам отрезка присваивается четырёхбитный код: b₀,b₁,b₂,b₃. Этот четырёхбитный код содержит информацию о положении точки относительно области вывода. На практике возможны 9 комбинаций:

Поясним эти коды:
Поясним эти коды:

• b₀=0, если x≥x_min;
• b₀=1, если xmin;
• b₁=0, если x≤x_max;
• b₁=1, если x>x_max;
• b₂=0, если y≥y_min;
• b₂=1, если ymin;
• b₃=0, если y≤y_max;
• b₃=1, если y>y_max;

1. Коды содержат только 0, а значит отрезок целиком лежит внутри окна и должен быть отрисован целиком;
2. Коды содержат единичный бит в одной и той же позиции, а значит, отрезок лежит за пределами окна и не будет отрисован;
3. Во всех остальных случаях в окне лежит только часть отрезка, и это значит, что есть необходимость в отсечении.

Если код любого из концов содержит единичный бит, то либо P₁, либо P₂ перемещается из-за пределов окна к одной из его границ (или к её продолжению). Т.е. точка P₁ перемещается в точку R, а P₂ в точку U. Для новых точек мы вновь вычисляем четырёхбитные коды. В нашем случае концы отрезка по-прежнему лежат вне окна, т.е. нам понадобится ещё одно перемещение: точка R переместиться в точку S, а точка U переместиться в точку T. Получается, что процесс отсечения является итеративным. Так как на каждом шаге уменьшается расстояние между концами отрезка, мы можем утверждать, что алгоритм сойдётся. В итоге будет получен отрезок (в нашем случае (S;T), который и надо отобразить).
Рассмотрим работу этого алгоритма на ещё одном примере.

Расположение отрезка (P₁;P₂) не соответствует ни условиям полной видимости, ни условиям полной невидимости, поэтому в этом случае тоже прибегнуть к операции переноса точек.

После выполненных переносов коды концов отрезка удовлетворяют второму условию, т.е. отрезок целиком не будет выводиться на экран.

Алгоритм средней точки

В алгоритме Сазерленда-Коэна поиск точки пересечения отрезка с границей окна может занять несколько итераций. Этого можно избежать, если реализовать поиск точки пересечения с помощью двоичного поиска. Эта идея была предложена Спруллом и Сазерлендом. Программная реализация этого алгоритма медленнее, чем алгоритм Сазерленда-Коэна, но аппаратная реализация быстрее, так как основные операции алгоритма весьма эффективно реализуются в аппаратуре.

Этот метод также использует четырёхбитный код, описанный выше. С помощью этих кодов легко выявляются случаи тривиальной видимости (a) и тривиальной невидимости (b). Остальные (нетривиальные) отрезки разбиваются на две равные части, и проверки выполняются для двух вновь полученных отрезков. Деление и проверки будут выполняться до тех пор, пока не будет обнаружено пересечение со стороной окна, или пока отрезок не выродится в точку. После того, как отрезок выродился, мы определяем его видимость и в зависимости от результата либо отрисовываем току, либо нет.
Рассмотрим отрезок c. Очевидно, что этот отрезок целиком лежит вне границ окна, но он не может быть отвергнут сразу. Именно поэтому мы выполняем половинные деления и исключаем некоторые части отрезка. Деление заканчивается в тот момент, когда отрезок превращается в точку. Убедившись, что полученная точка невидима, мы делаем вывод, что и весь отрезок не должен быть отрисован.
Отрезок d тоже не определяется тривиально. Его деление на две половины (точкой 3) приводит к одинаковым результатам для обеих половин. Отрезок (3;2) разбиваем пополам точкой 4. Теоретически можно уже отрисовать отрезок (3;4), но это не очень эффективно. Правильнее запомнить точку 4, как наиболее удалённую от точки 1 видимую точку, а отрезок (4;2) продолжить разбивать до пересечения с нижней границей окна. Полученная точка и будет считаться наиболее удалённой от точки 1 видимой точкой. Аналогично обрабатывается отрезок 3;1, и находится видимая точка, наиболее удалённая от точки 2. Потом между двумя этими точками и происходит отрисовка.
Для отрезков типа d необходимо выполнять два двоичных поиска видимых точек, наиболее удалённых от концов отрезка. Для отрезков типа e необходимость в одном из двоичных поисков отпадает.

Алгоритм Кируса-Бека

В работе алгоритма Кируса-Бека используется параметрическое представление отрезка: P_s (t)=P₁+(P₂-P₁)*t;t∈[0;1]. Данный алгоритм позволяет выполнять отсечение не только прямоугольным окном, но и любым выпуклым многоугольником.
Рассмотрим отдельное ребро E_i отсекающего многоугольника. Ориентируем нормаль к этому ребру во внешнюю сторону отсекающего многоугольника. Также будем считать, что отсекающий многоугольник обходится против часовой стрелки. Тогда, если ребро – это вектор P_(E(i1)) P_Ei2, то нормаль N_Ei будет пропорциональна (y_Ei2-y_Ei1; x_Ei1-x_Ei2).
Обозначим прямую, на которой лежит ребро через L_i. Тогда область, отсекаемая прямой L_i, соответствует точкам P, для которых скалярное произведение векторов (P-P_Ei)) и N_Ei больше 0 (P_Ei — любая точка на ребре E_i). Точка пересечения прямой, на которой лежит отрезок, с отсекающей прямой L_i находится из уравнения ((P_s(t)-P_Ei,N_Ei=0. Решая это уравнение, находим t.
Для описываемого алгоритма также важно в каком направлении (внутрь окна или из него) проходит точка при движении по отрезку от P₁ к P₂. Это определяется знаком ((P₂-P₁ ),N_Ei. Будем обозначать такие точки пересечения как:

После того, как рассчитаны координаты t для всех возможных пересечений с прямыми L_i, следует выбрать максимальную координату из потенциально входящих и минимальную из потенциально выходящих (t_ВхМакс;t_ВыхМин). Если прямая, на которой лежит отрезок P₁ P₂, пересекает отсекающий многоугольник, то t_ВхМаксВыхМин. В этом случае, если пересечение [t₁,t₂]=[t_ВхМакс,t_ВыхМин]∩[0,1] непусто, то P_s(t₁) P_s(t₂) и будет искомым отсечённым отрезком, в противном случае отрезок полностью лежит вне отсекаемой области.

На этих алгоритмах тема отсечения, разумеется, не заканчивается. Отдельный вопрос — алгоритмы отсечения многоугольников. Если тема будет интересна хабрасообществу, я обязательно раскрою и эту тему.

Источник