# Line Crossing a hexagon grid

We have an array of hexagons that a line, from the center of a starting hexagon goes to the center to a target hexagon (this works well).
The start hex and target hex centers are:
Var p1 As Point = GetCenter(from)
Var p2 As Point = GetCenter(tohex)

For each hexagon in the array we get its center and call GetHexagonEnteringSide
to get the side of the hexagons from where the line enters to the hex.

Var hexagon As Point = GetCenter(hex)

``````Public Function GetHexagonEnteringSide(p1 As Point, p2 As Point, hexagon As Point) As Integer
' Define Pi
Const Pi = 3.14159265358979323846264338327950

' Calculate the vector representing the line
Var lineVector As New Point(p2.X - p1.X, p2.Y - p1.Y)

' Calculate the vector representing the hexagon center to the starting point
Var hexagonToStartVector As New Point(p1.X - hexagon.X, p1.Y - hexagon.Y)

' Calculate the angle between the line vector and the hexagonToStartVector
Var angle As Double = Atan2(lineVector.Y, lineVector.X) - Atan2(hexagonToStartVector.Y, hexagonToStartVector.X)

' Normalize the angle to be within [0, 2 * Pi)
If angle < 0 Then angle = angle + 2 * Pi

' Determine the hexagon entering side based on the normalized angle
Var enteringSide As Integer = 1 +  round(angle / (Pi / 3)) Mod 6

' Return the entering side
Return enteringSide
End Function

``````

But, something is not working and I canâ€™t find what is it. The resulting entering side is not correct always and I do not have enough skills on Vectors, angles, etc.
Can anyone give some light ?.

Perhaps you could sketch a diagram of what you are trying to define and include this in the query.

You have two vectors that are defined as points.? Where is the origin of these vectors? Is it the same origin?

â€śhexagon in the arrayâ€ť? That happen to lie between the â€śstartâ€ť hexagon and the â€śtargetâ€ť hexagon. Are these regular hexagons tiled on a plane?

Why is the vector representing the line simply the midpoint of the line?

Speaking only for myself, I have difficulty visualizing what is being asked.

Now with Pixmapshape collision

https://www.dropbox.com/scl/fo/a7cwj38fms2tg069i2k0l/h?rlkey=7rjypx8kvbudoupwv2zmecrzf&dl=1

Thanks Robert and Rudolf Iâ€™ll try to clarify my project.
Iâ€™m using flat-topped hexagon grid, odd columns down

The Rudolf example is near my project.
In my case a line goes from the center of the started hexagon to the center of the target hexagon. Always from center to center. Then all hexagons crossed by the line are highlighted.

When the line crosses exactly a side of two hexagons both are highlighted.

When crossing the border of two hexes, both are included

I use zoom and scroll

I need to know the side of each involved hexagon crossed by the line.

In the last example the line enters
0404 from 5
0405 from 0
0504 from 4
0505 from 0
and reaches 0606 from 5

Getting these sides from code is where Iâ€™m lost.

A simple way I tried was using GetSharedSide()
That works on all cases where the line not goes through a common
border.

``````Public Function GetSharedSide(fromHex as string, toHex as string) As string
// tornem  el borde del from hex
// Si es vol el borde del toHex cal cridar intercanviant els hexes (tohex, fromHex)
//
// ODD column DOWN LAYOUT

Var colFrom  as Integer = fromHex.left(2).Val
Var colTo as integer = toHex.left(2).val
Var rowFrom as integer = fromHex.Right(2).val
Var rowTo as integer = toHex.Right(2).val

return "-1"
end if

// Mateixa columna
if colFrom = colTo then
if rowFrom > rowTo then return "0" else return "3"
end if

if colFrom mod 2 = 0 then // columna PAR **********

// cap a l'oest
if colFrom > colTo   then
if rowFrom = rowto then Return "4" else Return "5"
end if
// cap a l'est
if colFrom < colTo  then
if rowFrom = rowto then Return "2" else Return "1"
end if

else // Columna impar **********

// cap a l'oest
if colFrom > colTo  then
if rowFrom = rowto then Return "5" else  Return "4"
end if
// cap a l'est
if colFrom < colTo   then
if rowFrom = rowto then Return "1" else Return "2"
end if
end if

return "-1"
End Function

``````

LosHexes() is the array of all involved hexes
And to test it

``````Public Sub TestBorders()
var index as integer = 0
var hex1, hex2 as string
var border as string

For i as integer = 0 to LosHexes.LastIndex-1
hex1 = LosHexes(i)
hex2 = LosHexes(i+1)
border = GetSharedSide(hex2,hex1)
system.DebugLog (hex2 + "-"+ border )
Next
End Sub

``````

