triangulateMe 📐✏👽

An interactive computational geometry playground built with Three.js. Draw polygons and obstacles directly on the screen and watch classic computational geometry algorithms run step by step, with visualizations and explanations for each stage.

▶ Live Demo: defnetuncer98.github.io/triangulateMe

Developed as part of the Computer Graphics MSc program at Hacettepe University.

🦖 Fun fact: This project was written entirely by hand, before AI coding assistants were a thing. Every intersection test, every diagonal, every off-by-one bug — 100% organic, free-range, human-made code. 🙂

Modules

The app consists of three interactive modules, each demonstrating a different problem:

1. 🔺 Polygon Triangulation by Graph Coloring

Click to draw a simple polygon, then watch it get triangulated in three visualized steps:

Step	What happens	Complexity
1. Find Orientation	The rightmost vertex (on the convex hull) is located and the sign of its angle determines whether the polygon is clockwise or counter-clockwise	O(n)
2. Internal Diagonals	All candidate diagonals are tested: convex/reflex angle check, in-cone (internality) test, and edge intersection test	—
3. Two-Coloring the Graph	A graph is built where each diagonal is a node and intersecting diagonals share an edge. The graph is greedily two-colored; the "white" diagonals form a valid triangulation	—

2. ⚡ Motion Planning

Find a safe path for a point agent moving on a plane with line segment obstacles:

Step	What happens	Complexity
1. Fat Triangulation	A Delaunay triangulation is generated from the obstacle endpoints and the plane's corners	O(n log n)
2. Weighted Graph	Edge midpoints of the triangulation become graph nodes (adjacency list). Paths crossing obstacles are pruned; source and target points are added	O(n²)
3. Shortest Path	Dijkstra's algorithm finds the shortest obstacle-avoiding path from source to target	O(n²)

3. 🧊 2D Shadow

Compute which parts of a polygon are lit when light comes from all directions outside it:

Step	What happens	Complexity
1. Light Rays	Rays are shot between vertex pairs; a vertex is in the light if at least one unblocked exterior ray reaches it, otherwise it's in the shadow. Ray-boundary intersections add new light vertices on the edges	O(n³)
2. Removing Shadow Vertices	Shadowed vertices are removed to produce the new lit boundary	O(n)
3. Point Insertion	Click to add points — a ray-crossing (even–odd) test decides whether each point falls in the light zone or the shadow zone	O(n)

Running Locally

No build step or dependencies to install — it's plain HTML/CSS/JavaScript with Three.js included in the repo.

git clone https://github.com/defnetuncer98/triangulateMe.git
cd triangulateMe

# Serve with any static file server, e.g.:
python3 -m http.server 8000

Then open http://localhost:8000 in your browser.

Project Structure

triangulateMe/
├── index.html                  # Single-page app entry point
└── resources/
    ├── css/style.css
    ├── fonts/                  # Roboto (for in-scene 3D text labels)
    ├── images/                 # Custom cursor & UI gifs
    └── js/
        ├── app.js              # Page routing & global input handling
        ├── init.js             # Three.js scene setup
        ├── home.js             # Landing page
        ├── triangulate.js      # Module 1: triangulation by graph coloring
        ├── motion-planning.js  # Module 2: fat triangulation + Dijkstra
        ├── 2d-shadow.js        # Module 3: light/shadow computation
        ├── delaunay.js         # Delaunay triangulation
        ├── dijkstra.js         # Shortest path
        ├── polygon.js          # Polygon model (orientation, in-cone, intersection tests)
        ├── point.js / line.js  # Geometry primitives
        └── common-*.js         # Shared helpers (math, Three.js utilities)

Built With

• Three.js — rendering, scene management, and 3D text
• Vanilla JavaScript — all geometry algorithms implemented from scratch (except the Delaunay routine)
• Font Awesome — icons

Author

Defne Tunçer — @defnetuncer98

Created for the Computational Geometry coursework, Computer Graphics MSc @ Hacettepe University.