Thesis: Smallest Enclosing Circle & Voronoi Diagram

Implementation of an O(n log n) algorithm for the Smallest Enclosing Circle and the Voronoi Diagram, using efficient structures (Red‑Black tree, HashMap) with a JavaFX GUI.

Sven Skyum, “Implementation of an Algorithm for the Calculation of the Smallest Enclosing Circle and the Voronoi Diagram,” 1991.

Download Latest Release (Windows executable)

📋 Table of Contents

1. Overview
2. Features
3. Screenshots
4. Technologies
5. Installation
6. Usage
7. Architecture
8. Contributing
9. License
10. Contact

Overview

This project implements Sven Skyum’s 1991 algorithm for computing the Smallest Enclosing Circle and the Voronoi Diagram in O(n log n) time, using Java 17, JavaFX, and classic data structures (Red‑Black BST, HashMap). It follows MVC and Singleton patterns to deliver a user‑friendly GUI on Windows.

Features

• Efficient O(n log n) algorithm for smallest enclosing circle (Welzl/Skyum).
• Voronoi diagram construction via divide‑and‑conquer and balanced trees.
• JavaFX GUI: Interactive visualization, zoom/pan, and export functionality.
• MVC architecture for clean separation of model, view, and controller.
• Multiple input formats: CSV, Excel via Apache POI, and manual point entry.

Screenshots

Technologies

Layer	Technology
Language	Java 17
GUI	JavaFX 19
Data Parsing	OpenCSV 5.7.1, Apache POI 5.2.3
Algorithms	Custom Red‑Black BST, HashMap, divide‑and‑conquer
Patterns	MVC, Singleton

Installation

Clone repository

git clone https://github.com/johnprif/Thesis.git
cd Thesis

Usage

1. Load points: Load -> Open CSV/Excel or manual input.
2. Visualize: Pan/zoom the JavaFX canvas; use export buttons for PNG.

Architecture

+----------------+      +-----------------+      +------------------+
| JavaFX GUI     | <--> | Controller      | <--> | Algorithm Module |
+----------------+      +-----------------+      +------------------+
                                 |
                                 v
                       +----------------------+
                       | Data Parser (CSV/Excel) |
                       +----------------------+

• MVC separates presentation (JavaFX), control flow (Controller), and computation (Algorithm).
• Algorithm Module implements circle/Voronoi logic with Red-Black BST and HashMap.

Contributing

Contributes welcome! Please:

1. Fork the repo.
2. Create a feature branch: git checkout -b feature/YourFeature.
3. Commit: git commit -m "Add YourFeature".
4. Push: git push origin feature/YourFeature.
5. Open a Pull Request.

License

This project is licensed under the MIT License, See LICENSE for details.

Contact

• GitHub: joanisprifti
• Email: joanisprifti@gmail.com
• Phone: +306940020178