javascript python java c# php android html jquery c++ css ios mysql sql r node.js arrays reactjs c asp.net json ruby-on-rails .net sql-server swift python-3.x objective-c django angular angularjs excel regex pandas ruby iphone ajax linux xml vba asp.net-mvc spring laravel database wordpress typescript string wpf mongodb windows xcode postgresql bash oracle git vb.net amazon-web-services multithreading list firebase flutter eclipse spring-boot dataframe azure react-native algorithm docker macos forms image visual-studio scala powershell function twitter-bootstrap numpy api performance selenium winforms python-2.7 matlab vue.js sqlite apache hibernate entity-framework loops rest shell facebook express android-studio csv linq maven qt swing unit-testing file tensorflow

[ACCEPTED]-Delaunay triangulating the 2d polygon with holes-medial-axis

Accepted answer
Score: 11

It sounds like you want constrained Delaunay triangulation. The "holes" can 3 be implemented by constraining input edges 2 to remain unbroken in the triangulation.

See 1 the Triangle and poly2tri projects for implementations.

Score: 4

Here's one of the methods I came up with 4 when doing navmesh for an RTS game. Note 3 that it is homebrew, no third-party tools 2 were used, it took me about 3 weeks to implement 1 and bugfix:

  1. Feed all points into Delaunay triangulation (to get most uniform triangles)
  2. Check along holes outlines and flip polygon pairs produced by Delaunay to match outlines
  3. Clip holes innards

Result (plz ignore purple outlines):

enter image description here

Source: stackoverflow.com

More Related questions

Python: Calculate Voronoi Tesselation from Scipy's Delaunay Triangulation in 3D

How to find all neighbors of a given point in a delaunay triangulation using scipy.spatial.Delaunay?

Efficient Delaunay triangulation

Elegant/Clean (special case) Straight-line Grid Traversal Algorithm?

Determine winding of a 2D triangles after triangulation

Packing different sized circles into rectangle - d3.js

reference algorithm for weighted voronoi diagrams?

Cheap algorithm to find measure of angle between vectors

Find all integer coordinates in a given radius

Dispersing n points uniformly on a sphere