# Get counts from each cell in cavas in Processing

**URL:** <https://discourse.processing.org/t/get-counts-from-each-cell-in-cavas-in-processing/8238>\
**Category:** Coding Questions\
**Created:** [February 9, 2019, 6:24am UTC](https://discourse.processing.org/t/get-counts-from-each-cell-in-cavas-in-processing/8238 "2019-02-09T06:24:30Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![harvious](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/harvious/32/3610_2.png) [@harvious](https://discourse.processing.org/u/harvious)\
**Post date:** [February 9, 2019, 6:24am UTC](https://discourse.processing.org/t/get-counts-from-each-cell-in-cavas-in-processing/8238/1 "2019-02-09T06:24:30Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [February 11, 2019, 7:26pm UTC](https://discourse.processing.org/t/get-counts-from-each-cell-in-cavas-in-processing/8238/2 "2019-02-11T19:26:21Z")

</div>

- Is a cell an object?
- Do balls have their current cell as a property?
- Do cells have their current ball as a property?

The correct way to do this is highly depending on your code. Can you share an MCVE sketch?

> [@harvious](#):
>
> A ball is said to be in a cell if more than 50% of the area of the ball is within the cell.

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:

- do point/rect collision detection (center of ball) [Collision Detection](http://www.jeffreythompson.org/collision-detection/point-rect.php)
  - for the balls with points colliding with a rect, they might be “inside”:
    - do line/circle collision detection using each cell edges: [Collision Detection](http://www.jeffreythompson.org/collision-detection/line-circle.php)
      - if no points found, the ball is fully inside the cell
      - if one point found, it is inside
      - if points found, you have a ball with its center point in the cell, but overlapping one or more edges – it might or might not be 50% inside. Welcome to a pile of slow math: you need to find the correct case based on the intersection points and then compute the area of overlap based on that case to measure weather it is over 50%  
– see [java - Area of intersection between circle and rectangle - Stack Overflow](https://stackoverflow.com/questions/622287/area-of-intersection-between-circle-and-rectangle)

---

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [February 13, 2019, 1:32am UTC](https://discourse.processing.org/t/get-counts-from-each-cell-in-cavas-in-processing/8238/3 "2019-02-13T01:32:58Z")

</div>

hi @harvious,

Adding to Jeremy’s answer (and questions):

- Do the balls are objects of similar sizes ?

If so, [spatial hashing](https://www.google.com/search?client=firefox-b-d&ei=mWVjXKSJBM-6a96tv-AK&q=spatial+hash&oq=spatial+hash&gs_l=psy-ab.3..35i39l2j0i20i263j0l5j0i67j0.2616.2941..3312...0.0..0.105.264.2j1......0....1..gws-wiz.......0i71j0i22i30.UQtYJXZXE14) could be a solution.

The “giCentre” library has a powerful `HashGrid` class (see [example](https://www.gicentre.net/utils/hashgrid/)) 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](https://processing.org/reference/HashMap.html)) 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:

 ![30](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/7/774d089aa438684ddb6028f3f00f865845357f89.png)  
_5000 points bouncing in a 2D space ([GIF](https://media.giphy.com/media/jTUVBBp37duWvdhN4H/giphy.gif))_

> **Script**
>
> ```auto
> 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 = {}
> 
> ```

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [February 15, 2019, 6:06am UTC](https://discourse.processing.org/t/get-counts-from-each-cell-in-cavas-in-processing/8238/4 "2019-02-15T06:06:32Z")

</div>

For more on the grid based collision system approach with code examples, see:

> [@Implementing Grid-Based Collision System](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/5):
>
> The link below is for a Processing sketch I created which uses a quadtree data structure and allows the user to change the ball (moving object) size and configure some of the quadtree factors. You might like to try it. [QuadTreeDemo](http://lagers.org.uk/zzz/QuadtreeDemo-180904.zip) It requires the G4P library to be installed, can be done through the Contributions Manager [10]

…and previously [https://forum.processing.org/two/discussion/17830/how-do-i-iterate-through-individual-buckets-in-hashmaps](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](https://natureofcode.com/book/chapter-6-autonomous-agents/)  
… [noc-examples-processing/chp06\_agents/binlatticespatialsubdivision at master · nature-of-code/noc-examples-processing · GitHub](https://github.com/nature-of-code/noc-examples-processing/tree/master/chp06_agents/binlatticespatialsubdivision)

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

---

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [February 15, 2019, 9:45am UTC](https://discourse.processing.org/t/get-counts-from-each-cell-in-cavas-in-processing/8238/5 "2019-02-15T09:45:07Z")

</div>

A [comparison](http://zufallsgenerator.github.io/2014/01/26/visually-comparing-algorithms/) between Quadtree and Spatial Hashing using p5.js. Note that for the latter the author used bit-shifting for computational efficiency.

---

<div class="post-metadata">

**Author:** ![harvious](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/harvious/32/3610_2.png) [@harvious](https://discourse.processing.org/u/harvious)\
**Post date:** [February 15, 2019, 3:17pm UTC](https://discourse.processing.org/t/get-counts-from-each-cell-in-cavas-in-processing/8238/6 "2019-02-15T15:17:30Z")

</div>

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.

> [@solub](#):
>
> 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:

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

😄

---

<div class="post-metadata">

**Author:** ![scudly](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/scudly/32/5597_2.png) [@scudly](https://discourse.processing.org/u/scudly)\
**Post date:** [February 15, 2019, 6:10pm UTC](https://discourse.processing.org/t/get-counts-from-each-cell-in-cavas-in-processing/8238/7 "2019-02-15T18:10:52Z")

</div>

You might like to look at [https://codepen.io/scudly/pen/pPELKM](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.