Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.graphics.algorithms > #314 > unrolled thread

Honeycomb tiling algorithm

Back to article view | Back to comp.graphics.algorithms

Contents

  Honeycomb tiling algorithm Tiron <weston17@gmail.com> - 2011-08-10 14:55 -0700
    Re: Honeycomb tiling algorithm Nobody <nobody@nowhere.com> - 2011-08-11 08:30 +0100
      Re: Honeycomb tiling algorithm Tiron <weston17@gmail.com> - 2011-08-11 12:48 -0700
        Re: Honeycomb tiling algorithm Nobody <nobody@nowhere.com> - 2011-08-12 04:48 +0100
    Re: Honeycomb tiling algorithm Kaba <kaba@nowhere.com> - 2011-08-12 01:23 +0300

#314 — Honeycomb tiling algorithm

I'm trying to come up with an algorithm to calculate the points for
the vertices of a honeycomb pattern, to be used as a tile. Basically,
given any arbitrary tile size, I need to produce a single honeycomb
pattern inside of it so that it can then be tiled to produce a
seamless honeycomb pattern across the screen. These need to be
equilateral hexagons.

I've been able to implement a rudimentary version of this myself, but
I'm quite sure I'm doing it wrong because I can't seem to manage an
equilateral hexagon. Does anyone know the preferred method for this?

[toc] | [next] | [standalone]

#315

On Wed, 10 Aug 2011 14:55:04 -0700, Tiron wrote:

> I'm trying to come up with an algorithm to calculate the points for
> the vertices of a honeycomb pattern, to be used as a tile. Basically,
> given any arbitrary tile size, I need to produce a single honeycomb
> pattern inside of it so that it can then be tiled to produce a
> seamless honeycomb pattern across the screen. These need to be
> equilateral hexagons.
> 
> I've been able to implement a rudimentary version of this myself, but
> I'm quite sure I'm doing it wrong because I can't seem to manage an
> equilateral hexagon. Does anyone know the preferred method for this?

Are you talking about rectangular tesselation? If so, then for equilateral
hexagons, the rectangles need an aspect ratio of 3 / sqrt(3) ~= 1.732, or
a rational multiple thereof.

If the tile dimensions are constrained to an integral number of pixels,
then you can't get an exact equilateral hexagon, only an approximation
(97/56 is ~53ppm).

[toc] | [prev] | [next] | [standalone]

#320

We are actually trying to use this in a vector scenario. So we can
specify sub-pixel coordinates as points in the vector coordinate
system. And the tiles will get rasterized with anti-aliasing when we
do a pattern fill.

Given that, to produce a perfect equilateral honeycomb pattern using
only a single tile rendered over and over again across the screen,
what would the formula be to calculate each point on the honeycomb
shape. Additionally, to make sure it is a perfect honeycomb shape,
what kind of requirements would I need to have on the tile sizes?

On Aug 11, 1:30 am, Nobody <nob...@nowhere.com> wrote:
> On Wed, 10 Aug 2011 14:55:04 -0700, Tiron wrote:
> > I'm trying to come up with an algorithm to calculate the points for
> > the vertices of a honeycomb pattern, to be used as a tile. Basically,
> > given any arbitrary tile size, I need to produce a single honeycomb
> > pattern inside of it so that it can then be tiled to produce a
> > seamless honeycomb pattern across the screen. These need to be
> > equilateral hexagons.
>
> > I've been able to implement a rudimentary version of this myself, but
> > I'm quite sure I'm doing it wrong because I can't seem to manage an
> > equilateral hexagon. Does anyone know the preferred method for this?
>
> Are you talking about rectangular tesselation? If so, then for equilateral
> hexagons, the rectangles need an aspect ratio of 3 / sqrt(3) ~= 1.732, or
> a rational multiple thereof.
>
> If the tile dimensions are constrained to an integral number of pixels,
> then you can't get an exact equilateral hexagon, only an approximation
> (97/56 is ~53ppm).

[toc] | [prev] | [next] | [standalone]

#322

On Thu, 11 Aug 2011 12:48:06 -0700, Tiron wrote:

> We are actually trying to use this in a vector scenario. So we can
> specify sub-pixel coordinates as points in the vector coordinate
> system. And the tiles will get rasterized with anti-aliasing when we
> do a pattern fill.
> 
> Given that, to produce a perfect equilateral honeycomb pattern using
> only a single tile rendered over and over again across the screen,
> what would the formula be to calculate each point on the honeycomb
> shape. Additionally, to make sure it is a perfect honeycomb shape,
> what kind of requirements would I need to have on the tile sizes?

The vertices of a unit hexagon are:

	(1,0), (1/2,s), (-1/2,s), (-1,0), (-1/2,-s), (1/2,-s)

where s = sin(pi/3) = sqrt(3)/2 ~= 0.866

Its bounding box has a width of 2 and a height of 2s = sqrt(3) ~= 1.732.

A honeycomb pattern has 3 axes of translational symmetry:

	(-3/2,s), (-3/2,-s), (0,2s)

[These are the edges of an inscribed hexagram.]

For parallelogram tessellation, you can choose any two of these for the
tiling grid. For rectangular tesselation, add the first two together (so
that each tile has twice the area of a hexagon) to give:

	(-3,0), (0,2s)

I.e. the tiling grid will consist of rectangles 3 units wide and
sqrt(3) ~= 1.732 units high.

The tiles will look something like:

        +--------------------+
        |   o------o         |
        |  /        \        |
        | /          \       |
        |o            o------|
        | \          /       |
        |  \        /        |
        +--------------------+

[toc] | [prev] | [next] | [standalone]

#321

Tiron wrote:
> I'm trying to come up with an algorithm to calculate the points for
> the vertices of a honeycomb pattern, to be used as a tile. Basically,
> given any arbitrary tile size, I need to produce a single honeycomb
> pattern inside of it so that it can then be tiled to produce a
> seamless honeycomb pattern across the screen. These need to be
> equilateral hexagons.

A little trigonometry shows that if the sidelength of a regular hexagon 
is s, then the honeycomb vertices can be given by the help of the 
following functions:

x : ZZ --> RR: x(i) = floor(i / 2) (3 / 2) s + (i mod 2) (1 / 2) s
y : ZZ --> RR: y(j) = j (sqrt(3) / 2) s,

where ZZ is for integers, and RR is for real numbers.

(x(i), y(j)) is a honeycomb vertex if and only if
     i mod 4 <= 1 and j mod 2 = 0, or
     i mod 4 > 1 and j mod 2 = 1.

For example, if i and j are both even, then the vertices of one hexagon 
is given by

H = {
(x(i), y(j)),
(x(i + 1), y(j)),
(x(i + 2), y(j + 1)),
(x(i + 1), y(j + 2)),
(x(i), y(j + 2)),
(x(i - 1), y(j + 1))
}

Of course, the honeycomb pattern can be transformed by an orthogonal 
transfomation if needed.

-- 
http://kaba.hilvi.org

[toc] | [prev] | [standalone]

Back to top | Article view | comp.graphics.algorithms

csiph-web