I can't see your picture, unfortunately. Have you posted it on a working URL?
If all you want are the points, I would give your for loops one pass per y-value, rather than one pass per hex. And store them sorted first by y then by x. Given that, it should be possible to create a formula to find the right indexes into the array for a particular hex.
It seems like you already have a handle on the trig involved to make successive horizontal passes.
I confess, when I made Hexara (
www.hexara.com still a work in progress), which uses a hex grid, I wasn't trying to search for shapes on the fly. Instead, I created a Hexagon object, with a polygon stored for its "contains" method, and gave each Hexagon a list of it's neighbors, in a HashMap for when I'm doing tree searches of possible paths through the grid. I only have 20-something hexagons, sounds like you have a lot more than that.