How to determine which cells in a grid intersect with a given triangle?

Posted by Ray Dey on Game Development See other posts from Game Development or by Ray Dey
Published on 2011-01-24T20:05:57Z Indexed on 2011/01/28 23:39 UTC
Read the original article Hit count: 237

Filed under:

collision-detection

|

intersection

I'm currently writing a 2D AI simulation, but I'm not completely certain how to check whether the position of an agent is within the field of view of another.

Currently, my world partitioning is simple cell-space partitioning (a grid). I want to use a triangle to represent the field of view, but how can I calculate the cells that intersect with the triangle?

Similar to this picture: enter image description here

The red areas are the cells I want to calculate, by checking whether the triangle intersects those cells.

Thanks in advance.

EDIT:

Just to add to the confusion (or perhaps even make it easier). Each cell has a min and max vector where the min is the bottom left corner and the max is the top right corner.

© Game Development or respective owner

Related posts about collision-detection

Collision detection with curves

as seen on Game Development - Search for 'Game Development'
I'm working on a 2D game in which I would like to do collision detection between a moving circle and some kind of static curves (maybe Bezier curves). Currently my game features only straight lines as the static geometry and I'm doing the collision detection by calculating the distance from the circle… >>> More
Need some advice regarding collision detection with the sprite changing its width and height

as seen on Game Development - Search for 'Game Development'
So I'm messing around with collision detection in my tile-based game and everything works fine and dandy using this method. However, now I am trying to implement sprite sheets so my character can have a walking and jumping animation. For one, I'd like to to be able to have each frame of variable… >>> More
Collision Detection - Java - Rectangle

as seen on Stack Overflow - Search for 'Stack Overflow'
I would like to know if this is a good idea that conforms to best practices that does not lead to obscenely confusing code or major performance hit(s): Make my own Collision detection class that extends Rectangle class. Then when instantiating that object doing something such as Collision col =… >>> More
Collision Detection for Actionscript 3

as seen on Stack Overflow - Search for 'Stack Overflow'
Well, I was searching for a simple collision detection function for as3, I found Collision Detection Kit, but it is too complicated, I just want a damn function that I give 2 objects as paramenters and that's it. I would like to know where can I find a pixel-perfect collision detection function (The… >>> More
The Maths for 2D Collision Detection between an OBB and a Circle

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm creating a 2D game and want to test for collision between an OBB (Oriented Bounding Box) and a Circle. I'm unsure of the maths and code to do this. I'm creating the game in c++ and opengl. >>> More

Related posts about intersection

Sphere-Sphere intersection and Circle-Sphere intersection

as seen on Game Development - Search for 'Game Development'
I have code for circle-circle intersection. But I need to expand it to 3-D. How do I calculate: Radius and center of the intersection circle of two spheres Points of the intersection of a sphere and a circle? Given two spheres (sc0,sr0) and (sc1,sr1), I need to calculate a circle of intersection… >>> More
Efficient intersection of two List<String> in Java?

as seen on Stack Overflow - Search for 'Stack Overflow'
Question is simple: I have two List List<String> columnsOld = DBUtils.GetColumns(db, TableName); List<String> columnsNew = DBUtils.GetColumns(db, TableName); And I need to get the intersection of these. Is there a quick way to achieve this? >>> More
fast sphere-grid intersection

as seen on Stack Overflow - Search for 'Stack Overflow'
hi! given a 3D grid, a 3d point as sphere center and a radius, i'd like to quickly calculate all cells contained or intersected by the sphere. Currently i take the the (gridaligned) boundingbox of the sphere and calculate the two cells for the min anx max point of this boundingbox. then, for each… >>> More
Pixel Perfect Collision Detection in Cocos2dx

as seen on Game Development - Search for 'Game Development'
I am trying to port the pixel perfect collision detection in Cocos2d-x the original version was made for Cocos2D and can be found here: http://www.cocos2d-iphone.org/forums/topic/pixel-perfect-collision-detection-using-color-blending/ Here is my code for the Cocos2d-x version bool CollisionDetection::areTheSpritesColliding(cocos2d::CCSprite… >>> More
Triangle - Rectangle Intersection in 2D

as seen on Game Development - Search for 'Game Development'
I had previously asked this for 3D but now I changed my strategy and would like to do the intersection in 2D. The Rectangle is axis aligned and will always be in a fixed position, and has a constant shape and size, basically I want to clip the red areas of the triangles that extend outside the bounds… >>> More