5 ms·
Ah. I still remember my computational geometry professor telling us about an algorithm to do triangulation (composing a polygon into triangles) in linear time:
by gmoot 7y ago
Ah. I still remember my computational geometry professor telling us about an algorithm to do triangulation (composing a polygon into triangles) in linear time: "It's very complex. I don't think anyone has actually implemented it".
It shocked me at the time that there were algorithms like this.
https://en.wikipedia.org/wiki/Polygon_triangulation#Computational_complexity https://en.wikipedia.org/wiki/Polygon_triangulation#Computat...
- alanbernstein 7y agoWhat was shocking about this? Seems like something you could always solve by hand, even if you couldn't quite enumerate the steps you need to take to do it. I guess that's sort of my baseline for whether I expect an algorithm to exist.
- mfabbri77 7y agoFast and robust polygon triangulation was the hardest challenge in the period when we developed the OpenGL version of our 2D vector graphics engine (www.amanithvg.com), it was in the early 2000. I clearly remember all such research papers. After studying all of them and after three complete rewrite of the engine, we finally implemented a classic 2 step algo: sweepline polygon decomposition to monotone polygons, and then monotone polygons to triangles. We had really heavy headaches dealing with intersections, autointersections, splitting edges, comparing and merging original vertexes with vertexes created by splitting edges, managing edges connectivity and topology. After some try, we totally discarded the idea to write it in floating point arithmetic, preferring fixed point integers instead (and this was a real turning point for the robustness!). Anyway, good times to remember!
- carlmr 7y agoThey mention O(n log* n) being quasi linear time, I had to look up log * n because I never saw this before.
- pfdietz 7y agoAnd then there's O(n alpha(n)), where alpha(n) is an inverse the Ackermann function, and which grows even more slowly than log* n. The famous union-find algorithm has this complexity.
- MaxBarraclough 7y agoWikipedia link: https://en.wikipedia.org/wiki/Log-star https://en.wikipedia.org/wiki/Log-star
- IshKebab 7y agoYeah I discovered a fast algorithm for the travelling salesman problem with neighbourhoods (i.e. cities are shapes not points). Emailed the author to inquire about code, turns out they never wrote any.