How to check if an object is surrounded?

alt text

Hi! My team is making a game where you have the ability to lay down a trail, which is the blue line in the image above. We want to implement the ability to complete a level once the trail surrounds an orb (the blue sphere in the middle). Right now the trail is created by constantly instantiating texture planes at the player’s position, and so I can check if the player has completed a trail by checking the collision.

I need to check if the trail surrounds the orb, somehow. Any ideas?

I have a solution in mind, but I have no idea how to implement it. I could accomplish this if I could somehow draw out a shape that updates along with the trail, and check if the orb is within that drawn out shape. Like this:
alt text

I just can’t think of any other solution, or even how to execute this one… help, anyone?

I once did a game like this, and although it was grid based (which made the problem both easier and more difficult at the same time :P) I found the easiest solution to be the “winding number algorithm”. alt text

I.E. isolate the part of the trail that formed the loop. “Draw” a line from outside the trail along the x-axis at the same level as the orb. Check how many rising and falling edges you hit on your way to the orb.

If you need more info, Googling “point inside polygon” and “winding number algorithm” might even lead you to some code samples :slight_smile:

This is basically an ‘is point inside polygon’ test as far as I can tell. The polygon is the 2d set of line segments defined by your path.

I couldn’t quite tell from description, but depending on your scenario:

  • if you can guaruntee the shape created is convex then the test is very easy. You can find the algorithm for ‘is point inside convex polygon’ online. It basically consists of taking each line segment defined by your player’s path and testing which side of that line the point in question is on. If you’re on the same side for every line, then you’re inside the polygon
  • if the shape is concave its a bit more complex but various algorithms exist for it. The most basic is to write your self a little ray vs line segment test. Take a point that’s definitely outside the polygon (such as the left most point minus a bit), and imagine a line from there to the target point. If it crosses 1 line segment the point is inside. If it crosses 2, its outside. If it crosses 3, its inside… you get the idea :slight_smile:

-Chris