Find optimal placement for label/sticker on a simple polygon with holes

Question

I'm working on a real-time archviz renderer and I need to place a label/sticker/decal on walls, which have openings. So one way to think about this is a simple (possibly concave) polygon with holes. So there are two things I need: optimal position, maximum fitting size.

After some research I came to conclusion that I need a solution for maximum inscribed circle in a simple polygon. That will provide both the position and radius.

https://www.sthu.org/blog/14-skeleton-offset-topology/index.html

And couple of other questions, most answered by Stefan Huber, apparently The Authority nowadays regarding this problem. I'm time constrained and looking for plugin solution. So it's either commercial solutions (*Vroni) or CGAL that can at least help me construct straight skeleton. However my environment is JVM, not C++ (yes, I can go the FFI way using JNA).

Can you think of any other solution that I could use to position/scale the labels?

Answer 1

voronoi diagrams are pretty cool tools.

since you are searching for the largest circles available and you (judging by you posting an article about voronoi diagrams) are able to use a voronoi diagram of your surface. let's consider a few key facts about circles and voronoi diagrams.

a circle has a center equidistant from all its edges. a voronoi diagram contains polyons where in all points are closer to a single center point than to any other.

these aren't quite the same, but they are similar.

let's also consider that little piece of information i was taught back in middle school. the most optimized amount of space you can get out of an area by perimeter length is a circle

while i can't give you a proof for it, i believe we can predict a statistical tendency of larger area polygons in a voronoi diagram to also have a tendency towards larger circular inscriptions.

using this idea you can write a highly optimized algorithm to start searching the voronoi diagram for large circular inscriptions starting from the largest polygons in the diagram. i dare say you could write an algorithm not only good enough for one time calculation, but an algorithm good enough for 60fps realtime calculation every frame. mainly because voronoi is absolutely ripe for parallelization.

A truly mathematical solution may be more desired, but you asked for other solutions and i believe this is a very practical approach.

if you are looking for information on making voronoi diagrams(and finding their polygon's area) fast, and they can be lightning fast, then i suggest this article.

http://rykap.com/graphics/skew/2016/02/25/voronoi-diagrams/