❔ ✅The largest inscribed circle inside concave (non-convex) polygon 2D
Hey, I want to make an algorithm that will return the largest inscribed circle in any 2D polygon (or the furthest point from any edge). I want this because I need to place a label in the best spot inside that shape. Do you have any ideas on how can I achieve it in c#?
18 Replies
I don't know if there's an efficient algorithm, but you could place some points in a grid or randomly, then select the region with the best result, and repeat for those regions, a couple of times
Stack Overflow
Largest circle inside a non-convex polygon
How can I find the largest circle that can fit inside a concave polygon?
A brute force algorithm is OK as long as it can handle polygons with ~50 vertices in real-time.
some googling later gives a better solution
Thanks! There is a repo which tried to convert the original poly label.js into C# but unfortunately it has some forbidden library requiremnt
I'm pretty sure I need to use verenoi diagram fro this but not so sure how to do it 😆
what does that mean
voronoi*
Verenoi diagram*
no, it's voronoi
not verenoi
Oh, sorry xD I write it early in the morning and I didn't mind to correct you!
Yeah, it's voronoi for sure
https://github.com/mapbox/polylabel/issues/26 I'm trying to implement this poly label in c# but with no luck.. unfortunately
GitHub
Here is a C# implementation · Issue #26 · mapbox/polylabel
Using the PriorityQueue implementation from BlackWasp: using System; using System.Collections.Generic; using PriorityQueue; namespace SkiaDemo1 { public class PolyLabel { private const float EPSILO...
why no luck
you have references
you even have a complete c# impl
they all have their own implementation of queue and as I'm testing these neither of them yield promising result tbh. The last one created via Unity has a memory leak
It doesn't work for simple shape like this:
And concave polygons are way more complex to compute
in c# SortedSet is the standard library priority queue impl
Thanks, I manage to find a way to do this! I lost my internet connection on PC so here is an phone image of the result
Was this issue resolved? If so, run
/close - otherwise I will mark this as stale and this post will be archived until there is new activity.