13 replies to this topic

[jmartis]

Hey guys,

What I have...

A 2D ellipse (width, height, centerX, centerY) Let's say 100 width x 70 height at 100x, 200x.
A set amount of points. Let's say 50 points.

What I need...

An array of points based on set amount of points (50) that are all equal distance (equally distributed) from one another and within the area of the ellipse (100x70).

My math is very limited so your help is much appreciated!

[Reedbeta]

To clarify: you want to generate random points that are evenly distributed across the ellipse's area? If so, see Disc Point Picking and then just scale the generated points to cover the ellipse. (An ellipse is just a scaled circle, so this will work.)

[jmartis]

That is precisely what I am looking for (The disc on the right)... although it is above my head how to convert those formulas to working code. I am trying to write this in Actionscript 3. Any help is appreciated!

[Reedbeta]

First, you'll need a way to generate random numbers - this is probably a function built in to Actionscript. Generate one random number between 0 and 1 (this is 'r'), and a second between 0 and 2*pi (this is 'theta'). Then apply formulas (4) and (5) from the page (those are the important part) to get the x and y. Those are coordinates within the unit circle (centered at 0, 0 with a radius of 1). Then you'll need to scale and bias the x and y (multiply and add) to remap them to your desired ellipse.

[jmartis]

Thanks,

I was able to successfully implement the formula, but sadly it is not uniform enough. Just imagine placing pepperonis on a pizza in a uniform fashion, that is the desired outcome I want. Are there any formulas that can give total uniformity across all the points? Thanks

[Reedbeta]

"Not uniform enough" isn't very specific. Can you describe more carefully what you want vs what you're seeing, or post a screenshot illustrating it?

As a guess I'll assume that you are running into "clumpiness", a common problem with random numbers where they tend to gather into clumps that don't look especially uniformly distributed. If you still want to generate random values, you might look into stratified sampling (google for it). Another possibility if you don't have too many points is to check, as you generate each point, whether it's too close to a previously generated point (based on a threshold distance that you choose), and re-generate it if so. This will get very slow if you have many (thousands of) points.

[poita]

Does it need to look random, or do you just need a bunch of distributed points?

If not, just plot them in a hexagonal pattern. That way all the points will be evenly distributed.

[jmartis]

I would love if all the points were equal distance from one another, then I can play around with a little randomness on those points. How does one do a hexagonal layout? Thanks!

[jmartis]

Also,

I am trying to perform the idea of checking distances from points using a threshold. My height, width of the ellipse will vary, as will my # of points. In my testing I get stack overflows when trying different minDistances that the points need to be. Is there some sort of method to calculate my minDistance based on height, width of ellipse and # of points I am trying to return? Thanks!

[poita]

What language are you using?

Here's some (untested) C++ code to arrange them in a triangular pattern:

struct Point
{
	float x, y;
	Point(float x, float y):x(x), y(y) {}
};

std::vector<Point> points;
Point center(0.0f, 0.0f);

Point radii(100.0f, 80.0f);

// Minimum distance between points
float min_dis = 10.0f;

// Distance between 'rows'
float y_dis = min_dis * sqrt(0.75f);

for (float y = center.y - radii.y; y < center.y + radii.y; y += y_dis)
{
	bool offset = false;
	for (float x = center.x - radii.x + (offset ? min_dis * 0.5f : 0.0f);
		x < center.x + radii.x; x += min_dis)
	{
		// Normalize coordinates
		float nx = (x - center.x) / radii.x;
		float ny = (y + center.y) / radii.y;

		// Is it in the ellipse?
		if (nx * nx + ny * ny < 1.0f)
			points.push_back(Point(x, y));
	}
	offset = !offset; // Alternate row x offset.
}

[jmartis]

I am using Actionscript 3. I will try to implement your solution. How might you suggest calculating the Minimum distance between points? This formula has to be totally dynamic, no hard coded variables minus the width, height of the ellipse and the # of points to plot. Thanks!

[jmartis]

I converted your code to working AS3. This is a great start... but I have a certain # of points I wish to return, and this # varies. How could I drive this using a certain # of points I wish returned?

var xNum:Number;

var yNum:Number;

var points:Array = [];

var center:Point = new Point(0, 0);

var radii:Point = new Point(100,80);

var min_dis:Number = 10;

var y_dis:Number = min_dis * Math.sqrt(0.75);



for (yNum = center.y-radii.y; yNum < center.y+radii.y; yNum += y_dis) {

	

	var offset:Boolean = false;

	

	for (xNum=(center.x-radii.x+(offset?min_dis*0.5:0)); xNum<(center.x+radii.x); xNum+=min_dis) {

		var nx:Number = (xNum-center.x) / radii.x;

		var ny:Number = (yNum+center.y) / radii.y;

		if (nx * nx + ny * ny < 1) {

			points.push(new Point(xNum,yNum));

		}

		offset=!offset;

	}

	

}

[poita]

Oh, I didn't see that you needed a set number of points.

Well, the number of points inside is going to be roughly:

n_points = (pi/4) * (2*radii.y)/y_dis * (2*radii.x)/min_dis

Substitute min_dis * sqrt(0.75) in for y_dis and solve for min_dis.

That's just an estimate, so you could just use that and cheat a little by keeping a count and stopping once you've reach the amount. I'll have to think more about how you would do it more precisely.

[jmartis]

Thanks... I might need 60 points, I might need 105, I might need 4...

Also keep in mind those points need to "fill" the area of the ellipse