Stack Overflow
Stack Overflow

Questions tagged [collision-detection]

Collision detection is the problem of determining if geometric objects intersect. It is an important topic in computer graphics, in CAD/CAM, in dynamical simulation, and in computer games.

References

Related tags

4424 questions
601
votes
42 answers

How can I determine whether a 2D Point is within a Polygon?

I'm trying to create a fast 2D point inside polygon algorithm, for use in hit-testing (e.g. Polygon.contains(p:Point)). Suggestions for effective techniques would be appreciated.
Scott Evernden
  • 39,136
  • 15
  • 78
  • 84
278
votes
15 answers

Ball to Ball Collision - Detection and Handling

With the help of the Stack Overflow community I've written a pretty basic-but fun physics simulator. You click and drag the mouse to launch a ball. It will bounce around and eventually stop on the "floor". My next big feature I want to add in is…
mmcdole
  • 91,488
  • 60
  • 186
  • 222
241
votes
26 answers

Circle-Rectangle collision detection (intersection)

How can I tell whether a circle and a rectangle intersect in 2D Euclidean space? (i.e. classic 2D geometry)
aib
  • 45,516
  • 10
  • 73
  • 79
224
votes
29 answers

Circle line-segment collision detection algorithm?

I have a line from A to B and a circle positioned at C with the radius R. What is a good algorithm to use to check whether the line intersects the circle? And at what coordinate along the circles edge it occurred?
Mizipzor
  • 51,151
  • 22
  • 97
  • 138
160
votes
8 answers

iOS: verify if a point is inside a rect

Is there a way to verify if a CGPoint is inside a specific CGRect? An example would be: I'm dragging a UIImageView and I want to verify if its central point CGPoint is inside another UIImageView.
cyclingIsBetter
  • 17,447
  • 50
  • 156
  • 241
126
votes
10 answers

How do HashTables deal with collisions?

I've heard in my degree classes that a HashTable will place a new entry into the 'next available' bucket if the new Key entry collides with another. How would the HashTable still return the correct Value if this collision occurs when calling for one…
Alex
  • 4,844
  • 7
  • 44
  • 58
83
votes
7 answers

jQuery/JavaScript collision detection

How to detect if two
elements have collided? The two divs are simple coloured boxes travelling perpendicular to each other, so no complicated shapes or angles.
Chris Armstrong
  • 3,585
  • 12
  • 42
  • 47
73
votes
9 answers

How to detect collision in three.js?

I am using three.js. I have two mesh geometries in my scene. If these geometries are intersected (or would intersect if translated) I want to detect this as a collision. How do I go about performing collision detection with three.js? If three.js…
eqiproo
  • 1,736
  • 4
  • 17
  • 18
60
votes
2 answers

What is AABB - Collision detection?

Hi I'm making a voxel game in Java and while researching all the different things I'd need to learn, I noticed that a lot of games use AABB for collision detection. And then I remembered seeing AABB in Minecraft also. But when I google what AABB is,…
SemperAmbroscus
  • 1,308
  • 2
  • 12
  • 23
58
votes
6 answers

How does 3D collision / object detection work?

I'v always wondered this. In a game like GTA where there are 10s of thousands of objects, how does the game know as soon as you're on a health pack? There can't possibly be an event listener for each object? Iterating isn't good either? I'm just…
jmasterx
  • 52,639
  • 96
  • 311
  • 557
56
votes
9 answers

Collision detection of huge number of circles

What is the best way to check collision of huge number of circles? It's very easy to detect collision between two circles, but if we check every combination then it is O(n2) which definitely not an optimal solution. We can assume that circle…
Tomek Tarczynski
  • 2,785
  • 8
  • 37
  • 43
56
votes
10 answers

JavaScript: Collision detection

How does collision detection work in JavaScript? I can't use jQuery or gameQuery - already using prototype - so, I'm looking for something very simple. I am not asking for complete solution, just point me to the right direction. Let's say…
jack moore
  • 1,989
  • 4
  • 25
  • 22
52
votes
10 answers

Test if two lines intersect - JavaScript function

I've tried searching for a javascript function that will detect if two lines intersect each other. The function will take the x,y values of both the start end points for each line (we'll call them line A and line B). Is to return true if they…
Jarrod
  • 9,349
  • 5
  • 58
  • 73
47
votes
2 answers

Best algorithm for efficient collision detection between objects

I'm confused. Well not confused, so much as not wanting to do 6 test programs to see which algorithm is the best. So I thought I'd ask my expert friends here at SO to give me the benefit of their experience. The scenario is a 3d scene with…
Robinson
  • 9,666
  • 16
  • 71
  • 115
47
votes
3 answers

Performing your own physics calculations for a collision in Sprite Kit

I'm trying to set up some elastic collisions using Sprite Kit. There is an issue with the case of multiple objects resting near each other as I asked in Sprite Kit Physics Collision Issue I am confused on the timing of the situation for a…
Cherr Skees
  • 1,508
  • 2
  • 21
  • 37
1
2 3
…
99 100