The Samples of GeoSheet

Graph Algorithms

Minimum Spanning Tree

This algorithm calculates the minimum spanning tree of the input graph.

Maximum Cardinality Bipartite Matching

This algorithm finds a matching of vertices from a bipartitie graph that has a maximum cardinality. A matching is a set of edges which do not have any vertex in common.

Delaunay Triangulation Algorithm

It first takes as input a list of points and generates the Delaunay triangulation. Then it computes a directed graph representing the planar subdivision defined by the Voronoi diagram of the input points. It also returns the convex hull of the input points. It is based on a randomized incremental algorithm.

Visibility of A Simple Polygon

Find the region within a polygon which is visible from a given point located either on a vertex or inside the given polygon.

Delaunay Triangulation

This algorithm computes the Delaunay triangulation by plane sweep method. Original code was implemented by Steven Fortune.

Planar Point Location Problem

This algorithm is to preprocess a set of non-vertical straight line segments into a data structure so that for any given query point p one can determine quickly which segment is the first one directly below p. Original code was implemented by Raimund Seidel.

Source code is available.