This works except (thatâ€™s the point) when the line crosses exactly the common border of two hexagons. For these cases I tried the vector system that I do not understand well and not works either.
for example:

``````// Calculate the vector representing the hexagon center to the starting point
Var hexagonToStartVector As New Point(p1.X - hexagon.X, p1.Y - hexagon.Y)
``````

Why isnâ€™t this:

``````Var hexagonToStartVector As New Point(hexagon.X - p1.X, hexagon.Y - p1.Y)
``````

This would seem more in keeping with

``````// Calculate the vector representing the line
Var lineVector As New Point(p2.X - p1.X, p2.Y - p1.Y)
``````
``````Const Pi = 3.14159265358979323846264338327950
// Assume that the upper horizontal side is 0 and then numbered clockwise 1, 2 etc.
// Basically setting up a coordinate system where the center of the startHexagon is considered the origin
Var p1 As New Point
Var p2 As New Point
Var hexagon As New Point
Var side As Integer

Var startToEndVector As New Point
startToEndVector.X = p2.X - p1.X
startToEndVector.Y = p2.Y - p1.Y
Var startToEndAngle As Double
startToEndAngle = ATan2(startToEndVector.X, startToEndVector.Y)

Var startToHexagonVector As New Point
startToHexagonVector.X = hexagon.X - p1.X
startToHexagonVector.Y = hexagon.Y - p1.Y
Var startToHexagonAngle As Double
startToHexagonAngle = ATan2(startToHexagonVector.X, startToHexagonVector.Y)

// The special cases when the connecting line runs exactly across a common border
// the possible startToEndAngle angles are 0, Pi/3, 2Pi/3, Pi, 4Pi/3, 5Pi/3

If startToEndAngle.Equals(0, 10) Then
If startToHexagonAngle > startToEndAngle Then side = 3 Else side = 0

ElseIf startToEndAngle.Equals(Pi / 3, 10) Then
If startToHexagonAngle > startToEndAngle Then side = 2 Else side = 5

ElseIf startToEndAngle.Equals(2 * Pi / 3, 10) Then
If startToHexagonAngle > startToEndAngle Then side = 4 Else side = 1

ElseIf startToEndAngle.Equals(Pi, 10) Then
If startToHexagonAngle > startToEndAngle Then side = 0 Else side = 3

ElseIf startToEndAngle.Equals(4 * Pi / 3, 10) Then
If startToHexagonAngle > startToEndAngle Then side = 5 Else side = 2

ElseIf startToEndAngle.Equals(5 * Pi / 3, 10) Then
If startToHexagonAngle > startToEndAngle Then side = 1 Else side =4

Else
MessageBox("It is not one of the special case")
End If
``````

I would treat the situation where

when the line crosses exactly the common border of two hexagons.

As a special case and use code like the above to deal with this special case.

Youâ€™re right Robert, startVector should be calculated as:

``````Var hexagonToStartVector As New Point(hexagon.X - p1.X, hexagon.Y - p1.Y)
``````

But Iâ€™m still having a big problem when line passes exactly through the border. This happens when the line is horizontal or NE, NW, SW, SE. Some hexagons have, in this case, two borders touched by the line.

The example from 0303 to 0405 gives those entering borders:
11:05:14 : PB Launched
11:05:25 : 0304-0
: 0404-4
: 0405-0
Assuming 0 is the hexagon top side

The results are correct but insufficient because 0304 should have also border 1 touched by the line, and 0404 the same, so the result should be:

0304 - 0 and 1
0404 4 and 5
0405 0 and 5

Can you aply a little offset to the centers just when doing your calculations? a little to the left for the starting point and to the right for the ending one.

Can you aply a little offset to the centers just when doing your calculations? a little to the left for the starting point and to the right for the ending one.

This is a major change, I should call five times the method that gets the crossed hexagons, one for the normal center to center then four other cases with displacing the y +/- delta and displacing the x +/- delta.

``````var delta as integer = 4
for offset as integer = 0 to 4
' 0 normal call
if offset = 1 then
p1.y = p1.y+delta
elseif offset = 2 then
p1.y = p1.y-delta
elseif offset = 3 then
p1.x = p1.x+delta
elseif offset =4 then
p1.x = p1.x-delta
end if
End for
``````

Then the array that keeps the hexes crossed must be changed to accept same hex with diferent border.

``````Private Sub AddToArray(x as integer, y as integer)
Var row, col as integer
x = x + mw.HorizontalScrollBar.Value
y = y + mw.VerticalScrollBar.Value
mw.BoardMap.PointToHex(x,y,row,col)
var hex as string = Terrain.RowColToHex(row,col)

if LosHexes.IndexOf(hex) = -1 then
end if
End Sub

``````

