bl4ckb0ne / Delaunay Triangulation
Licence: gpl-3.0
C++ version the delaunay triangulation
Stars: ✭ 339
Projects that are alternatives of or similar to Delaunay Triangulation
Xseries
Library for cross-version Minecraft Bukkit support and various efficient API methods.
Stars: ✭ 109 (-67.85%)
Mutual labels: algorithm, library
Earcut
The fastest and smallest JavaScript polygon triangulation library for your WebGL apps
Stars: ✭ 1,359 (+300.88%)
Mutual labels: algorithm, triangulation
Polysnap
A work in progress polygon operations library with integer snap-rounding
Stars: ✭ 14 (-95.87%)
Mutual labels: algorithm, library
Swarmz
A free, header-only C++ swarming (flocking) library for real-time applications
Stars: ✭ 108 (-68.14%)
Mutual labels: algorithm, library
React Native Blurhash
🖼️ A library to show colorful blurry placeholders while your content loads.
Stars: ✭ 430 (+26.84%)
Mutual labels: algorithm, library
C Algorithms
A library of common data structures and algorithms written in C.
Stars: ✭ 2,654 (+682.89%)
Mutual labels: algorithm, library
Cosmos
Hacktoberfest 2021 | World's largest Contributor driven code dataset | Algorithms that run our universe | Your personal library of every algorithm and data structure code that you will ever encounter |
Stars: ✭ 12,936 (+3715.93%)
Mutual labels: algorithm, library
Arabiccompetitiveprogramming
The repository contains the ENGLISH description files attached to the video series in my ARABIC algorithms channel.
Stars: ✭ 675 (+99.12%)
Mutual labels: algorithm, library
Delaunator Cpp
A really fast C++ library for Delaunay triangulation of 2D points
Stars: ✭ 244 (-28.02%)
Mutual labels: algorithm, triangulation
Solid
🎯 A comprehensive gradient-free optimization framework written in Python
Stars: ✭ 546 (+61.06%)
Mutual labels: algorithm, library
Earcut.hpp
Fast, header-only polygon triangulation
Stars: ✭ 447 (+31.86%)
Mutual labels: algorithm, triangulation
Delaunator
An incredibly fast JavaScript library for Delaunay triangulation of 2D points
Stars: ✭ 1,641 (+384.07%)
Mutual labels: algorithm, triangulation
Cdt
C++ library for constrained Delaunay triangulation (CDT)
Stars: ✭ 165 (-51.33%)
Mutual labels: library, triangulation
Cgal
The public CGAL repository, see the README below
Stars: ✭ 2,825 (+733.33%)
Mutual labels: library, triangulation
delaunay-triangulation
Pseudo-code algorithm
Pseudo-code can be found on Wikipedia
function BowyerWatson (pointList)
// pointList is a set of coordinates defining the points to be triangulated
triangulation := empty triangle mesh data structure
add super-triangle to triangulation // must be large enough to completely contain all the points in pointList
for each point in pointList do // add all the points one at a time to the triangulation
badTriangles := empty set
for each triangle in triangulation do // first find all the triangles that are no longer valid due to the insertion
if point is inside circumcircle of triangle
add triangle to badTriangles
polygon := empty set
for each triangle in badTriangles do // find the boundary of the polygonal hole
for each edge in triangle do
if edge is not shared by any other triangles in badTriangles
add edge to polygon
for each triangle in badTriangles do // remove them from the data structure
remove triangle from triangulation
for each edge in polygon do // re-triangulate the polygonal hole
newTri := form a triangle from edge to point
add newTri to triangulation
for each triangle in triangulation // done inserting points, now clean up
if triangle contains a vertex from original super-triangle
remove triangle from triangulation
return triangulation
Sample
From the Wikipedia page of the algorithm
Requirement
Build
meson build
ninja -C build
Note that the project description data, including the texts, logos, images, and/or trademarks,
for each open source project belongs to its rightful owner.
If you wish to add or remove any projects, please contact us at [email protected].