2 ms·
Actually, your "pixel overlap" method can be developed into a technique that is pretty efficient, provided we have (a) a quick way to partition any polygon into
by akoboldfrying 3y ago
Actually, your "pixel overlap" method can be developed into a technique that is pretty efficient, provided we have (a) a quick way to partition any polygon into 2 roughly equal-size polygons and (b) a quick way to come up with a "covering disk" for any polygon (that is, a circle that contains the polygon, and doesn't extend too much further):
isColliding(poly P, poly Q):
if dist(P.circle.centre, Q.circle.centre) > P.circle.radius + Q.circle.radius:
return false
if P.circle.radius > THRESH:
(P1, P2) = subdivide(P)
return isColliding(P1, Q) || isColliding(P2, Q)
if Q.circle.radius > THRESH:
(Q1, Q2) = subdivide(Q)
return isColliding(P, Q1) || isColliding(P, Q2)
// Both P and Q are "small"
return detectOverlapByRasterising(P, Q)