Square and Circle Sector intersection

Hi and hello. I was looking for a forum with this kind of knowhow, so let's get started.

I have a circle segment with a given angle, direction, and radius (it's like a 2d field of view of a character). And a lot of squares. How can I check which squares are visible?

Here's an example:
http://img410.imageshack.us/img410/1236/examplel.jpg

I've figured out how to do it with a full circle (as seen on the picture), but I can't figure out how to do it for a limited segment.

Any solutions?

Thanks for help!

Ps. To be specific:
http://img5.imageshack.us/img5/3628/ex2o.jpg

I'm gonna assume speed isn't entirely of the essence. The following method should easily be doable 10,000+ times per second; if you need a faster method ask and I'll try to optimize.

1. Construct two vectors, a and b, which are the sides of the cone in your field of view pie slice. To be specific, each has magnitude equal to radius, a has reference angle direction + angle/2, b has reference angle direction - angle/2. Recall that any 2D vector is given by these two parameters, using 2D vector = <magnitude*cos(reference angle), magnitude*sin(reference angle)> for angles in radians.
   
2. Apply your "full circle" check (which is almost certainly some variant on the distance formula).
   
3. For any points that pass the "full circle" check, do the following:
   
   • Construct a vector pointing from the tip of your cone to the point in question. Again to be specific, this vector is v = <pointx - tipx, pointy - tipy>.
   • Normalize a, b, and v by dividing each by its magnitude--for some vector <x,y>, that vector normalized is <x,y>/Sqrt(x^2+y^2). Note that you can normalize a and b in step 0 by setting magnitude=1.
   • Calculate the angles between a and v, and v and b. If v lies in the cone, the sum of these angles should be the same as the angle between a and b, and not otherwise. Recall that for normalized vectors, we can find the angle between them in terms of the dot product: if a = <a1, a2> and b = <b1, b2>, then a dot b = a1*b1+a2*b2 = cos(theta) with theta being the angle between them.
   • In particular, use this formula: arccos(a dot v) + arccos(v dot b) = arccos(a dot b) [allowing some small fudge factor, say 0.0001, for numerical roundoff errors]. If that equality holds up to the fudge factor, accept the point. If it doesn't hold, reject the point.

Note that the test in step (3) assumes that v is not the zero vector--that is, it breaks whenever your test point is exactly centered on your character, which you may well expect seeing as it's arguable as to whether such a point is in the character's field of view.

Feel free to ask for clarification if needed. It ended up being a crash course in basic vector math which can be tough without well developed mental pictures.

I want to check for whole squares. Not points. (Points can be done a lot easier - get atan of v and check if it's between direction + angle/2 and direction - angle/2).

Whole squares are hard, believe me. There are a lot things to concider:

(example!)

http://img210.imageshack.us/img210/1879/ex3.jpg

1. Fully inside FOV = SEEN
2. Intersecting the FOV arc = SEEN
3. Intersecting the circle, but not the FOV arc, and in the FOV angle = NOT SEEN (that's the hardest one which I can't figure out)
4. Fully outside = NOT SEEN

Hope it's clearer now.

If you consider #2 to be seen, all you need to do is to check wether ANY corner-point of a square is seen.
In other words you need the check only for POINTS! (Which is easy, according to YOU)

Ok, that was just an example. If we investigate, some visible squares don't have any corners inside the circle segment.

examples continue:

http://img2.imageshack.us/img2/2679/lolkej.jpg

I had assumed by "squares" you meant the black blobs and not the red boxes. It does make things tougher this way.

There are three cases:

1. Square entirely in sector. This occurs if and only if the four corners of the square are all inside the sector, since the sector is convex.
2. Square partially in sector. Tough edge cases.
3. Square not in sector. Most of these squares can be eliminated quickly from rough distance checks.

To test for 1, do the four point tests. To test for 2 and 3, you could simply do collision detection. Consider the sector to be a circle and two lines, and collide the four lines of the box with those equations. Check if the intersections occur both on the sector and on the box. Cover the edge case of a box just touching the edge of the sector at a single point. If no valid intersections occur, we have case 3; otherwise, since we have an intersection, one side of the box will be inside and one will be outside the sector, and we have case 2.

The intersections could be done with some algebra. It's not terribly pretty but would cover all cases, and with a few optimizations would be quite quick since that edge case wouldn't occur very often. The key thing to this method is to realize that case 1 can be tested for easily due to the concavity of the sector.

I figured I'd put in a more formal proof of my test for case 1, since the full argument is technical and I have a few minutes to waste before dinner :).

A polygon is convex when any line segment between any two vertices remains entirely inside (or on the edge of) the polygon, or equivalently when internal angles are 180 degrees or less. Convex non-self-intersecting polygons have the property that their interior set (including points on the edge of the polygon) is a convex set. Convex sets by definition have the property that, choosing any two points in the set, the line segment connecting those two points is also entirely in the set.

Consider the following sequence of convex, non-self-intersecting polygons: (base case) make a triangle out of your sector; next add a vertex in the middle of the secant and attach it to the curved part, making a kite-like object with two secants; continue adding a vertex in a similar manner to make closer approximations of the sector. This generates an infinite series of polygon approximations of the sector. The sequence clearly converges to the sector, more technically it does so by the convergence of linear interpolations of continuous functions with a finite number of discontinuities of the first kind in their first derivative. The sequence also has the important property that each polygon is entirely contained within the sector. Each polygon is convex since the refinements never add an angle greater than 180 degrees, and the starting triangle is convex.

Now we wish to show that for a box B and a sector S, B is entirely within S if and only if the 4 corners of B are within S.

In the backward direction, assume the 4 corners of B are within S and show B is entirely within S. Since the above sequence of polygons converges to S, take a polygon P from the sequence which contains all 4 corners of B. P is convex and non-self-intersecting, so that it has the property above. Consider the four edges of B; from the convexity property, since the two vertices of these edges are in P, the edges themselves are in P. We can then pick mirrored points on two opposite edges of B, and these with the segment between them will also be in P. In this manner we can cover all of B, so B is entirely within P. Since each polygon is entirely contained in the sector, P is in S, so B is entirely within S, which is what we wanted.

In the forward direction, assume B is entirely within S and show that the 4 corners of B are within S. This is trivially true. Thus, the above equivalence for being entirely within S holds, and testing the 4 corners of B suffices to show that B either is or is not a case 1 box. Done.

Thanks for your reply!

I was thinking about collision detection. Line segment intersections are cheap to compute, but there's a problem with line segment - arc segment intersection (with requires sqrt'ing...). And there are 4 segments to check.

My current approach is:
1. Eliminate all the squares outside the circle.
2. For a square that is checked, compute an angle (and direction) at which it is seen from our point of view.
3. Check if it covers our field of view.

This works pretty good and fast, but there is a problem with squares "type 3" (from my 2nd post).

Short of collision detecting the problem squares I don't see a way out in all cases. The number of problem squares would almost certainly be a very small fraction of all squares if you first check for any of the 4 corners being inside the sector. I figure if you can take arctans and projections/rotations you'd likely have the processing time to do those checks. In fact, I suspect that no function involving only polynomials (no negative exponents) solves this in all cases, though a proof would be very tough.

If you wanted to avoid the intersection math... personally I'd reevaluate how important these edge cases are.

er

This may be nit-picky, but would it be more helpful to reconsider step 1 of
your current approach to be:

1. Only consider squares inside of the circle

That's as far as I've gotten so far :)
Interesting situation.

