[SOLVED] Formula: Find grid points within an Ellipse.

[ClassyGoat]

Hello!
So I'm trying to write a formula to find all the squares on a grid system that are within a defined ellipse shape. Attached is an image showing an example of this: The blue squares represent all the squares that are fully within the ellipse.

I've got one that works for perfect circles, which is:

cell_size = 24; // Each square is 24 x 24 pixels.
var _radius = 6; // Change be changed to anything
{
  for (var _y = -_radius; _y <= _radius; _y++)
    for (var _x = -_radius; _x <= _radius; _x++)
      if ((_x * _x) + (_y * _y) <= (_radius * _radius)){
       draw_sprite( spr_square, 0, _x * cell_size, _y * cell_size ); // Draws "spr_square" at every square within circle.
        }
}

But I need to be able to do this with an ellipse where the major and minor axis are different sizes.

I did find this online, which might do what I want, but I'm having a hard time converting the code to GML: http://people.sc.fsu.edu/~jburkardt/cpp_src/ellipse_grid/ellipse_grid.html

Any and all help with this would be greatly appreciated!

 

[Cameron]

I'm on my phone so can't provide great detail but there is a collision_ellipse function you could use to get the job done. Place the ellips center at the grid center and test the inside bounding box of the grid boxes against the function. Use draw ellipse function with identical ellipse data to make sure your dimension and placement are correct.

Edit: based on the image provided you would actually want to use outside bounding box as opposed to inside bounding box.

 

[ClassyGoat]

I looked into the collision_ellipse function a little bit and it checks for collisions with objects. So I'd have to create a temporary object at every cell in the grid, then tests for collisions, then delete all those objects. I've got grid sizes of up to 100 x 100, that's 10,000 objects created and deleted, or that have to sit there in the memory. This could work, but I think there should be a much more performance friendly way to do it that doesn't require collision checking.

It doesn't really matter to me whether or not the results give inside or outside the bounding box.

 

[samspade]

Hello!
So I'm trying to write a formula to find all the squares on a grid system that are within a defined ellipse shape. Attached is an image showing an example of this: The blue squares represent all the squares that are fully within the ellipse.

I've got one that works for perfect circles, which is:

cell_size = 24; // Each square is 24 x 24 pixels.
var _radius = 6; // Change be changed to anything
{
  for (var _y = -_radius; _y <= _radius; _y++)
    for (var _x = -_radius; _x <= _radius; _x++)
      if ((_x * _x) + (_y * _y) <= (_radius * _radius)){
       draw_sprite( spr_square, 0, _x * cell_size, _y * cell_size ); // Draws "spr_square" at every square within circle.
        }
}

But I need to be able to do this with an ellipse where the major and minor axis are different sizes.

I did find this online, which might do what I want, but I'm having a hard time converting the code to GML: http://people.sc.fsu.edu/~jburkardt/cpp_src/ellipse_grid/ellipse_grid.html

Any and all help with this would be greatly appreciated!

This post might help. I eventually figure it out for a circle, but finding for a circle and an ellipse is basically the same. You just have to look up that formula instead. So instead of using point_distance you would write your own script for calculating distance in an oval.

https://forum.yoyogames.com/index.p...n-a-circular-patter-solved.53560/#post-326440

primary code from post:

/// @description Add values to a Grid in a Disc Shape
/// @param grid
/// @param grid_x
/// @param grid_y
/// @param range
/// @param max
/// @param min

var _grid, _grid_x, _grid_y, _range, _max, _min;
_grid = argument0;
_grid_x = argument1;
_grid_y = argument2;
_range = argument3;
_max = argument4;
_min = argument5;

for (var i = -_range; i <= _range; i += 1) {
   for (var j = -_range; j <= _range; j += 1) {
   
       if (_grid_x + i < 0) || (_grid_x + i >= array_height_2d(_grid)) ||
          (_grid_y + j < 0) || (_grid_y + j >= array_length_2d(_grid, 0)) {
           continue;
          }

       var _dist = point_distance(0, 0, i, j);       
       if (_dist <= _range) {
           _grid[_grid_x + i, _grid_y + j] += floor(scr_map(_dist, _range, 0, _min, _max));
       }

   }
}

return _grid;

 

[Cameron]

I looked into the collision_ellipse function a little bit and it checks for collisions with objects. So I'd have to create a temporary object at every cell in the grid, then tests for collisions, then delete all those objects. I've got grid sizes of up to 100 x 100, that's 10,000 objects created and deleted, or that have to sit there in the memory. This could work, but I think there should be a much more performance friendly way to do it that doesn't require collision checking.

It doesn't really matter to me whether or not the results give inside or outside the bounding box.

I was on my phone so I was just going off memory and didn't remember that. That beind said, you could still manage it with a single object and just move the coordinates of the object to the cell you wanted to check. Just call it obj_collision_checker or something.

 

[ClassyGoat]

Alright, I found the simple solution I was looking for:

I have a script that tests if a given point is within a given ellipse:

/// @description Check if the given point is within an ellipse
/// @param x point to test
/// @param y point to test
/// @param width of ellipse
/// @param height of ellipse
/// @param x origin of ellipse
/// @param y origin of ellipse

if ( (sqr(argument4 - argument0) / sqr(argument2)) + (sqr(argument5 - argument1) / sqr(argument3)) <= 1 )
    {return true; } // Point is within the ellipse
    else { return false; } // Point is not within the ellipse.

So I just use a for loop to check every cell in my grid.

Thanks everyone for your help!

 

[samspade]

Alright, I found the simple solution I was looking for:

I have a script that tests if a given point is within a given ellipse:

/// @description Check if the given point is within an ellipse
/// @param x point to test
/// @param y point to test
/// @param width of ellipse
/// @param height of ellipse
/// @param x origin of ellipse
/// @param y origin of ellipse

if ( (sqr(argument4 - argument0) / sqr(argument2)) + (sqr(argument5 - argument1) / sqr(argument3)) <= 1 )
    {return true; } // Point is within the ellipse
    else { return false; } // Point is not within the ellipse.

So I just use a for loop to check every cell in my grid.

Thanks everyone for your help!

You might have already figured this out, but since an ellipse is always completely within a rectangle of the same width and height, you don't need to check the ellipse formula for every cell in the grid, and probably shouldn't if the grid is very large. Instead, you can do a simple rectangle check, which is much less computation to see if it is even possible for the ellipse test to return true, and only if so, do the ellipse test. You could basically use the code I posted but add another variable for width (and change range to height or vice versa).

But this only matters if you're grid is very large or you're doing it multiple times per step or something.

 

[ClassyGoat]

I hadn't thought of that, samspade. But that's a really good point. Thanks!