Array of points within an ellipse

F0e6dd9a3db23093a35badf8688e3ea9
0
jmartis 101 Nov 18, 2009 at 22:24

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!

13 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Nov 18, 2009 at 22:32

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

F0e6dd9a3db23093a35badf8688e3ea9
0
jmartis 101 Nov 19, 2009 at 03:27

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!

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Nov 19, 2009 at 03:46

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.

F0e6dd9a3db23093a35badf8688e3ea9
0
jmartis 101 Nov 19, 2009 at 16:02

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

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Nov 19, 2009 at 17:43

“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.

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Nov 20, 2009 at 04:53

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.

F0e6dd9a3db23093a35badf8688e3ea9
0
jmartis 101 Nov 20, 2009 at 15:35

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!

F0e6dd9a3db23093a35badf8688e3ea9
0
jmartis 101 Nov 20, 2009 at 16:18

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!

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Nov 21, 2009 at 03:15

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.
}
F0e6dd9a3db23093a35badf8688e3ea9
0
jmartis 101 Dec 01, 2009 at 20:54

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!

F0e6dd9a3db23093a35badf8688e3ea9
0
jmartis 101 Dec 01, 2009 at 21:41

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;
    }
    
}
36b416ed76cbaff49c8f6b7511458883
0
poita 101 Dec 02, 2009 at 11:12

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.

F0e6dd9a3db23093a35badf8688e3ea9
0
jmartis 101 Dec 02, 2009 at 22:19

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