Re: 2D circle-triangle intersection test
- From: "Gene" <eugene.ressler@xxxxxxxxxxxxxxx>
- Date: 23 Jul 2005 17:46:36 -0700
If you mean a test for whether the _areas_ intersect (not the edges),
then you get an interesting algorithm by thinking about the Minkowski
sum of the two shapes. Conceptually, you slide the circle around the
triangle while tracing out the path of the circle's center. The
resulting shape is a larger triangle with the corners rounded to the
same radius as the circle. Now just test whether the _actual_ center
of the circle falls inside this new shape.
You can make the test relatively efficient by first constructing three
half spaces that are the outside the big triangle. The math for this
is simple enough. Put the edge in point-normal form and then move the
point along the normal a distance of r, the circle's radius. If the
center is C and C lies in any of the outside half-spaces, then there is
no contact.
Otherwise there is contact unless the center lies just outside one of
the rounded corners. You can detect this case by testing C against the
half-spaces outside of the _original_ triangle edges. If C falls
inside any two, that gives you the vertex V to test (there can be only
one). If |C-V|<=r, you have contact, else none.
Suppose the triangle with vertices in counterclockwise order is abc, C
is center of circle with radius r. Then the code (assuming no
degenerate triangles) would look something like:
nab = normalize(perp(b - a))
if (dot(C - (a + r * nab), nab) > 0) return false;
nbc = normalize(perp(c - b))
if (dot(C - (b + r * nbc), nbc) > 0) return false;
nca = normalize(perp(a - c))
if (dot(C - (c + r * nca), nca) > 0) return false;
if (dot(C - c, nca) > 0 and dot(C - a, nab) > 0) return (distance(C,
a) <= r)
if (dot(C - a, nab) > 0 and dot(C - b, nbc) > 0) return (distance(C,
b) <= r)
if (dot(C - b, nbc) > 0 and dot(C - c, nca) > 0) return (distance(C,
c) <= r)
return true
.
- Follow-Ups:
- Re: 2D circle-triangle intersection test
- From: Dylan
- Re: 2D circle-triangle intersection test
- References:
- 2D circle-triangle intersection test
- From: Dylan
- 2D circle-triangle intersection test
- Prev by Date: Re: How to convert RGB values to CMYK values
- Next by Date: CMYK/RGB conversion
- Previous by thread: Re: 2D circle-triangle intersection test
- Next by thread: Re: 2D circle-triangle intersection test
- Index(es):
Relevant Pages
|
