Array of points within an ellipse

13 replies to this topic

#1jmartis

New Member

• Members
• 8 posts

Posted 18 November 2009 - 10:24 PM

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!

#2Reedbeta

DevMaster Staff

• 5308 posts
• LocationSanta Clara, CA

Posted 18 November 2009 - 10:32 PM

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.)
reedbeta.com - developer blog, OpenGL demos, and other projects

#3jmartis

New Member

• Members
• 8 posts

Posted 19 November 2009 - 03:27 AM

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!

#4Reedbeta

DevMaster Staff

• 5308 posts
• LocationSanta Clara, CA

Posted 19 November 2009 - 03:46 AM

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.
reedbeta.com - developer blog, OpenGL demos, and other projects

#5jmartis

New Member

• Members
• 8 posts

Posted 19 November 2009 - 04:02 PM

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

#6Reedbeta

DevMaster Staff

• 5308 posts
• LocationSanta Clara, CA

Posted 19 November 2009 - 05:43 PM

"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.
reedbeta.com - developer blog, OpenGL demos, and other projects

#7poita

Senior Member

• Members
• 322 posts

Posted 20 November 2009 - 04:53 AM

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.

#8jmartis

New Member

• Members
• 8 posts

Posted 20 November 2009 - 03:35 PM

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!

#9jmartis

New Member

• Members
• 8 posts

Posted 20 November 2009 - 04:18 PM

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!

#10poita

Senior Member

• Members
• 322 posts

Posted 21 November 2009 - 03:15 AM

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

// 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.
}

#11jmartis

New Member

• Members
• 8 posts

Posted 01 December 2009 - 08:54 PM

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!

#12jmartis

New Member

• Members
• 8 posts

Posted 01 December 2009 - 09:41 PM

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 min_dis:Number = 10;

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

var offset:Boolean = false;

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;

}

}



#13poita

Senior Member

• Members
• 322 posts

Posted 02 December 2009 - 11:12 AM

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

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

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.

#14jmartis

New Member

• Members
• 8 posts

Posted 02 December 2009 - 10:19 PM

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

1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users