9
\$\begingroup\$

How to detect a collision between a sprite and a user-generated shape of some sort.

For example. There are some objects on the screen. The user takes their finger and draws a circle shape around an object (The selection rule is painting circle around the sprite, but the painting shapes may be various). I need to detect which object selected, which just like:

(demo images): originally posted as http://i52.tinypic.com/28h0t1g.png

\$\endgroup\$
  • \$\begingroup\$ Can you explain why blue is selected and not red in your final example? Can you also clarify whether the line has to actually touch the sprite? The third example does not touch the red box but it is stated as selected. The 5th example is very similar but not selected. What is the difference you're looking for between #3 and #5? \$\endgroup\$ – Romen Aug 26 '19 at 21:24
2
\$\begingroup\$

If the shape is drawn primarily with line segments from the user (or Bezier curves with control points), you can implement a fairly widely used algorithm known as Separating-Axis-Theorem. Simply put: if there is an axis (unit-vector representing a direction) on which the shapes don't overlap (their projected values do not result in a positive difference), the objects are not overlapping. I have used this in the past and it has worked like a charm.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

If shape is hand-drawn like in Crayon Physics, you can hold an array of straight lines and check collisions with each of them. Despite of straight lines you can use Bezier curves or something like that.

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$
  • Create a buffer of same size as screen (or surface where are Your shapes). At each position it contains boolean whether there is sprite; then, check all "pixels" of user shape whether at their position is the sprite (by checking value of that boolean). Alternatively, You can create more sprites there by storing their ID instead of boolean; but this was case of 1 sprite.
  • If user generated shape can be represented by sequence of lines, then You can check whether each such line crosses sprite. Since sprite has rectangular shape and user shape is a line just Look for "line rectangle intersection" ... (separating axes algorithm si one way to do it)

Approaches depend on what data structures You choose, whether they are bitmaps or vectors.

First approach can handle arbitrary complex shapes, is simple to implement but uses more memory. Actually You can reduce memory overhead by using compression and speed it up by using hierachical data strutures (octrees) ...

Second approach , is not so simple to implement but uses more processing power.

In each case measure if it matters. I would try to do first one because it is simpler to implement. Good luck. :)

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.