Habrador Computational-Geometry Library in C#

Computational geometry is a branch of computer science that focuses on the study of algorithms and data structures to solve geometric problems.

The Habrador/Computational-Geometry library is an Open Source collection that provides efficient implementations of various geometric algorithms.

Among the available algorithms are:

• Triangulation: Dividing a polygon into triangles.
• Convex Hull: Calculating the smallest convex polygon that contains a set of points.
• Segment Intersection: Detecting intersection between lines and segments.
• Visibility Algorithms: Calculating visible areas from a point.
• Voronoi Diagrams: Dividing the plane based on distances to a set of points.
• Delaunay Networks: Optimized triangulation of a set of points.
• Polygons and Operations: Manipulation and analysis of polygons.

Habrador/Computational-Geometry is open source, and all its code and documentation are available in the project repository on GitHub - Habrador/Computational-geometry.

Some Examples

Here are some examples of the algorithms included in Habrador/Computational-Geometry. For more information, refer to the library documentation.

Convex Hull Calculation

This example shows how to calculate the convex hull of a set of points using the Graham Scan algorithm.

using System;
using System.Collections.Generic;
using Habrador.ComputationalGeometry;

class Program
{
    static void Main(string[] args)
    {
        List<MyVector2> points = new List<MyVector2>
        {
            new MyVector2(0, 0),
            new MyVector2(1, 1),
            new MyVector2(2, 2),
            new MyVector2(1, 2),
            new MyVector2(2, 1),
            new MyVector2(3, 3)
        };

        List<MyVector2> convexHull = ConvexHullAlgorithms.GrahamScan(points);

        Console.WriteLine("Convex Hull:");
        foreach (var point in convexHull)
        {
            Console.WriteLine($"({point.x}, {point.y})");
        }
    }
}

Polygon Triangulation

In this example, it shows how to divide a polygon into triangles using the library.

using System;
using System.Collections.Generic;
using Habrador.ComputationalGeometry;

class Program
{
    static void Main(string[] args)
    {
        List<MyVector2> polygon = new List<MyVector2>
        {
            new MyVector2(0, 0),
            new MyVector2(2, 0),
            new MyVector2(2, 2),
            new MyVector2(0, 2)
        };

        List<Triangle2> triangles = Triangulator.TriangulatePolygon(polygon);

        Console.WriteLine("Triangles:");
        foreach (var triangle in triangles)
        {
            Console.WriteLine($"({triangle.p1.x}, {triangle.p1.y}), ({triangle.p2.x}, {triangle.p2.y}), ({triangle.p3.x}, {triangle.p3.y})");
        }
    }
}

Segment Intersection Detection

This example shows how to detect the intersection between line segments.

using System;
using Habrador.ComputationalGeometry;

class Program
{
    static void Main(string[] args)
    {
        MyVector2 p1 = new MyVector2(0, 0);
        MyVector2 p2 = new MyVector2(2, 2);
        MyVector2 p3 = new MyVector2(0, 2);
        MyVector2 p4 = new MyVector2(2, 0);

        bool intersects = Intersections.Intersect(p1, p2, p3, p4, out MyVector2 intersectionPoint);

        if (intersects)
        {
            Console.WriteLine($"Intersection at: ({intersectionPoint.x}, {intersectionPoint.y})");
        }
        else
        {
            Console.WriteLine("No intersection");
        }
    }
}

Voronoi Diagram

This example shows how to generate a Voronoi diagram from a set of points.

using System;
using System.Collections.Generic;
using Habrador.ComputationalGeometry;

class Program
{
    static void Main(string[] args)
    {
        List<MyVector2> points = new List<MyVector2>
        {
            new MyVector2(1, 1),
            new MyVector2(3, 1),
            new MyVector2(2, 3)
        };

        VoronoiDiagram voronoi = VoronoiDiagram.Generate(points);

        Console.WriteLine("Voronoi Edges:");
        foreach (var edge in voronoi.edges)
        {
            Console.WriteLine($"({edge.v0.x}, {edge.v0.y}) -> ({edge.v1.x}, {edge.v1.y})");
        }
    }
}