Given three points on a triangular lattice (think of them as Eisenstein integers if you like), I want to calculate the area of the axis-aligned hexagon spanned by them (in units of sqrt(3)/4 or "triangles"). Can anyone think of a neat expression or O(1) algorithm for that?

(the hexagon may be degenerate, so it may be a quadrilateral or line or point)

...or triangle

...or pentagon (somehow thought that isn't possible)

for example, given 0, ⍵ and 3+2⍵ I'd want to get 7

best I've currently got is O(N) where N is the shortest extent of the hexagon. compute all six bounding lines, take the opposite pair that is closest, then iterate along parallel lines from one of those to the other, counting how wide the line is inside the hexagon at each step (which lets you infer the number of triangles between two lines).

so I guess that's O(sqrt(A))

I suppose it's possible to split the hexagon into two trapezia and a parallelogram (any of which might be degenerate) and calculate their areas explicitly.

yep, that works, I even managed to simplify it a bit:

min_x = [a.r, b.r, c.r].min
max_x = [a.r, b.r, c.r].max
min_y = [a.i, b.i, c.i].min
max_y = [a.i, b.i, c.i].max
min_z = [a.r-a.i, b.r-b.i, c.r-c.i].min
max_z = [a.r-a.i, b.r-b.i, c.r-c.i].max

left_y  = min_x - min_z
right_y = max_x - max_z

width  = max_x - min_x
height = max_y - min_y

EInt.new(2 * width * height - (max_y - left_y)**2 - (right_y - min_y)**2)

I'm basically computing the area of the bounding parallelogram and subtract the two triangles that extend beyond the hexagon. (and triangle areas are trivial to compute because in these units they're just h^2 where h is the triangle's height)