La computación geométrica es una rama de la informática que se enfoca en el estudio de algoritmos y estructuras de datos para resolver problemas geométricos.
La biblioteca Habrador/Computational-Geometry es una recopilación Open Source que proporciona implementaciones eficientes de varios algoritmos geométricos.
Entre los algoritmos disponibles están,
- Triangulación: División de un polígono en triángulos.
- Convex Hull: Cálculo del menor polígono convexo que contiene un conjunto de puntos.
- Intersección de segmentos: Detección de intersección entre líneas y segmentos.
- Algoritmos de visibilidad: Cálculo de áreas visibles desde un punto.
- Diagramas de Voronoi: División del plano basado en distancias a un conjunto de puntos.
- Redes de Delaunay: Triangulación optimizada de un conjunto de puntos.
- Polígonos y operaciones: Manipulación y análisis de polígonos.
Habrador/Computational-Geometry es de código abierto y todo su código y documentación están disponibles en el repositorio del proyecto en GitHub - Habrador/Computational-geometry.
Algunos ejemplos
Aquí algunos ejemplos de los algoritmos incluidos en Habrador/Computational-Geometry. Para más información, consultar la documentación de la librería.
Cálculo de Convex Hull
Este ejemplo muestra cómo calcular el convex hull de un conjunto de puntos utilizando el algoritmo de Graham Scan.
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})");
}
}
}Triangulación de un polígono
En este ejemplo, se muestra cómo dividir un polígono en triángulos utilizando la biblioteca.
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})");
}
}
}Detección de intersección de segmentos
Este ejemplo muestra cómo detectar la intersección entre segmentos de línea.
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");
}
}
}Diagrama de Voronoi
Este ejemplo muestra cómo generar un diagrama de Voronoi a partir de un conjunto de puntos.
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})");
}
}
}