javascript - Efficient algorithm for finding which hexagon a point belongs to - Stack Overflow

admin 管理员组

文章数量: 1086019

I'm trying to find a more efficient way of determining which hexagon a point belongs to from the following:

1. an array of points - for the sake of argument, 10000 points.
2. an array of center points of hexagons, approximately 1000 hexagons.
3. every point will belong to exactly one hexagon, some (most) hexagons will be empty.
4. The hexagons form a perfect grid, with the point of one hexagon starting in the top left corner (it will overlap the edge of the total area).

My current solution works, but is rather slow n * (m log m) I think, where n=length(points) and m=length(hexagons).

I suspect I can do much better than this, one solution that es to mind is to sort (just once) both the points and the hexagons by their distance to some arbitrary point (perhaps the middle, perhaps a corner) then iterate over the points and over a subset of the hexagons, starting from the first hexagon whose distance to this point is >= to the last hexagon matched. Similarly, we could stop looking at hexagons once the distance difference between the (point -> ref point) and (hexagon center -> ref point) is larger than the "radius" of the hexagon. In theory, since we know that every point will belong to a hexagon, I don't even have to consider this possibility.

My question is: Is there a Much better way of doing it than this? In terms of plexity, I think it's worst case bees marginally better n * m but the average case should be very good, probably in the region of n * 20 (e.g., we only need to look at 20 hexagons per point). Below is my current inefficient solution for reference.

points.forEach((p) => {
  p.hex = _.sortBy(hexes, (hex) => {
    const xDist = Math.abs(hex.middle.x - p.x);
    const yDist = Math.abs(hex.middle.y - p.y);
    return Math.sqrt((xDist * xDist) + (yDist * yDist));
  })[0];
});

I'm trying to find a more efficient way of determining which hexagon a point belongs to from the following:

1. an array of points - for the sake of argument, 10000 points.
2. an array of center points of hexagons, approximately 1000 hexagons.
3. every point will belong to exactly one hexagon, some (most) hexagons will be empty.
4. The hexagons form a perfect grid, with the point of one hexagon starting in the top left corner (it will overlap the edge of the total area).

My current solution works, but is rather slow n * (m log m) I think, where n=length(points) and m=length(hexagons).

I suspect I can do much better than this, one solution that es to mind is to sort (just once) both the points and the hexagons by their distance to some arbitrary point (perhaps the middle, perhaps a corner) then iterate over the points and over a subset of the hexagons, starting from the first hexagon whose distance to this point is >= to the last hexagon matched. Similarly, we could stop looking at hexagons once the distance difference between the (point -> ref point) and (hexagon center -> ref point) is larger than the "radius" of the hexagon. In theory, since we know that every point will belong to a hexagon, I don't even have to consider this possibility.

My question is: Is there a Much better way of doing it than this? In terms of plexity, I think it's worst case bees marginally better n * m but the average case should be very good, probably in the region of n * 20 (e.g., we only need to look at 20 hexagons per point). Below is my current inefficient solution for reference.

points.forEach((p) => {
  p.hex = _.sortBy(hexes, (hex) => {
    const xDist = Math.abs(hex.middle.x - p.x);
    const yDist = Math.abs(hex.middle.y - p.y);
    return Math.sqrt((xDist * xDist) + (yDist * yDist));
  })[0];
});

• javascript
• sorting
• putational-geometry

Share Improve this question Follow asked May 22, 2019 at 16:44 Zack NewshamZack Newsham 3,00222 gold badges2626 silver badges4545 bronze badges 8

• 4 Does redblobgames./grids/hexagons/#pixel-to-hex address what you are looking with by demonstrating a square grid coordinate to hex mapping via formula? – Jason Aller Commented May 22, 2019 at 16:50
• That is extremely cool - I'm not 100% sure but I'll absolutely take a look - I started looking into QuadTrees as that might do it, but it looks like it might be less efficient – Zack Newsham Commented May 22, 2019 at 17:03
• @JasonAller wow, that resource is fabulous! – Bergi Commented May 22, 2019 at 20:51
• 10000 points in 1000 hexagons and most hexagons empty does not sound correct. – user1196549 Commented May 23, 2019 at 16:44
• If the grid is regular, you can pute in time O(1) the tile index(es) for an arbitrary point. Hence O(n) for the n points. No preprocessing required. – user1196549 Commented May 23, 2019 at 16:46

 |  Show 3 more ments

4 Answers 4

Sorted by: Reset to default 2

Update: Leaving the below ment for posterity

I am now using the code provided here: https://www.redblobgames./grids/hexagons/

