Hello all,
I have been working on a simulation project for a while which involves N colliding balls in a 2D space. What I want to get is the count of the number of balls in each cell every frame and save it to a text file. A ball is said to be in a cell if more than 50% of the area of the ball is within the cell. How do I go about this?
PS: Each ball is an object of a pre defined class.
The correct way to do this is highly depending on your code. Can you share an MCVE sketch?
Ugh. Is this a requirement? Or could a ball be said to be in a cell if its center point is in the cell? This is a really weird definition for a grid of cells – for example, balls at the intersection points of the grid are 25% in each cell, so they are not in any cell!
If you go down this road, you may need to case each ball based on its points of intersection with grid lines, then compute the area of intersection.
The only good news here is that, if I’m understanding your use case right, then you can optimize like this:
hi @harvious,
Adding to Jeremy’s answer (and questions):
If so, spatial hashing could be a solution.
The “giCentre” library has a powerful HashGrid class (see example) but it will return the points within a radius of a specific location (not within a bounding box).
Processing has a HashMap() class (see reference) but I don’t know Java well and can’t tell if you could use it in this case.
You could also try to implement your own class based on the various examples you can find on the web. Here below a simple example sketch in Python mode that just does that:
def setup():
size(800, 400, P3D)
frameRate(1000)
strokeWeight(2)
textSize(9)
smooth(8)
global hmap, cellSize, balls
cellSize = int(width/20)
hmap = Hashmap()
balls = [Ball() for i in xrange(1000)]
def draw():
background('#ffffff')
for b in balls:
b.update()
b.render()
hmap.insert(b.loc)
pushStyle()
strokeWeight(1)
stroke('#ffffff')
for x in xrange(0, width, cellSize):
for y in xrange(0, height, cellSize):
binPts = hmap.query(PVector(x, y))
fill(10 + len(binPts) * 7, 250 - len(binPts) * 3, 255 - len(binPts) * 2, 130)
rect(x, y, cellSize, cellSize)
fill('#0000')
text(len(binPts), x + cellSize * .1, y + cellSize * .9)
popStyle()
hmap.reset()
class Ball(object):
def __init__(self):
self.loc = PVector(random(width), random(height), 0)
self.vel = PVector.random2D()
def update(self):
self.loc.add(self.vel)
if self.loc.x > width or self.loc.x < 0: self.vel.x *= -1
if self.loc.y > height or self.loc.y < 0: self.vel.y *= -1
def render(self):
point(self.loc.x, self.loc.y, self.loc.z)
class Hashmap(object):
def __init__(self):
self.grid = {}
def _key(self, p):
return (int((floor(p.x/cellSize))*cellSize),
int((floor(p.y/cellSize))*cellSize),
int((floor(p.z/cellSize))*cellSize))
def insert(self, p):
if self._key(p) not in self.grid:
self.grid[self._key(p)] = []
self.grid.setdefault(self._key(p), []).append(p)
def query(self, p):
return self.grid.setdefault(self._key(p), [])
def reset(self):
self.grid = {}
For more on the grid based collision system approach with code examples, see:
…and previously https://forum.processing.org/two/discussion/17830/how-do-i-iterate-through-individual-buckets-in-hashmaps
…and also, see this chapter with code examples:
Ch.6 from Nature of Code – in particular section 6.14 “Algorithmic Efficiency (or: Why does my $@(*%! run so slowly?)” The Nature of Code
… noc-examples-processing/chp06_agents/binlatticespatialsubdivision at master · nature-of-code/noc-examples-processing · GitHub
However note that these approaches do not satisfy “A ball is said to be in a cell if more than 50% of the area of the ball is within the cell.”
A comparison between Quadtree and Spatial Hashing using p5.js. Note that for the latter the author used bit-shifting for computational efficiency.
Hello all,
Thank you for all of your replies.
I think I can do away with the 50% radius requirement. I really just need the number of balls in each cell every frame and the cell coordinates ie :
cell [(x,x+a);(y,y+a)] and count, where a is the side length of each square cell. I could just reference each cell by number, but then I have to generate the x,y values manually again anyway; since my ultimate goal is to get the spatial density of the balls for each frame.
I will be trying to implement this to processing as this seems to be the closest to what I need.
Since I am very new to this, I am sure I will muck it up somehow.
Thank you once again for all of your help. I will post here again, if I am stuck with the implementation ( which is inevitable).
You might like to look at https://codepen.io/scudly/pen/pPELKM for an example of a simple 2D gridded collision detector. ‘g’ toggles showing the grid. ‘r’ randomizes the ball locations. Up and down arrows change the ball sizes.
Each ball computes its grid number. Balls are sorted by grid number. Collisions are tested against balls in the same cell, one to the right, and three in the row below. It’s trivial to count the balls in each cell by just running down the list until you hit a ball with the next cell number.