How do I determine if two convex polygons intersect?

by

You could use this collision algorithm:

To be able to decide whether two convex polygons are intersecting (touching each other) we can use the Separating Axis Theorem. Essentially:

  • If two convex polygons are not intersecting, there exists a line that passes between them.
  • Such a line only exists if one of the sides of one of the polygons forms such a line.

The first statement is easy. Since the polygons are both convex, you’ll be able to draw a line with one polygon on one side and the other polygon on the other side unless they are intersecting. The second is slightly less intuitive. Look at figure 1. Unless the closest sided of the polygons are parallel to each other, the point where they get closest to each other is the point where a corner of one polygon gets closest to a side of the other polygon. This side will then form a separating axis between the polygons. If the sides are parallel, they both are separating axes.

So how does this concretely help us decide whether polygon A and B intersect? Well, we just go over each side of each polygon and check whether it forms a separating axis. To do this we’ll be using some basic vector math to squash all the points of both polygons onto a line that is perpendicular to the potential separating line (see figure 2). Now the whole problem is conveniently 1-dimensional. We can determine a region in which the points for each polygon lie, and this line is a separating axis if these regions do not overlap.

If, after checking each line from both polygons, no separating axis was found, it has been proven that the polygons intersect and something has to be done about it.

More Related Contents:

  1. How to test if a point is inside of a convex polygon in 2D integer coordinates?
  2. How do CSS triangles work?
  3. How do you detect where two line segments intersect? [closed]
  4. Circle-Rectangle collision detection (intersection)
  5. An algorithm for inflating/deflating (offsetting, buffering) polygons
  6. ray and ellipsoid intersection accuracy improvement
  7. How to determine if a list of polygon points are in clockwise order?
  8. A simple algorithm for polygon intersection
  9. How to create circle with Bézier curves?
  10. How do I efficiently determine if a polygon is convex, non-convex or complex?
  11. Largest circle inside a non-convex polygon
  12. How to determine if a point is inside a 2D convex polygon?
  13. Problem superimposing and aligning 3D triangles
  14. Efficiently find points inside a circle sector
  15. Polygon enclosing a set of points
  16. algorithm to rasterize and fill a hypersphere?
  17. Is there a more efficient way of texturing a circle?
  18. How to determine whether a point (X,Y) is contained within an arc section of a circle (i.e. a Pie slice)?
  19. Check if polygon is inside a polygon
  20. Boundary enclosing a given set of points
  21. How can I create an internal spiral for a polygon?
  22. Transfer coordinates from one triangle to another triangle
  23. Checking if a point is inside a polygon
  24. Using the “animated circle” in an ImageView while loading stuff
  25. Convert lat/lon to pixel coordinate?
  26. What’s the simple way to compute the diagonal length of a 3D mesh bounding box?
  27. Pygame rotating cubes around axis
  28. How to intersect two polygons?
  29. Random points inside a parallelogram
  30. Location of highest density on a sphere

Leave a Comment