A really important note, is that your hexagon grid MUST start with the first hexagons mid point at (0, 0) - if it doesn't you get extremely odd results from this, which at first glance appeared as rounding errors (even after accounting for the expected offset). For me, it didn't matter where the first hexagon was positioned, so I just set it to be (0, 0) and it worked great.

Old solution

I'm still hoping for an optimal solution, but I ended up rolling my own which needs only check 6 hexagons per point, with a little overhead (approximately sqrt(m)) needed in addition.

With approximately 3000 points, and 768 hexagons (of which 310 were populated), it correctly assigned the point to the hexagon 100% of the time (as checked against a brute force approach) and took 29 milliseconds, pared to ~840 with brute force.

To start with, I store the hexagons in a map where the key is "${column},${row}". The columns technically overlap, so for the 0th row, the 0th column starts at -0.5 * hexWidth, and for row 1, the 0th column starts at 0px.

Next, I start from the position of the top left hexagon, item "0,0", which should also be at position 0, and increment y by either the height of the hexagon, or the edge length of the hexagon accordingly. When the y is > the points y, I've found the probable row, I then check the row above and below.

For the column within the row, I take the both the Math.floor and Math.ceil of x / hexWidth.

Doing this gives 6 hexagons to check, from this point the solution is identical to the solution in the question.

In theory, this could be used to just look up the correct hexagon, using the x/y position. However in practice, this didn't work for me about 5% of the time with off by 1 errors, likely a rounding problem.

Some other things I looked at:

1. As suggested by @jason-aller, https://www.redblobgames./grids/hexagons/#rounding. Unfortunately, this seems to assume some form of transformation on the hex grid (rotations) and is not easy to follow - continually referencing functions which have yet to be defined.

2. QuadTree (various implementations) unfortunately, this returned approximately 100 "potential matches" for each point - so the performance improvement was not good. I'm aware that insertion order changes how useful QuadTree is, I tried natural order, sorted by distance from top, left and shuffled, they all performed equally badly. It's likely that an optimal solution with QuadTree would involve populating the tree with the item closest to the mid point, then the items 1/2 from the mid point to each corner, recursively. Too much like hard work for me!

For an arbitrary point, you can find the nearest hexagon center in two steps (assuming the same arrangement as that of Futurologist):

• divide the abscissa by the horizontal spacing between the centers, and round to the nearest integer.

• divide the ordinate by the half of the vertical spacing, and round to the nearest even or odd integer, depending on the parity found above.

• consider this center and the six ones around it, and keep the closest to the target point.

This gives you the indexes of the tile, in constant time.

Just a suggestion: assume you have the centers of each regular hexagon from your regular hexagonal grid (if I have understood correctly, that's part of the information you have).

         -----
       /       \
           -     -----        -----------> x - axis
       \       /       \
         -----     -    
       /       \       /
           -     -----
       \       /       \
         -----     -    
           |   \       /
           |     ----- 
           |  
           |          
           V
        y - axis

You can think that your coordinate system starts from the center of the hexagon in the upper left corner and the y coordinate axis runs vertically down, while the x axis runs from left to right horizontally. The centers of the hexagons from your regular hexagonal grid form an image of the regular square grid, where the integer vertices of the square grid are transformed into the centers of the polygons by simply multiplying the coordinates of points in the square grid by the 2 x 2 square matrix (a sheer metrix)

A = a*[ sqrt(3)/2    0;

          1/2        1 ]

where a is a parameter of the hexagonal grid, the distance between the centers of two edge-adjacent hexagons. This provides a way to assign integer indices [m n] to the grid formed by the hexagonal centers. After that, if you are given a point with coordinates [x y] in the hexagonal grid, you can apply the inverse matrix of A

 [u; v] = A^(-1)*[x; y] 

where 

A^(-1) = (2/(a*sqrt(3)))*[  1           0   ;

                           -1/2   sqrt(3)/2 ]

([x; y] and [u; v] are column vectors) and then take m = floor(u) and n = floor(v) to determine the integer coordinates (also the indices) [m = floor(u), n = floor(v)] of the upper left corner of the square cell from the square grid (observe that we have chosen the coordinates for both grids to start from the upper left corner). Thus, your point [u, v] is in the square with vertices [m,n] [m+1, n] [m, n+1] [m+1, n+1] which means that the original point [x y] is in one of the four hexagons whose centers have indices [m,n] [m+1, n] [m, n+1] [m+1, n+1]. So you can use that to check in which of the four hexagons the point [x y] is.

I hope this helps.

You can search a 2d space efficiently with quadtrees. Essentially it's like a binary search of a 1d space expanded to 2 dimensions. For each point you're searching it should take log(n) time to search for which hexagon it goes to if you first build a quadtree out of the n hexagons that tesselate your search area.

本文标签： javascriptEfficient algorithm for finding which hexagon a point belongs toStack Overflow