Random point between multiple polygons

Godot Version

4.3 b2

Question

Mornin’ fellow godooters!

Looking to figure out if there’s a way to get a random point in multiple unconnected polygons taking into account their sizes.

I got this off of reddit and it works well for a single polygon but I’d like to have maps with multiple spawn areas of differing sizes, which means it should not be 50/50 spawn rate between a larger and smaller area~

static func get_rand_in_polygon( polygon: PackedVector2Array ) -> Vector2:
	var _polygon = polygon
	
	var _triangles = Geometry2D.triangulate_polygon(_polygon)
	var _cumulated_triangle_areas: Array
	var _rand = RandomNumberGenerator.new()
	var triangle_count: int = _triangles.size() / 3
	
	assert(triangle_count > 0)
	_cumulated_triangle_areas.resize(triangle_count)
	_cumulated_triangle_areas[-1] = 0
	for i in range(triangle_count):
		var a: Vector2 = _polygon[_triangles[3 * i + 0]]
		var b: Vector2 = _polygon[_triangles[3 * i + 1]]
		var c: Vector2 = _polygon[_triangles[3 * i + 2]]
		_cumulated_triangle_areas[i] = _cumulated_triangle_areas[i - 1] + triangle_area(a, b, c)
	
	var total_area: float = _cumulated_triangle_areas[-1]
	var choosen_triangle_index: int = _cumulated_triangle_areas.bsearch(_rand.randf() * total_area)
	var a: Vector2 = _polygon[_triangles[3 * choosen_triangle_index + 0]]
	var b: Vector2 = _polygon[_triangles[3 * choosen_triangle_index + 1]]
	var c: Vector2 = _polygon[_triangles[3 * choosen_triangle_index + 2]]
	return random_triangle_point(a, b, c)


static func triangle_area(a: Vector2, b: Vector2, c: Vector2) -> float:
	return 0.5 * abs((c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y))

static func random_triangle_point(a: Vector2, b: Vector2, c: Vector2) -> Vector2:
	return a + sqrt(randf()) * (-a + b + randf() * (c - b))

Hi,
Can your polygon overlap or not ?
in each case, you can create a bounding box around all you polygon, then generate a point in this rectangle and test if it belongs to one of your polygon. If not, just regenerate until you get one. If your bounding box is filled enough by your polygon, it will not take to many attempts and you get a probability link to the surface of all your polygon

No I did mention they would be specifically unconnected polygons!

They could be polygons across the map from one another like this so this method would unfortunately not work for me as it would be a low chance to pick inside a polygon (Image purely as an example).

P.s. I’m using polygons not a collection of tiles in an array because some of the arrays were huge.

I made this 3 other function but not tested (this can be improved by storing polygon area instead of recalculate each time).

Add function
static func get_rand_in_polygons(polygons : Array[PackedVector2Array]) -> Vector2:
	var polygon = get_rand_polygon(polygons)
	return get_rand_in_polygon(polygon)

static func get_rand_polygon(polygons : Array[PackedVector2Array]) -> PackedVector2Array:

	# This part can be done once and stored
	var total = 0
	var area_list = []
	for poly in polygons:
		var area = get_area(poly)
		total += area
		area_list.append(area)
	#######
	
	var value = randf() * total;

	var trunk_sum = 0
	for i in range(area_list.size()):
		trunk_sum += area_list[i]
		if (value <= trunk_sum):
			return polygons[i]
	
	return polygons.back()

static func get_area(polygon: PackedVector2Array) -> float:
	var total = 0
	for i in range(polygon.size()):
		var addX = polygon[i].x
		var id = i + 1
		if (i == polygon.size() - 1): 
			id = 0
		var addY = polygon[id].y
		var subX = polygon[id].x
		var subY = polygon[i].y
		total += (addX * addY * 0.5) - (subX * subY * 0.5);
	return abs(total);

I used this algorithme for area calculation :

This works thank-you so much! I’ll take it and optimize it a bit more with your suggestion of storing the polygon areas~ Sometimes I just look at math things and totally blank, so this was super duper helpful <3

1 Like