I’m working on floor placement that works via triangulation. We are using an implementation of the ear clipping algorithm but I’m debating a second implementation for specifically convex polygons due to how cheap it is (it’s just drawing an edge between vertex 1 to every other edge except for the previous and next vertex) versus our ear clipping algorithm which is done in O(n3) time if I counted correctly.
So I’m wondering if anyone has any insight on whether or not it’s worth switching between the 2 dynamically because of the performance benefits? It will take up more memory because it’s a whole other function, and I need to initially iterate over all the points to determine that the polygon has no concave vertices and to determine winding order. However if the polygon is convex, it will also take much less time to triangulate than using ear clipping.
It’s an easily implemented triangulation algorithm that provides high-quality triangulations that also works with concave polygons by repeatedly cutting off ear tips until only 3 vertices remain.
I could benchmark them but I’m sure that convex polygon triangulation would take less time. I’m just concerned for the memory aspect
Consider if you even care. Is your current approach fast enough? Then any work spent optimizing further is wasted. If you’re not calling it at least once every frame then I doubt it.
Consider if it’s an option to spread the calculation out over several frames.
If you really need to optimize, just try it and see if it works.
It’s not impossible to give pointers to actually answer your question, but really it depends on your exact use case.
Haven’t tested it super extensively. Then again worst case scenario, if our implementation isn’t fast enough, there is a portion in that above paper I can use to bump it down to O(n2). 3 seems to be fast enough (for now) though, and the option to spread it out over frames is also plausible. I’ll try it out with very complex convex polygons and see how performance is but that also makes me think that if a complex convex polygon is too slow, a complex concave one would be as well so it probably isn’t worth it.