point within hexagon?

BlitzPlus Forums/BlitzPlus Programming/point within hexagon?

dgroncki(Posted 2003) [#1]
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


skidracer(Posted 2003) [#2]
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




sswift(Posted 2003) [#3]
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. :-)


skidracer(Posted 2003) [#4]
input is 3 points that form 2 vectors, and no i don't know the correct term for the scalar cross dotted product thingy


QuietBloke(Posted 2003) [#5]
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.


dgroncki(Posted 2003) [#6]
thanks all for the replies! I may try and do a rough check first and then refine it with the more exact code above.


sswift(Posted 2003) [#7]
Um...

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


Ross C(Posted 2003) [#8]
Yeah, i think Quietblokes idea is good, pretty simple too.


Shagwana(Posted 2003) [#9]
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.


Perturbatio(Posted 2003) [#10]
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


dgroncki(Posted 2003) [#11]
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


sswift(Posted 2003) [#12]
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.


Perturbatio(Posted 2003) [#13]
oi! they aren't my functions


sswift(Posted 2003) [#14]
I don't know why I said perturbatio when I meant skidracer.


Perturbatio(Posted 2003) [#15]
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... :)


skidracer(Posted 2003) [#16]
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



dgroncki(Posted 2003) [#17]
skid, thanks for catching that! I'll give it a whirl tonight when I get home.


sswift(Posted 2003) [#18]
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.


superqix(Posted 2003) [#19]
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.


dgroncki(Posted 2003) [#20]
update - fixed code seems to work pretty well. Very few "flashes" (no hit situation).
thanks again, all!!


skidracer(Posted 2003) [#21]
You might want to change all the conditions to >=0 instead of >0 to be inclusive of the hexagon edges.