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);
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
