2

My object is constructed in a honeycomb grid. All objects are connected. The red lines represents the connection between each node. I heard Binary Space Partitioning (BSP) Trees is good with this type of problem, but not sure what is front and back in my case.

I've implemented the lookup using the honeycomb grid system as shown (x , y)

class Node {
    Point position; //center position
    Point grid; //honeycomb grid system
}

class MyObject {
    Node lookup(Point grid);
}

I need a data structure that represent the graph as user add more nodes onto the scene and a way to quickly determine if a grid point is (against MyObject): 1. outside 2. inside 3. inside a hole

enter image description here

docchang
  • 1,115
  • 15
  • 32
  • 3
    I need my delicious morning coffee, but I'm not sure how to work the coffee machine in Costa, however I could attempt to make a coffee before asking for help when I inevitably get grounds and milk on the ceiling. You need to do the same for your question - show what you've tried so far, whether that's code (best) or any research you've done – Bojangles Nov 27 '13 at 08:10
  • If you want to use ready implementation boost provides geometry library. – Aleksander Fular Nov 27 '13 at 08:20
  • Knowing a bit more about the larger problem might shed more light on the best solution. – Dwayne Towell Nov 27 '13 at 08:24
  • @AleksanderFular boost is not available on my platform. However, C++11 std stuff is okay. – docchang Nov 27 '13 at 08:26
  • @Bojangles The code I have so far is just a list of line segments that are drawn in the picture. I figured there isn't very helpful to the question. – docchang Nov 27 '13 at 08:39
  • When this is a question about an algorithmic problem there isn't much need for code anyway, but specifying [tag:c++] doesn't make sense then either. – moooeeeep Nov 27 '13 at 08:47
  • Is performance a concern? If not, just calc (square of) distance to each hex tile, find smallest, figure out if your point is in that hex or outside it. Also, get it working first with "dumb" solution, then replace with better, is often good approach when you are unsure what you are doing. – hyde Nov 27 '13 at 09:03
  • Is _outside the graph_ == _within a hole_? (Put differently, do you need to distinguish the state whether the point is entirely surrounded by node connections or not?) – moooeeeep Nov 28 '13 at 10:21
  • No, I need to make an distinguish between outside and within a hole. The user will create the nodes one at a time. I'm trying to find ways to build a data structure so that I can easily determine (outside, inside, inside a hole) when a given grid point is given. – docchang Nov 30 '13 at 01:07

2 Answers2

0

How big is the space you're working in?

Simulate the whole thing with a simple rectangular grid assuming even-rows are staggered right.

Any node has coordinates [x,y]

  • For (y%2 == 0) neighbor nodes are [x-1,y][x+1,y][x,y+1][x,y-1][x-1,y-1][x-1,y+1]
  • For (y%2 == 1) neighbor nodes are [x-1,y][x+1,y][x,y+1][x,y-1][x+1,y-1][x+1,y+1]

Each node can be full or empty and empty nodes can be checked or not checked. Originally all empty nodes are not checked.

Check if a node belongs to a hole by:

  • if node is full - it does not belong to hole, it belongs to the shape.
  • if a node is empty mark node as checked.
  • Iterate over all neighbor nodes:
    • Skip nodes marked as checked or full
    • recursively repeat the search for all nodes not checked.
  • If the recursion brings you into any x<0, y<0, x>MAX_X, y>MAX_Y, abort. The node is outside the shape
  • If the recursion ends without finding edges of the playfield, the node belongs to a hole.

Additionally, you may now repeat the procedure turning all checked nodes into outside or hole for later reference.

If you want to index all holes at start, it may be easier to find all not checked empty nodes at borders of the playfield (x==0, y==0, x==MAX_X, y==MAX_Y) and use the above algorithm to mark them as outside. All remaining empty nodes are holes.

Depending on your grid size, you may implement it as 2D array of structs/objects containing object state (or even chars, with status as bits of the number), sized [MAX_X+1][MAX_Y+1] if it's reasonably sized, or as a list (vector) of full nodes, each containing its coords, status and if you want this to be more speed-optimal, neighbors. In this case, search the shape, finding all empty neighbor nodes for potential holes. Edge nodes with extreme coords (lowest/highest x/y) belong to "outside". Follow their empty neighbors that have full neighbors, to find the outer edge of the shape. All remaining are inner edges and after following the algorithm starting with them you'll have all your "holes".

SF.
  • 13,549
  • 14
  • 71
  • 107
0

My suggestion:

  • Assign each tile a center position in a 2d cartesian space.
  • Build a binary search tree (BST) containing all center positions.
  • For a query point find the relative position to the nearest occupied tile using that BST.
  • Determine whether that position is inside or outside the tile using some geometric formula, e.g., as in here:

Alternatively, work with an approximation using squares, e.g., as seen here:

Community
  • 1
  • 1
moooeeeep
  • 31,622
  • 22
  • 98
  • 187