point within hexagon?

Hi all,
I'm working on a game that uses hexagon-shaped board tiles. I'm trying to figure out how I can determine, given a mouse coordinate, which (if any) hexagon that coordinate falls within. Any suggestions on either some formula or some other way to think of the problem? If it proves too time consuming to figure out, I guess I could always just use the largest inner square that fits within a hexagon to approximate where the mouse is at, although it won't register in certain "dead" areas.
thanks...Dave

once it passes some quicker bounds test, for accuracy you could use something like this:

Function dot(x0,y0,x1,y1,x2,y2)
	Return (x1-x0)*(y2-y1)-(x2-x1)*(y1-y0)
End Function

Function InsideHexagon(px,py,x0,y0,x1,y1,x2,y2,x3,y3,x4,y4,x5,y5)
	If dot(x0,y0,x1,y1,px,py)>0
		If dot(x1,y1,x2,y2,px,py)>0
			If dot(x2,y2,x3,y3,px,py)>0
				If dot(x3,y3,x0,y0,px,py)>0
					If dot(x4,y4,x0,y0,px,py)>0
						If dot(x5,y5,x0,y0,px,py)>0
							Return True
						EndIf
					EndIf
				EndIf
			EndIf
		EndIf
	EndIf
End Function

Skid, why do you have that function labeled dot() as in dot product, when it is not a dot product?

I was trying to figure out how your code worked, cause I was gonna suggest you find out which side of each side the point is on, and if it is on the inside of each side then it is on the inside of the object, but when I look at your dot function, it appears to accept three vectors, and a dot product is the product of two vectors.

So I'm confused. :-)

input is 3 points that form 2 vectors, and no i don't know the correct term for the scalar cross dotted product thingy

Personnaly I would create a graphic image containing a solid image of the hexagon.
Then I would do a bounding box collision check where the bounding box is around the whole hexagon.
If the mouse is within the bounding box then you can do a pixel check on your hex image to see if the pixel is inside the hexagon.

Just thinking off the top of my head here so I hope that makes sense.

thanks all for the replies! I may try and do a rough check first and then refine it with the more exact code above.

Um...

Why does your function not use any floating point values skid? :-)

Yeah, i think Quietblokes idea is good, pretty simple too.

One of these functions I posted in the code arcs might also help you find a mathamatical way to pull off what you want. Food for thought at least.

I was recently investigating this myself, I discovered these links:

http://pixelpracht.flipcode.com/files/hexcoordsTut_e.htm
http://www-cs-students.stanford.edu/~amitp/Articles/Hexagon1.html
http://www-cs-students.stanford.edu/~amitp/gameprog.html#Hex

Hey skid,
I tried using the formula code you posted and I"m getting weird results. If my piece is within a hex as calculated by these functions, I will see it at the mouse location. If it is not within any hex, the piece will not appear. As I move the piece around within the gameboard that contains all hexes, it "flashes" very much so there are many instances where the test is failing (more than it working).

I have not incorporated any floating numbers here. Is that needed? I am purely using integer x,y's as input.
Help anyone?

thanks...Dave

Try changing perturbatio's functions so that all the integers are floats and see if that solves the problem. It's very odd that he used ints all over the place.

oi! they aren't my functions

I don't know why I said perturbatio when I meant skidracer.

It's my subliminal messaging program I wrote, I set it to say all code belongs to Perturbatio in anticipation of the european software patents act actually being passed... :)

oops, my bad, try this one, and I have no idea why you would want to use floats when using integer based pixel positions:

Function dot(x0,y0,x1,y1,x2,y2)
	Return (x1-x0)*(y2-y1)-(x2-x1)*(y1-y0)
End Function

Function InsideHexagon(px,py,x0,y0,x1,y1,x2,y2,x3,y3,x4,y4,x5,y5)
	If dot(x0,y0,x1,y1,px,py)>0
		If dot(x1,y1,x2,y2,px,py)>0
			If dot(x2,y2,x3,y3,px,py)>0
				If dot(x3,y3,x4,y4,px,py)>0
					If dot(x4,y4,x5,y5,px,py)>0
						If dot(x5,y5,x0,y0,px,py)>0
							Return True
						EndIf
					EndIf
				EndIf
			EndIf
		EndIf
	EndIf
End Function

skid, thanks for catching that! I'll give it a whirl tonight when I get home.

skid:

Well I suppose in this case you could get away with using only ints, but I like to use floats for everything just in case.

FYI,

(x1-x0)*(y2-y1)-(x2-x1)*(y1-y0) is just an equation that returns the distance from a point (x2,y2) to the closest point on a line (x0,y0)-(x1,y1). The cool part of the equation is that it will return negative numbers if a point is left of a line and positive numbers if the point is right of the line and 0 if the point is on the line.

update - fixed code seems to work pretty well. Very few "flashes" (no hit situation).
thanks again, all!!

You might want to change all the conditions to >=0 instead of >0 to be inclusive of the hexagon edges.