20.500.12556/RUL-110074 Risanje vozlov z vzmetnimi algoritmi Drawing knots using spring embedders 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šč. 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. vozel ravninski graf risanje grafov vzmetni algoritem interpolacija Fruchterman-Reingoldov algoritem algoritem Kamada-Kawai kardinalni zlepek knot plane graph graph drawing spring embedder interpolation Fruchterman-Reingold algorithm Kamada-Kawai algorithm cardinal spline true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2019-09-11 15:05:17 2019-09-11 15:05:20 2022-08-22 03:41:29 0000-00-00 00:00:00 2019 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 24021 1538333635 Zupancic_Nik_-_Risanje_vozlov_z_vzmetnimi_algoritmi.pdf Zupancic_Nik_-_Risanje_vozlov_z_vzmetnimi_algoritmi.pdf 1 FD6ACD73A3C0E3C019CD0F460C764B19 3cf4f466a993ffd2311e2d84604f29a6ae4cc1a09cbdbe874845233cbaa25f09 06eb86bd-a1b7-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=121693 Fakulteta za računalništvo in informatiko 0 0 0