# How do you find all hexes within an arbitrary arc?

Suppose you have a grid of hexagons oriented with the left and right segments of each hexagon perpendicular to the x axis. How do you find all hexes that fall wholly into an arbitrary arc of the origin hex? (for sake of argument let the arc be 90 degrees).

I'm not entirely sure what the proper way to phrase what I'm asking is, so I figured that an image would be better.

I would like to, from any facing on the origin hex (NE, E, SE, SW, W, NW) find all hexes that fall with in a given outward going arc. In the example below, I have place a 120 degree arc from the origin. Is there a mathematical way of calculating if a hex is within the gray region? Note: The gray region (angle) can be arbitrary.

-
What, exactly, do you mean by "arc"? Do you mean "part of a circle", or something else? Is an arc "of" the origin hex one that passes through it, or one centered on it, or something else? –  Tanner Swett Feb 12 '12 at 2:06
I edited my question. I hope it is clarified. –  AedonEtLIRA Feb 13 '12 at 15:55
You still need to clarify what you mean by 'within' - in particular, do you need only the center of the hex to be in your sector, or the entirety of the hex? Adding the two lines that define your sector might help, too... –  Steven Stadnicki Feb 13 '12 at 16:08
@StevenStadnicki Can do. I fix the image now. What I mean by entirely is that all 6 vertices (the entire area of the hex) must fall within the confines of the arc. –  AedonEtLIRA Feb 13 '12 at 16:36
(Also, as a note: this question might go better on the gamedev stackexchange site, as the mathematical content here is relatively minimal and much of it is bound up in particular implementation details that are likely more germane to the 'applied' site than to this one.) –  Steven Stadnicki Feb 13 '12 at 18:17

As far as the testing problem - 'is this hex within the sector?' - there's a relatively straightforward procedure, though not quite the simple equation you might be looking for. Since hexagons are convex, then the hex is entirely within your sector if and only if all six of its vertices are within the sector; and because a sector is the intersection of two half-planes, then testing a point against the sector comes down to the AND of two half-plane tests for the two defining half-planes. For instance, if you have an upwardly-oriented 90-degree sector, then the two half-planes in question are the two half-planes '$y\gt x$' and '$y\gt -x$'; you'd simply confirm that each vertex of your hex satisfies both of those constraints.