Itâ€™s a possibility, not seems the most elegant, but Iâ€™ll try this in a separate project.

But not 0304 - 2 ?
But not 0404 - 3 ?

I think I understand your definition of â€śenter sideâ€ť.

Basically, we are going to identify the â€śspecialâ€ť circumstances that result in a connecting line between the start and the end hexagons that runs exactly through the common side of two adjacent hexagons.

Then divide the special cases into the 6 relevant directions (NE, NW, SE, SW, WEST, EAST) and for each one considered separately write the code that places the â€śenter sideâ€ť into a data structure that is created for this purpose (a dictionary) of all the titled hexagons.

``````// Screw trigonometry functions
// dealing with the special case of the connecting line passes exactly through borders
Const VERY_SMALL As Double = .000001

Var distanceStartEnd As Double
// the side of a hexagon is the unit distance (1)

// Example values for the start and end hexagon are provided.
Var rStart, cStart As Integer // row and column of the start hexagon
Var rEnd, cEnd As Integer // row and column of the end hexagon
rStart = 7
cStart = 6
rEnd = 2
cEnd = 3

// We are defining a side of a hexagon as having the unit value 1
// This will be the distance between the centers of the example hexagons
distanceStartEnd = 9 // in this example case

Var iDistanceStartEnd As Integer

// identify whether these start and end hexagons are a special case with connecting line passing exactly through borders
Var qualify As Boolean // does it qualify as a special case?

iDistanceStartEnd = Round(distanceStartEnd)
// should be an integer value if the side is considered to be 1
If Abs(iDistanceStartEnd - distanceStartEnd) < VERY_SMALL Then qualify = True Else qualify = False

// The distances should be a multiple of 3 between qualifying end and start hexagons.
If iDistanceStartEnd Mod 3 = 0 And qualify Then
qualify = True
Else
qualify = False
End If

// now figure out the "entry" sides for the involved hexagons between the start and end hexagon.
If qualify Then // the start/end pair of hexagons qualify

// the angled directions
Var NW, NE, SE, SW, WEST, EAST As Boolean

If rStart > rEnd And cStart > cEnd Then
NW = True
End If
If rStart > rEnd And cStart < cEnd Then
NE = True
End If
If rStart < rEnd And cStart > cEnd Then
SW = True
End If
If rStart < rEnd And cStart < cEnd Then
SE = True
End If
If rStart = rEnd And cStart > cEnd Then
WEST = True
End If
If rStart = rEnd And cStart < cEnd Then
EAST = True
End If

Var totRow, totCol As Integer // whatever values fill the case at hand. - Example
totRow = 8
totCol = 8
// Var hex(-1, -1) As Integer
// hex.ResizeTo(totRow, totCol)

Var theValue As String

// create a structure (a dictionary) that will hold all the "entry sides" for a given hexagon
// dHex.Value("05*04") might be "3-4"
Var dHex As New Dictionary
Var sRow, sCol As String
For nRow As Integer = 0 To totRow
sRow = Format(nRow, "00")

For nCol As Integer = 0 To totCol
sCol = Format(nCol, "00")
theValue = sCol + "*" + sRow
dHex.Value(theValue) = ""
Next nCol

Next nRow

Var incrementRow As Integer // the rows of hexagons on a diagonal increment or decrement in a pattern 1, 2, 1, 2, 1 etc.
// within a row there is a pattern with (in this example) the even column hexagons are higher than their odd column row members
Var upHex As Boolean // up or down relative to some others in the row

// NW
If NW Then

If cStart Mod 2 = 0 Then upHex = True // even columns have "high" rows
If upHex Then incrementRow = -2 Else incrementRow = -1
Var jRow As Integer = rStart

For jCol As Integer = cStart To cEnd Step -1

// the hexagon directly above
sRow = Format(jRow - 1, "00")
sCol = Format(jCol, "00")
dHex.Value(sCol + "*" + sRow) = "3" + "-" + "4"

// the hexagon above and to the left
If upHex Then
sRow = Format(jRow - 1, "00")
Else
sRow = Format(jRow, "00")
End If
sCol = Format(jCol - 1, "00")
dHex.Value(sCol + "*" + sRow) = "1" + "-" + "2"

// move on to the next hexagon with line through its center
jRow = jRow + incrementRow

upHex = Not (upHex)
If upHex Then incrementRow = -2 Else incrementRow = -1

Next jCol

End If

// Write similar custom code for each of the other
// WEST and EAST are simplest, NE, SE, SW are analogous to what has been provided for NW
// NE
// SE
// SW
// WEST
// EAST

End If
``````

Thanks Robert,
Thatâ€™s rightâ€™s you said, I need only the side from where the line ENTER the hexagons.
Iâ€™ll study your code and try to replicate for each direction.

