3 ms·
Get the depth (distance from edge to deepest point) of an irregular polygon. At first I was doing all kinds of crazy geometry and the future looked bleak. Then
by swayvil 12y ago
Get the depth (distance from edge to deepest point) of an irregular polygon. At first I was doing all kinds of crazy geometry and the future looked bleak. Then I was "fuck it" and did a randomsample, reduce, randomsample, reduce thing. It's fast and precise.
- timdumol 12y agoIn case you're still interested in an exact solution, I think computing the Voronoi diagram for the polygon (treating each vertex as a point) should help in finding the answer. The deepest point should lie on one of the edges of the Voronoi diagram.
- lifeformed 12y agoI had a similar experience. I was writing a polygon intersection algorithm, heavily optimized for the domain of inputs, but kept having issues when vertices were coincident or when edges were colinear. I spent days trying to fix it, until I decided to just truncate the vertex values to some good-enough level of precision, and add a random unique jitter to each value (past the truncated precision). This made sure that there were never coincident or colinear situations. Then I just truncated the resulting intersection points again to remove the jitter. It was trivial to add, and it was faster than all the extra checks I'd have to do for the edge cases. Also, it gave me peace of mind, since I knew it worked in theory, instead of my other feeble attempts which worked most of the time, but always failed in some new edge case.