2
votes
3answers
310 views

Polygonal Triangulation - algorithm with O(n log n) complexity

I wish to triangulate a polygon I only have the outline of (p0, p1, p2 ... pn) like described in this question: polygon triangulation algorithm and this webpage: ...
4
votes
1answer
234 views

Create shape from points / lines in editor and mathematically calculate nearest points within shape

If I want an editor that accepts "points" of a minimum of three (a triangle) and I just add some points first, like this: how can I mathematically connect these corners (points) into an object of ...
2
votes
1answer
291 views

Dynamically creating astar node map by triangular polygonal map

My game's map format uses a bunch of triangles to make up the platforms and terrain in 2d. Right now I can set up a 2d array of nodes for the astar algorithm that basically is a bunch of rectangles ...
10
votes
1answer
1k views

Triangulation A* (TA*) pathfinding algorithm

I need help understanding the Triangle A* (TA*) algorithm that is described by Demyen in his paper Efficient Triangulation-Based Pathfinding, on pages 76-81. He describes how to adapt the regular A* ...