poly2tri library to Lua (math for 2d navmesh)

[Tanner]

Please, if not too much trouble, could you download here(on this forum topic) the binary library files to link with Lua for Windows(32 and 64 bit versions).
It would save a lot of time for me in future, in develop my Navmesh library. Because I'm a noob in C and C++.

Yep, binaries are on the releases page: https://github.com/TannerRogalsky/lua-poly2tri/releases

[AntonioModer]

Yep, binaries are on the releases page: https://github.com/TannerRogalsky/lua-poly2tri/releases

Cool, thanks. I was do a simple test, it work.

[alundaio]

Some reason I crash *rarely* using those poly2tri dlls, not sure why.

I needed an easy way to do simple delauney triangulation and everything I have found has been overly convoluted for my needs (additions of many classes or dependencies on other libraries or dozens of extra methods I don't need). I really did not like Yonaba's script, just looking at it I can tell it's slow, so I wrote a single function based on: http://paulbourke.net/papers/triangulate/morten.html


Here is my script: http://pastebin.com/4b6pAVJY


Example:

Code: Select all

function love.draw()
	local polys = { {100,100}, {200,200}, {300,300}, {400, 100}, {300, 200} }

	local triangles = math.DelauneyTriangulate(polys)
	love.graphics.print(strformat("triangles=%s",#triangles),5,0)
	love.graphics.print(strformat("vertices=%s",#polys),5,15)
	if (triangles) then 
		for i,tri in ipairs(triangles) do
			love.graphics.polygon( "line", polys[ tri[1] ][1],polys[ tri[1] ][2], polys[ tri[2] ][1],polys[ tri[2] ][2], polys[ tri[3] ][1],polys[ tri[3] ][2])
		end
	end
end

Implementation:


I just needed something to create a simple mesh between 'cells' on a grid.

[Tanner]

Some reason I crash *rarely* using those poly2tri dlls, not sure why.

Unfortunately, if you don't satisfy the constraints that poly2tri has (no same points, no self-intersection, no holes touching other holes or the countour) then it's method of letting you know that is to segfault (at least on OSX). I'm working on a separate library to help with sanitizing data before it's passed to poly2tri and I will post it here when it's done.

You might just be looking for https://love2d.org/wiki/love.math.triangulate, though. It's fast and good for simple cases. I believe it uses Kong's algorithm. http://www.sunshine2k.de/coding/java/Po ... /Kong.html

[ivan]

Kong's algorithm uses earclipping (as well as love.math.triangulate) so neither of these will output constrained Delaunay triangulations of which alundaio is eluding. Poly2Tri is fast but I don't believe it supports constrained Delaunay triangulation (at least it didn't a while ago, not sure about the more recent versions).
"self-intersection, no holes touching other holes or the countour" - polygon union/difference/offsetting are handled by the "Polygon Clipper" library or "GPC".
Again, you rarely need these features in 2D games.
If you clean up the input then love.math.triangulate should be sufficient 99% of time.

[Tanner]

Poly2Tri is fast but I don't believe it supports constrained Delaunay triangulation (at least it didn't a while ago, not sure about the more recent versions).

It does. At least the version that I've wrapped does.

"self-intersection, no holes touching other holes or the countour" - polygon union/difference/offsetting are handled by the "Polygon Clipper" library or "GPC".

I allude to that in the readme for my wrapper. The approach I'm using for sanitizing the data is to union the holes with NonZero winding along with some other robustness tweaks. Clipper already has a nice FFI-powered wrapper: https://luapower.com/clipper

[ivan]

Tanner, I was looking over the benchmarks on your Github page:
Roland's triangulation lib is designed for convex polygons,
so a heads up - the output is not comparable to the other benchmarks you have listed on there.

Good job on the wrapper (I know it's a lot of work),
but honestly I have more love for the pure Lua implementations,
vrld has a good code example in his HC (under "polygon.lua").

[alundaio]

Some reason I crash *rarely* using those poly2tri dlls, not sure why.

Unfortunately, if you don't satisfy the constraints that poly2tri has (no same points, no self-intersection, no holes touching other holes or the countour) then it's method of letting you know that is to segfault (at least on OSX). I'm working on a separate library to help with sanitizing data before it's passed to poly2tri and I will post it here when it's done.

You might just be looking for https://love2d.org/wiki/love.math.triangulate, though. It's fast and good for simple cases. I believe it uses Kong's algorithm. http://www.sunshine2k.de/coding/java/Po ... /Kong.html

love.math.triangulate didn't solve my needs as it was creating overlapping edges. Poly2Tri had the results I was looking for, but I can't control the order the vertices I input to make sure I satisfy the constraints since I'm making a procedurally generated graph. The delaunay algorithm I'm using now works perfectly, though. I just needed nice non-overlapping edges so that I can calculate the adjacent neighbors for each 'room cell' in my picture. But thanks.

This is what I wanted to achieve: