Polylabel Algorithm for Unity

Polylabel.cs

// modified for usage in Unity by grapefrukt, (removed support for polygons with holes as I do not need it)
// based C# port of Polylabel found here: https://github.com/mapbox/polylabel/issues/26#issue-211932869
// which in turn, is based on Polylabel from https://github.com/mapbox/polylabel

// as the name implies this is useful for placing labels on a polygon

using System.Collections.Generic;
using UnityEngine;

namespace Utilities {
	public static class PolyLabel {
		public static Vector2 GetPolyLabel(Vector2[] polygon, float precision = .1f) {
			// calculates the in-center in fixed time for any triangles, it's faster and more accurate 
			if (polygon.Length == 3) return GetInCenter(polygon);

			//Find the bounding box of the outer ring
			float minX = float.MaxValue, minY = float.MaxValue, maxX = float.MinValue, maxY = float.MinValue;

			foreach (var point in polygon) {
				minX = Mathf.Min(minX, point.x);
				maxX = Mathf.Max(maxX, point.x);
				minY = Mathf.Min(minY, point.y);
				maxY = Mathf.Max(maxY, point.y);
			}

			var width    = maxX - minX;
			var height   = maxY - minY;
			var cellSize = Mathf.Max(width, height);
			var halfCell = cellSize / 2;

			//A priority queue of cells in order of their "potential" (max distance to polygon)
			var cellQueue = new CellPriorityQueue();

			if (FloatEquals(cellSize, 0)) return new Vector2(minX, minY);

			var firstCell = new Cell((minX + maxX) / 2, (minY + maxY) / 2, halfCell, polygon);
			cellQueue.Enqueue(firstCell);
			var bestCell = firstCell;

			while (cellQueue.HasItems) {
				//Pick the most promising cell from the queue
				var cell = cellQueue.Dequeue();

				//Update the best cell if we found a better one
				if (cell.D > bestCell.D) {
					bestCell = cell;
				}

				//Do not drill down further if there's no chance of a better solution
				if (cell.Max - bestCell.D <= precision)
					continue;

				//Split the cell into four cells
				halfCell = cell.H / 2;
				cellQueue.Enqueue(new Cell(cell.X - halfCell, cell.Y - halfCell, halfCell, polygon));
				cellQueue.Enqueue(new Cell(cell.X + halfCell, cell.Y - halfCell, halfCell, polygon));
				cellQueue.Enqueue(new Cell(cell.X - halfCell, cell.Y + halfCell, halfCell, polygon));
				cellQueue.Enqueue(new Cell(cell.X + halfCell, cell.Y + halfCell, halfCell, polygon));
			}

			// lastIterationCount = iterationCount;
			return new Vector2(bestCell.X, bestCell.Y);
		}

		static Vector2 GetInCenter(Vector2[] polygon) {
			// Formula to calculate in-center
			var a = Vector2.Distance(polygon[2], polygon[1]);
			var b = Vector2.Distance(polygon[0], polygon[2]);
			var c = Vector2.Distance(polygon[2], polygon[0]);
			var x = (a * polygon[0].x + b * polygon[1].x + c * polygon[2].x) / (a + b + c);
			var y = (a * polygon[0].y + b * polygon[1].y + c * polygon[2].y) / (a + b + c);
			return new Vector2(x, y);
		}

		//Signed distance from point to polygon outline (negative if point is outside)
		public static float PointToPolygonDist(float x, float y, Vector2[] polygon) {
			var inside    = false;
			var minDistSq = float.MaxValue;

			for (int i = 0, len = polygon.Length, j = len - 1; i < len; j = i++) {
				var a = polygon[i];
				var b = polygon[j];

				if (a.y > y != b.y > y && x < (b.x - a.x) * (y - a.y) / (b.y - a.y) + a.x)
					inside = !inside;

				minDistSq = Mathf.Min(minDistSq, GetSegDistSq(x, y, a, b));
			}

			return (inside ? 1 : -1) * Mathf.Sqrt(minDistSq);
		}

		//Get squared distance from a point to a segment
		static float GetSegDistSq(float px, float py, Vector2 a, Vector2 b) {
			var x  = a.x;
			var y  = a.y;
			var dx = b.x - x;
			var dy = b.y - y;

			if (!FloatEquals(dx, 0) || !FloatEquals(dy, 0)) {
				var t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy);
				if (t > 1) {
					x = b.x;
					y = b.y;
				}
				else if (t > 0) {
					x += dx * t;
					y += dy * t;
				}
			}

			dx = px - x;
			dy = py - y;
			return dx * dx + dy * dy;
		}

		static bool FloatEquals(float a, float b) => Mathf.Approximately(a, b);
	}

	internal class Cell {
		public readonly float X;
		public readonly float Y;
		public readonly float H;
		public readonly float D;
		public readonly float Max;
		const           float Sqrt2 = 1.41421356237f;

		public Cell(float x, float y, float h, Vector2[] polygon) {
			X   = x;
			Y   = y;
			H   = h;
			D   = PolyLabel.PointToPolygonDist(X, Y, polygon);
			Max = D + H * Sqrt2;
		}
	}

	internal class CellPriorityQueue {
		readonly SortedList<float, Cell> queue = new();
		public bool HasItems => queue.Count > 0;
		public void Enqueue(Cell cell) => queue.TryAdd(-cell.Max, cell);
		public Cell Dequeue() {
			var c = queue.Values[0];
			queue.RemoveAt(0);
			return c;
		}
	}
}

Hi @grapefrukt, thanks for your code.

How to implement for shape has the hole?

We have GetPolyLabel(Vector2[] polygon) function, but how to add point with polygon has holes?

Have a good day!

@at-minhth I removed support for polygons with holes as it added complexity I didn't need for my specific use case. The sources I used are linked at the top, you may be able to salvage what you need from there. Good luck!

@grapefrukt thanks, I can remake it but I'm not sure about input Vector2[] polygon.
I guess they're vertices of polygon.
How to add it with Polygon has hole?

@at-minhth the code in this comment has support for holes: mapbox/polylabel#26 (comment)

I see that you're in that thread too, so this is the best help I can offer.