Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

hexagon coordinates

In my program, it draws them by offsetting every other row by half of the width, as pictured above. Each tile can be referenced by coordinates, also shown above.

hexagon roads

I want to know how many blue tiles are accessible from a certain starting tile and a series of "roads." In this example, three blue tiles can be reached.

How would I represent roads? This is what I would need to know about it:

  • how it is rotated (for drawing)
  • which hexagons it borders
  • which other roads it touches, if any
  • where it should be drawn

I assume I could use recursion to to count the accessible blue squares if the above conditions are met.

share|improve this question
    
How are the blue tiles given? –  A.Schulz Dec 9 '12 at 16:28
    
Each tile is an object with a variable telling whether it is blue or not. These objects are assembled into a two-dimensional array in a Board class. –  tyjkenn Dec 9 '12 at 19:27
    
What's the context-- how do you define "reachability"-- max.number of hops-- hexagon sides between consecutive blue tiles ? is the entire graph known or is it discovered as you go ? any restrictions on traversing the hexagon edges ? Not allowing me to write comments here yet. –  ashley Dec 10 '12 at 22:13
    
The three that can be reached have roads connecting them to the starting tile. The blue tile on the bottom row cannot be reached because there are no roads connecting it to the starting tile. If you could only "walk" on the black roads, how many blue tiles could you walk to if you start at the starting tile? –  tyjkenn Dec 10 '12 at 23:27
    
Assume the entire graph is known, and the length of the path is irrelevant. All I need to know is if it is possible. The only edges you can traverse are the ones with roads (represented by the bold black) –  tyjkenn Dec 11 '12 at 0:36
add comment

2 Answers

up vote 3 down vote accepted
+50

Let us first calculate the coordinates $C(m,n)$ of the center of hexagon $(m,n)$. We assume that the origin is at the center of hexagon $(0,0)$ and that the hexagon radius (distance from center to vertex) is $r$. A short calculation shows that hexagon $(1,0)$ has its center at $$C(1,0) = a = (\sqrt{3} r, 0)$$ and hexagon $(0,1)$ has its center at $$C(0,1) = b = (\sqrt{3} r/2, 3 r/2).$$ Therefore, hexagon $(m,n)$ has its center at $$C(m,n) = m \cdot a + n \cdot b = (\sqrt{3} r (m + n/2), 3 r n / 2).$$ Notice that we should allow negative $m$ and $n$ if we want to cover the whole plane.

To get from the center $C(m,n)$ to one of the adjacent centers we need to add to $C(m,n)$ one of the vectors $a$, $b$, $-a$, $-b$, $a - b$, or $b - a$. (If we add $a + b$ or $-a-b$ we go too far). If we travel half the distance we will end up exactly in the midpoint of a side. Therefore, midpoints of sides have coordinates of the form $$C(m+1/2, n), C(m,n+1/2), C(m-1/2,n), C(m,n-1/2), C(m+1/2,n-1/2), C(m-1/2,n+1/2).$$ We have discovered how to encode sides: just use half-integer coordinates. But this is silly, it is better to multiply everything by two, which leads to the following system.

We represent both hexagons and sides as pairs of integers $(m,n)$. When $m$ and $n$ are both even this encodes a hexagon whose center is at $$C(m/2,n/2) = (m \cdot a + n \cdot b)/2.$$ If either $m$ or $n$ is odd then $(m,n)$ represents a side of a hexagon whose midpoint is at $C(m/,n/2)$.

It is also easy to tell which two hexagons a given side belongs to: the side $(2 i + 1, 2 j)$ belongs to hexagons $(2 i, 2 j)$ and the side $(2 i + 2, 2 j)$, while the side $(2 i, 2 j + 1)$ belongs to hexagons $(2 i, 2 j)$ and $(2 i, 2 j + 2)$.

Similarly, the sides of hexagon $(2 i, 2 j)$ are: $(2 i + 1, 2 j)$, $(2 i - 1, 2 j)$, $(2 i, 2 j + 1)$, $(2 i, 2 j - 1)$, $(2 i + 1, 2 j - 1)$ and $(2 i - 1, 2 j + 1)$.

We now have a good system for representing hexagons and sides as pairs of integers. We still need to solve the original problem, namely which blue hexagons are reachable from a starting hexagon by traveling along certain "black" paths. This is a graph-theoretic reachability problem if we think of sides as edges in a graph and their endpoints as vertices of a graph (as we reach each black side we verify whether it belongs to a blue hexagon). Many algorithms are known on how to solve this. Let me know if you need more details.

share|improve this answer
    
I will have my bounty now, thank you ;-) –  Andrej Bauer Dec 14 '12 at 13:31
add comment

You could represent a road as a list of the two faces involved. Given a road and a hexagon, you can explicitly calculate the roads next in order clockwise or counterclockwise on the hexagon. That way you can find all the neighbours on both sides.

This suggestion is attributed to the hypermap community by Gonthier et al., where it is called "dart" or "flag" (see pages 18-19).

share|improve this answer
    
Each road actually touches up to four hexagons, one at each end, and one on each side. Could you please elaborate? I don't know if I'm quite following. –  tyjkenn Dec 12 '12 at 21:26
    
Each road borders at most two hexagons. –  Yuval Filmus Dec 12 '12 at 21:31
    
Oh, It think I understand what you are saying: check if the road goes left by "wrapping" counter-clockwise around the left hexagon, and check if the road goes right by wrapping clockwise around the right hexagon, marking each road as visited. How would you distinguish between the left and right tiles? How would this setup be initialized? The starting tile and blue tiles would still need to be able to find even when it is only connected at a corner. –  tyjkenn Dec 12 '12 at 22:50
    
There are no "left and right" tiles. For any reasonable definition of "left and right", you will be able to distinguish between them by looking at the coordinates of the hexagon. For constructing the data structure, I would consult the example configuration in your question, write down the six "edge types", and then use some loops. –  Yuval Filmus Dec 13 '12 at 8:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.