Projects of Sigbjørn Vik

A few of my past personal projects that were written for distribution, rather than solely personal use or learning.

Polygon Triangulation
Football Manager Game

Polygon Triangulation

As my senior thesis at Macalester College I did a honors project on polygon triangulation. I implemented the currently best known method of triangulating polygons in Mathematica, showed how the method could be optimized in certain cases, and generalized (and implemented) the method to be able to deal with multiple intersecting polygons and lines.

Abstract

In 1991 Seidel found a practical algorithm for triangulating simple polygons with an expected running time of O(n log* n). This paper describes an implementation of his routine, and shows how the theoretical time bound compares to the experimental. Several generalizations and optimizations of his routine are discussed, and the final result is an algorithm that can triangulate any set of overlapping and self-intersecting polygons and lines in the plane with near-linear expected running time. The implementation is completed with a set of functions that will graphically display any step of the algorithm.

Thesis and Code

An implementation of a Near-Linear Polygon Triangulation Algorithm for General Polygons: Thesis in .pdf format - 119 kB
Appendices: Code, Documentation and Movies in Mathematica 3.0 format - zipped to 227 kB

Free Programs

Acrobat Reader: Program to view .pdf files
Winzip: Program to extract and viev zipped files
MathReader: Program to view Mathematica files

Football Manager Game

My first big project - long before I even understood words such as "statements", "syntax" and "optimization". Programmed from scratch in <a href='http://www.pascal-central.com/'>Pascal</a>, without ever having read a programming book, I am still quite proud of this Norwegian game. This project was finished, and distributed to friends who loved the game. I never did manage to get around to writing version 2 though, with a number of suggested gameplay improvements made by my friends.

Downloads

Mål: The game, along with all the source code in .zip format - 59 kB
Winzip: Free program to extract and viev zipped files