Hi Robert,

Iâ€™ trying to use your code, and just started Iâ€™ve a question,

``````// Example values for the start and end hexagon are provided.
Var rStart, cStart As Integer // row and column of the start hexagon
Var rEnd, cEnd As Integer // row and column of the end hexagon
rStart = 7
cStart = 6
rEnd = 2
cEnd = 3
``````

in your example the hexagons translated to my coordinates system â€śCCRRâ€ť:
0607 to 0302

``````// We are defining a side of a hexagon as having the unit value 1
// This will be the distance between the centers of the example hexagons
distanceStartEnd = 9 // in this example case
``````

But the distance is 6, and why the side is 1?

(You count how many radius?) so hex 0302 count as 1 but hex 0404 count as 2?

In the special case situation, the distance between 0302 and 0607 is 9. From the center of 0302 to its edge is 1 (the length of a side). The distance from that edge to the edge of 0404 is 1 (the length of a side). The distance across the entirety of 0404 is 2. The distance from the edge of 0404 to the edge of 0505 is 1. The distance across the entirety of 0505 is 2. The distance from the edge of 0505 to the edge of 0607 is 1. The distance from the edge of 0607 to the center of 0607 is 1.

If you add up all these things then you get 9 which is the distance from the center of 0302 to the center of 0607.

Well that is not a special case and that line measurement will be not be a simple integer. It will have to be calculated as the distance between two points:

`Sqrt((P0303.X - P0707.X) ^ 2 + (P0303.Y - P0707.Y) ^ 2)`

I assumed from your original post that you had already established the Points that define the center of all the hexagons. That work cannot be abandoned.

For the grid of hexagons, the center of one of them will have to be declared as the 0, 0. Letâ€™s say we decide on your first image that the center of 0306 is going to be the 0,0 point. It is easy to establish the center point of 0305. The distance from the center of a hexagon of side = 1 to the center of and edge is

Sqrt(3) / 2 : That is the height of an equilateral triangle of side 1

and for simplicity of reference we will call that h.

The center point of 0305 will be 0, 2 * h. The center point of 0304 will be 0, 4 * h. etc. as you move up the column. How about moving to the next column?

The center point of 0406 is (1.5, h)
The center point of 0407 is (1.5, -h)
The center point of 0405 is (1.5, h + 2 * h) or (1.5, 3 * h)

The center point of 0505 is (3, 2 * h)
The center point of 0504 is (3, 4 * h)

The pattern should become evident. The centers of all the hexagons in the grid can be determined in this coordinate system.

Moving on to your second diagram, if we adhere to the coordinate system that we established in my last entry:

The center of 0303 is (0, 6 * h)

The center of 0702 is (6, 8 * h)

The distance between them would be

Sqrt( 6 ^ 2 + (2 * h) ^ 2)

In my original post, I failed to deal with the hexagons that are bisected by the line between start and end. I have added the code below to include these.

For jCol As Integer = cStart To cEnd Step -1

``````// the hexagon itself
sRow = Format(jRow, "00")
sCol = Format(jCol, "00")
dHex.Value(sCol + "*" + sRow) = "2" + "-" + "3"
``````

// the hexagon directly above
sRow = Format(jRow - 1, â€ś00â€ť)
sCol = Format(jCol, â€ś00â€ť)
dHex.Value(sCol + â€ś*â€ť + sRow) = â€ś3â€ť + â€ś-â€ť + â€ś4â€ť

// the hexagon above and to the left
If upHex Then
sRow = Format(jRow - 1, â€ś00â€ť)
Else
sRow = Format(jRow, â€ś00â€ť)
End If
sCol = Format(jCol - 1, â€ś00â€ť)
dHex.Value(sCol + â€ś*â€ť + sRow) = â€ś1â€ť + â€ś-â€ť + â€ś2â€ť

// move on to the next hexagon with line through its center
jRow = jRow + incrementRow

upHex = Not (upHex)
If upHex Then incrementRow = -2 Else incrementRow = -1

Next jCol

``````// deal with the start hexagon which does not have an entry side(s)
sRow = Format(rStart, "00")
sCol = Format(cStart, "00")
dHex.Value(sCol + "*" + sRow) = "start"

// deal with the end hexagon as you see fit. I am not sure if you track entry side(3)
sRow = Format(rEnd, "00")
sCol = Format(cEnd, "00")
// ?? dHex.Value(sCol + "*" + sRow) = "end"
``````

hello Enric Herrera,
My simple way to determine the direction from the center to the entry point without any major calculations

https://www.dropbox.com/scl/fi/6kzccuqn19gndxw4alrh3/test-direction-Point.xojo_binary_project?rlkey=4d87tiq18rka7s1026vxq47zt&dl=1