Risanje vozlov z vzmetnimi algoritmi

diplomsko delo

Nik Zupančič (Author), Gašper Fijavž (Mentor)

Abstract

V delu izdelamo in opišemo postopek za izračun vizualno ustrezne slike diagrama vozla. Vozel je, formalno, vložitev krožnice v trirazsežni prostor. Projekcijo vozla v ravnino imenujemo diagram vozla, ki ga lahko kombinatorično opišemo z Gaussovo kodo. Gaussova koda bo naš vhodni podatek pri problemu izrisa. Najprej izdelamo in opišemo kriterij, ki preveri, ali je Gaussova koda sploh pravilna. V nadaljevanju skonstruiramo ravninski graf, ki je podaljšek pravilne Gaussove kode, hkrati pa služi kot osnova za izračun ustrezne slike vozla. V prvi fazi koordinate točk grafa določimo s pomočjo vzmetnega algoritma Fruchtermana in Reingolda. Nato graf, upoštevajoč njegove geometrijske omejitve, popravimo, in v drugi fazi izračunamo koordinate točk s pomočjo algoritma Kamada-Kawai, pri čemer pa dodatno upoštevamo vzmeti v smeri enakomernih kotov okoli posameznih križišč vozla in vzmeti v smeri ravnanja prevojev. Slednjič izračunane točke grafa uporabimo kot interpolacijske točke za izračun vozlove krivulje. V zadnjem delu predstavimo tudi slike diagramov vseh vozlov z relativno majhnim številom križišč.

Keywords

vozel;ravninski graf;risanje grafov;vzmetni algoritem;interpolacija;Fruchterman-Reingoldov algoritem;algoritem Kamada-Kawai;kardinalni zlepek;računalništvo in informatika;univerzitetni študij;diplomske naloge;

Data

Language:	Slovenian
Year of publishing:	2019
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[N. Zupančič]
UDC:	004(043.2)
COBISS:	1538333635
Views:	571
Downloads:	162
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Drawing knots using spring embedders
Secondary abstract:	In this thesis we describe and implement a system for drawing knot diagrams in a visually pleasing way. A knot is formally an embedding of a circle in the 3-space. Its projection into the plane is called a diagram, which can in turn be combinatorially described using Gaussian code. Gaussian code serves as our input. We first describe a criterion which decides whether the code indeed represents a knot. In what follows we construct a plane graph, which serves as the extension to the code and serves as the initial step in constructing the layout. Fruchterman-Reingold spring embedding algorithm is used as the first step in determining positions of crossings. Afterwards the graph is adjusted, and Kamada-Kawai approach is used in the second phase. In this phase we use additional force-like constraints that control uniform angle positions around a crossing and also serve to diminish the severity of inflections. Finally the vertex coordinates are used as interpolation points for the curve. We also present layouts of several knots with small number of crossings.
Secondary keywords:	knot;plane graph;graph drawing;spring embedder;interpolation;Fruchterman-Reingold algorithm;Kamada-Kawai algorithm;cardinal spline;computer and information science;diploma;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000468
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	54 str.
ID:	11221277