hex line intersections

← to index

this post is about how to run line/line intersections on a hexagonal grid, within the hexagonal grid system. this isn't "how to run bresenham's algorithm on a hex grid", this is how to implement basic line/line and line/point intersection algorithms on a non-cartesian grid.

you'll have to look at the page's actual source to see a lot of the math i'm using; there's no full listing of code.

you could very reasonably ask why even bother, since it's trivial to convert these coordinates to cartesian and then just doing standard cartesian line tests. in my case it's mostly just that it felt weird to constantly be converting into floats to handle what was fundamentally integer-based intersection code.

here's the hexagonal coordinate system that i'll be using:

this is an 'oblique' axis system. for more information about why these hexes don't actually tile, see my other hex drawing document. magnitude for these coordinates is calculated as follows: sign x == sign y ? max (abs x, abs y) : abs x + abs y. the math also involves conversion to a polar coordinate system during certain steps, which looks like this:

i've been calling this coordinate system 'rki': the first number is the radius, the second the axis, and the third the oblique motion from the axis. note that with the exception of 0 0 0, the i value is always strictly less than the r value, and the fraction i / r represents the coordinate's percentage of the distance 'around' that particular sextant of the grid. this means k + (i / r) will be a value between [0,6) that represents the angle of the hex from the origin. this will be relevant.

k ends up coming up a lot; i generally write a function like this:

let hexes =
	[new Hex ( 0, 1)
	,new Hex ( 1, 1)
	,new Hex ( 1, 0)
	,new Hex ( 0,-1)
	,new Hex (-1,-1)
	,new Hex (-1, 0)
	];

function dirHex (k, i) {
	return hexes[k % 6].timesScalar(i);
}

the first major function here is an implementation of turns, which takes three points: the first two defining a line, and the third the point to check the side of. for this, click to set the first point and move the mouse to set the second point, and every hex on the grid is called for the reference-- left is red, through is green, and right is blue. note how this is grid-accurate-- the only hexes that show up as green are the ones that absolutely perfectly run through the line given by the two points; this isn't a bresenham's line algorithm, which will calculate a solid line through the grid. (there's also some fun stuff about ratios and primes going on here but that's not really super relevant aside from the obvious stuff about how line slope is a linear relationship so of course you see the same ratios show up along a line)

apparently this does not work super great on a phone due to the lack of distinction between mousemove/click/drag events. try not using a phone.

(also note how the function fails if you hover over the selected tile, since that would try to test for a zero-length line with no directionality.)

here's a bigger grid to mess around with, for fun.

it's possible to chain a bunch of turns tests together to get shape tests. you can do this with arbitrary points, or you can do this with a series of axis-aligned lines. either will work, but in the latter case you'll get a solid perimeter, which can be useful. but this will only let you write a hex-in-poly test. to efficiently calculate whether two shapes intersect, you need a line/line intersection test.

turns serves as a line/point intersection test -- returning 'through' means that the hex is in the line, and it's possible to use that with some magnitude tests to do line segment/hex intersections. the next basic intersection test is line/line, or line segment/line segment intersections.

this uses turns internally, along with a bunch of other functions, to do a direct in-grid line/line intersection test. there's a somewhat extensive special-case for parallel lines intersecting, since now that space is quantized it's very reasonable to generate a list of overlapping points from two parallel line segments intersecting.

the first thing to do is write a hex/convex shape intersection: 'is this hex in this shape'. this is done a very basic way: a shape is defined as a clockwise winding of lines, and if a point is either through or on the right side of every line then it's in the shape.

(there are axis-aligned sweep tests, where to test if x,y is in the shape you make a line from -infinity,y to x,y and test that against the lines of the shape: an odd number of intersections means the point is in the shape and an even number of intersections means the point isn't in the shape. that would work here, but it would require a little tweaking to handle the cases where the line is right along an outer line, or where you hit a corner, etc, and i'm kind of lazy here.)

so that's useful, but it's not feasible to test every hex against every other hex to try to figure out if two shapes intersect.

with all this, though, it's possible to put together some convex shape/shape intersection tests: store some line segments that make a closed shape, and you'll be able to intersect them en masse to get intersection points. there's a 'fast' version of this that just detects any collision at all, and a slower version that calculates the precise overlap shape.

[explicit shape/line intersection demo]

[shape/shape intersection code]

[concave shape definition & concave shape/line intersection]