search

iShapeUnity / Triangulation

Complex polygon triangulation. A fast O(n*log(n)) algorithm based on "Triangulation of monotone polygons". The result can be represented as a Delaunay triangulation.
MIT License
22 stars 3 forks source link

Add references to articles of algorithms used #1

Closed martinmaxk closed 3 years ago

martinmaxk commented 3 years ago

It is stated this implementation is based on "Triangulation of monotone polygons", but I was unable to find an article of that name and also there must be an extra step before this of converting polygons to monotone pieces.

What algorithm is used in TriangulationExt.cs?

NailxSharipov commented 3 years ago

It's very common implementation. You can look on it in wiki or the first link in google give me a nice pdf article.

First step is break your path into this monotone-polygons that was iShape.Triangulation.Shape.LayoutExt.public static MonotoneLayout Split(this PlainShape shape, long maxEdge, NativeArray extraPoints, Allocator allocator) do!

about TriangulationExt public static NativeArray Triangulate(this PlainShape shape, NativeArray extraPoints, Allocator allocator) exactly implement monotone algorithm first raw: var layout = shape.Split(0, extraPoints, Allocator.Temp); - break a path into monotone layout and after triangulate its