Spoo

Starting from all squares using an algorithm, I think it makes more sense to "eliminate" first. Starting in a proof, though, "consider" would definitely be the way to do. :D (Technically, there are squares that are both on the inside and outside that "consider squares inside of the circle" wouldn't literally cover without caveats)

jem

Yeah, you might be right. I was just reacting to er's language;
I had no plan in mind.

Now that I've had a little sleep, I've hatched an idea, which may
or may not comply with my prior post. Let me elaborate...

Givens:
1. O, the origin of the sector
2. theta, the angle (fov)
3. R, the radius
4. C1 to C4, the coords of the 4 corners of each square

General concept:
1. Find the point P on a square that is the closest to O
2. If distance O-to-P is less than R, then square is IN.

Somewhat more specific concept (elaboration of step 1):
1a. of C1 to C4, find the two that are the closest to O
1b. draw a line between them
1c. somehow (hehe) determine the point on that line that is
closest to O.

Some interesting outcomes (re: er's post #5)

Square 1: lower left (LL) and lower right (LR) are closest corners,
and visually, it appears that the midpoint (P) of a line between
LL and LR is the closest to O. Distance O-P sure seems less than R.
Indeed, if distance from LL-O and LR-O are equal, then we can state
that the square is orthogonal to O (ie, the centerline of the square, if
projected, would go through O).
Square 2: ditto
Square 3: ditto

Actually, orthogonal cases become quite easy, albeit rare. Hence,
for the majority of the cases, fleshing out step 1c will be key. Oh yeah,
then we need to deal with theta !!

That's all I've got so far... anything to it?

BTW, er .. fantastic graphics :thumb:
And welcome to the Forum (as this appears to be your first thread) :wave:

Spoo

Yeah, I'm trying to visualize what I want to say :P English is my second language and pictures don't require words :)

Today's bonus - a working prototype!

Try it out -> http://er453r.release.com.pl/ssi/

W - forwards
S - backwards
A - rotate left
D - rotate right
Up Arrow - increase radius
Down Arrow - decrease radius
Left Arrow - increase angle
Right Arrow - decrease angle

Works in Firefox (Chrome recomended - it's javascript is much faster). I haven't checked other browsers.

It currently uses my algorithm described earlier. You can check out the source code if you want to, though it lacks any comments and hasn't been cleaned up. The function discussed is segment_intersects_square :P

Have fun.

Spoo, I think you're on the right track to eliminate those Type 3 cases. The missing bit to the algorithm is:

Step 3: Check if it covers our field of view. If so, check that, restricting ourselves to the field of view, the square comes within the given radius of O.

We can check this by checking each side in the following way. You might be able to check only one or two sides, but I thought of a counterexample to the naive 'check the one with the closest midpoint' idea; the counterexample comes up when you start considering theta.

For each side, find the perpendicular bisector passing through that side's line, starting at O. [This isn't tough, just algebra spew.] Find the point P where this bisector passes through that side's line; that will have to be the minimum distance. Note that traveling along the side in either direction is guaranteed to continually increase our distance to O.

If P is in the field of view, continue. If P is not in the field of view, travel along the edge line until you get into the field of view, and use that point as your new P. [More algebra and a couple of switch cases.]

If distance(P, O) <= radius using any of the sides, the box is in the sector. If not, the box is outside the sector. This relies on the fact that we've just ensured P to be the local minimum distance of the line to O on the field of view.


Attached is an MS Paint rendition of this. The green line is a one side of a particular square, extended in each direction. The blue line is the perpendicular bisector of that green line. The orange point at their intersection is the initial P. The purple point is the new P, the first point we get if we travel towards the field of view. The other squares are included as examples.

Oh hey I thought of something. You might be able to get by in your code without inverse trig functions, which are probably by far the slowest part of the collision routine.

The inverse tangent function is monotonic--it's always increasing. So, if we have three points at (x1, y1), (x2, y2), (x3, y3) and we want to determine if the second point is in the arc swept out between the first two, we don't actually have to evaluate the inverse tangent.

If the points are in the first or second quadrant, we can simply say

p2 is between p1 and p3 if and only if y1/x1 <= y2/x2 <= y3/x3 if and only if atan(y1/x1) <= atan(y2/x2) <= atan(y3/x3).


There are some negative cases to consider but I would bet this would be an improvement over taking inverse tangents all over the place.

Yeah, I actually thought about this at one point and completely forgot about it :P Thanks.

But I was thinking about something else. The field-of-view, should be determined by two bounding vectors and radius (not one vector, angle, radius). Then we can check points inside simply by calculating cross products.

I'm not quite sure what cross products have to do with it, but yeah you can use two vectors and a radius like I suggested in my first reply (or use a variant on that).

Sign of the cross product determines if a vector is on the "left", or the "right" side of another vector. If we have 3 vectors we can check if one given is between other two.

That's a good point. Looking at it, that method would take two multiplications and a comparison for a single test, in all 4 multiplications and 2 comparisons to see if p2 is between p1 and p3. The one I mentioned above would take 3 divisions and 2 comparisons, making it (maybe) slightly better.