Hello,
I’m trying to get random points inside a hexagon but don’t know how.
At the moment I am just calculating random points inside a square, this is what I have:
I have already found several hints how to do this but I couldn’t really understand…
If someone could tell/show me how to make this calculation inside blueprint I would very much appreciate it.
Thanks a lot!
Hello, GullJemon,
Use polar coordinates. Instead of representing a point with a cartesian coordinate system, you represent it with an angle and a distance from a center point (so a random point inside a sphere is just an angle between 0 and 360, and a distance to the center point, ranged between 0 and the ratio of the sphere). Here is a long explanation on how it could be done.
If you where to check if a known point is inside a sphere, you would be just checking the distance between the center of the sphere and the point you are detecting, and seeing if that is less than the ratio of your sphere, correct?
You can think of your hexagon as having two different ratios: A max one when your angle corresponds to a vertex, and a min one, when your angle corresponds to a midpoint.
Now, you imagine that your center point also has a direction, it is pointing to the front. So you can get the look at rotator needed to look from that direction to your known point, and that in turn gives you the angle at which you are in your hexagon.
You know at what angle you are, so you can use that information to lerp between those two ratios to get your actual limit distance at that angle of the hexagon. Then you just check if the distance to your point is lower than that max distance at angle that you calculated.
On a hexagon, you have a vertex at every 60 degrees or PI/3 radians. If you use the modulo operator with 60 as a second input, you will know where you are inside a segment of 60 degrees where 0 is a vertex, 60 is a vertex and 30 the midpoint. You can go from there to calculate the alpha value needed to lerp between max ratio and min ratio. That would be a method of seeing if a point is inside an hexagon.
To get a random point inside an hexagon, you first get a random angle between 0 and 360, calculate your max distance at angle as described before, and get a random float in range between 0 and your max distance.
That is giving you the polar coordinates for the location of your point. You can use those coordinates to get the cartesian world coordinates that correspond to the random point inside the hexagon that you calculated.
For example, you can create a 3D vector that corresponds to the world coordinates position of your hexagon center. Then you apply a rotator to a second normalized vector, with the random angle that you calculated, and you multiply that normalized vector for a float that would have the random distance in range that you calculated (thus getting a vector that points from the origin of the hexagon to your point). You add your first vector to the second vector and that would give you the 3D location of your randomly generated point.
Hope this helps. All the best.
if y is a random number between
-.866 and +.866
and x is a random number between
-1 and +1
you can check if
abs(x) < 1 - .5( abs(Y)/.866 )
if so, you can mark a point at X and Y.
otherwise, you can discard that point, because its within the bounding rectangle, but outside the hexagon.
so, as the absolute value of Y approaches 0.866, the bounds of the absolute value of X approaches 0.5, and as the absolute value of Y approaches 0, the bounds of the absolute value of X approaches 1, which describes a regular hexagon with a radius of 1. to scale this hexagon, you can just multiply the X and Y results by whatever radius of Hexagon you want to create.
this updated method will produce an even distribution of random points within a regular hexagon, but the total number of points will be randomized based on how many attempted points within the bounding rectangle were discarded because they missed the hexagon.
Thanks a lot… what exactly would you mean with “won’t create a perfect distribution” I’m really looking for true hexagon bounds… If there would be any kind of overlapping I cannot use this method. Since it’s math I feel obligated to find a precise solution, just an approximation wouldn’t suffice.
Smart, and easy to implement. This method would only work for hexagon (not regular polygons with an arbitrary number of corners like the other one) but is much cleaner.
Thanks a lot, I’m very interested here… I’m going to delver into this but an example how I would actually go about this inside the UE4 Blueprint System would be very helpful because I can’t quite yet imagine what you mean…
using polar coordinates with distance lerping between inner and outer radii ( 1 and .866 ) is a good idea, but modulus creates more of a saw tooth wave, when you actually need a triangle wave. otherwise you would make a sawblade shape, instead of a hexagon. to turn a saw tooth wave into a triangle wave, you can subtract half of its amplitude to center it on 0, and take the absolute value to reflect it.
so:
Theta = random number between 1 and 360
Max = ( .866 + ( Abs( ( Abs(Theta) Mod 60 ) - 30 ) / 30 ) * 0.134 ) * HexRadius
Radius = random number between 0 and Max
X = Radius * Cos(Theta)
Y = Radius * Sin(Theta)
then place your points at X and Y, and that location will be a random point that falls within a regular hexagon with a radius the length of HexRadius, with a random distribution that exponentially favors the center.
Here is an example implementation.
It is quite late so I am sure I must have made some silly mistake somewhere and it might not work at the first attempt, but it shows the idea in practice. Hope it is not too badly constructed.
Asume the following default values for variables: Sides = 6, maxRatio = 100, everything else = 0.
If you have any question about the implementation let me know.
Scott’s solution would be much more compact and implies less math, so it’s lighter. If you only care about a hexagon and don’t mind the non-uniform distribution, it will work very well too.
The local coordinate might as well be a 2D vector, wouldn’t matter and would be easier to conceptualize maybe.
Hehehe, I keep missing your replies. Again, smart and clean.
but with this method, each concentric ring would have a similar number of points, but concentric rings closer to the center will have a smaller circumference…
so it will result in an uneven distribution with a bias towards the center.
You are totally right, Scott. To be honest hadn’t think about that.
Think it might be modified to apply the solution described here?
some distributions of random points have a bias, meaning they have a higher density in some areas. in my earlier solution, the points would clump up towards the top and bottom of the hexagon, doubling in density compared to the middle of the hexagon. Diego’s solution would have a bias towards the center, exponentially increasing in density as you approach the center of the hexagon. my updated method will produce an even distribution of points, which has the same density everywhere, as long as the numbers are random.
“just an approximation” is all that is possible, because hexagons inherently have irrational proportions. due to Pythagorean theorem, the proportions of a hexagon involve radical 3, which is an irrational number, meaning it can’t ever be accurately represented using decimal, no matter how many decimal places you use. also, floating point numbers only have so much precision, so you should probably just round half of radical 3 down to .866, and call that close enough.
or you can decide how accurate you want to get, √3 / 2 roughly equals 0.8660254037844386
probably not, because they are using calculus integration to cancel out biased random distributions in a sphere, but your bias is actually a worse case than you would get from attempting this with a perfect circle. the corners of the hexagon are actually causing more of a star shaped exponential bias towards the center in your solution, so canceling that out would be tricky. once you start using absolute value and modulus in your formulas, finding a way to cancel those out would probably get ugly fast, and doing calculus sounds pretty expensive versus my method of finding a random point within a rectangle, and discarding it if its outside the bounds of the hexagon.
Ok, makes sense. Yeah, your updated answer is much better.
So the best solution if the original poster wants a perfectly even distribution would be to get a random point within a rectangle, check if that point is within the bounds of a hexagon (your test is excellent), and if it isn’t, discard it. Repeat until he gets his point, or the number of points he needs.
And it would be much more efficient than doing all the math involved in the other methods (that wouldn’t get a regular distribution anyways), even though he might have to discard x number of random points before getting a valid coordinate. Awesome, Scott, this will prove helpful to me too.
Yes, an even distribution is what I’m looking for, thanks a lot. I’ve now managed to get it to work! Thanks again for your effort!
