# 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

I should note that you're asking two slightly different questions: how to determine whether a hex is within the sector or not is a different problem from generating all the hexes within the sector; the generation problem is more challenging, and it may depend on what order you want to generate them in. (Also, note that 'all' here means infinitely many, so you'd probably want a stopping procedure too!)

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.

To go much further than this, the problem needs to be still more precisely stated; for instance, a sector isn't uniquely specified by just its angle; you need both a center or vertex point for the sector (which it sounds like will always be the origin in your case, but that's not clearly specified) and two angles - either the angles of the left and right sides, or a central 'facing' angle and a spread to either side of it. There are likely to be slightly smarter tests available, since depending on the specific sector angle only a couple of vertices will need to be tested for most hexagons (rather than all six), but those tests depend a fair bit on the problem's precise specification.

-
Thank you for your help. I was thinking there was some equation that would accomplish the same effect. Most problems could be solved programmatically with elementary math, but they are usually inefficient. I probably should move the question over to game.stack and work on a clarified and more specific question. – AedonEtLIRA Feb 14 '12 at 15:58