Re: Simple question
- From: Gene <gene.ressler@xxxxxxxxx>
- Date: Wed, 17 Oct 2007 14:02:26 -0000
On Oct 17, 1:07 am, Logan Shaw <lshaw-use...@xxxxxxxxxxxxx> wrote:
guitarstru...@xxxxxxxxx wrote:
I need some code to detect the collision between a square and a
circle. Almost any language will be acceptable. Thanks!
Break this up into three cases.
Case 1: the center of the circle is inside the square.
-> You always have a collision.
Case 2: the center of the circle is within the vertical range of
the square or within its horizontal range. In other words, you
could draw a horizontal or vertical line through the center of
the circle and it would pass through the square.
-> Measure the distance from the center of the circle to
the nearest (perpendicular) edge; if it's less than the
radius of the circle, you have a collision.
Case 3: neither #1 or #2 is true, so the center of the circle is
off at a diagonal.
-> Measure the distance from the center of the circle to
the closest corner of the square; if it is less than the
radius of the circle, you have a collision.
Note the difference between #2 and #3 is that in #2 you are finding
a distance along a horizontal or vertical line, so you only need to
subtract two X coordinates or subtract two Y coordinates, whereas in
#3 you are using the Pythagorean Theorem.
To see why all this works, imagine rolling the circle around the
square. At each point, where is the center of the circle, and what
is the closest point on the square? It seems fairly easy to see
that the time when the corner becomes the closest point is the time
when the center of the circle is on the line formed by one of the
edges of the square.
- Logan
Excellent, except OP did not say the square was axis-aligned. You can
either transform the problem so it is, or do the tests in problem
space. You can determine if a point P is left of a line segment from
A to B by testing
(P-A) dot perp(B-A) > 0 and (P-B) dot (A-B) > 0 and (P-A) dot (B-A) >
0
Where perp([x,y]) = [-y,x].
This is enough to determine the cases you've described very well.
One other thing is that the idea of sliding one convex polygon around
the border of another (without rotating, though in this case it
doesn't matter) and considering the area enclosed by some reference
point on the sliding polygon (in your case the center of the circle),
is a good one. It's called a Minkowski difference. The problem of
determining if two convex polygons intersect is equivalent to
determining if the reference point lies in the Minkowski difference.
For this problem, the difference is the square "blown" up by the
circle radius on all sides, with corners rounded. We need to test if
the circle center lies inside this oval shape, which is equivalent to
what you've described.
.
- References:
- Simple question
- From: guitarstrummr@xxxxxxxxx
- Re: Simple question
- From: Logan Shaw
- Simple question
- Prev by Date: Re: sample software designs
- Next by Date: Re: Simple question
- Previous by thread: Re: Simple question
- Next by thread: Printing only a portion of the Web page
- Index(es):
Relevant Pages
|
