Finding neighbours on an arbitrary polygon grid

[Rishavs]

Hi

I have a grid composed of convex polygons with variable sides. SOmething similar to voronoi plots.

For any face/polygon i want to find all its neighbouring polygons (which share a side).
For regular grids made of rectangles, triangles, heaxgons wtc, we can simply employ an indexing system which gives their position and neighbour.

But the same is not possible in an irregular grid which i made of polygons of all sizes and shapes.
Currently I am iterating through all polygons and doing an intersection test with each of them which is very inefficient.

Is there any generic way of finding the neighbours of any polygon?

[Tanner]

There is no algorithmic solution to your problem because of the irregular nature of your shapes. The solution you will want to employ is to create a list of the neighbouring polygons when you build the graph or employ some form of spatial hash to narrow your search size.

[vrld]

I'm afraid you will have to check every polygon.

However, you can speed up the intersection tests by computing the outcircle of each polygon (has to be done only once) and test whether the outcircles intersect (centroid-distance < sum-of-radii). If they don't, you know the polygons will not share a side.

You can also store the vertices and edges of the polygons in separate tables. The vertex-list contains all vertices of all polygons, but each vertex only once. The edge list contains indices to the vertex list instead of the vertex positions. That way, you can check whether two polygons share an edge by a simple if statement.

For example (untested):

Code: Select all

vertices = { {0,0}, {0,1}, {1,0}, {1,1}, {2,3}, {4,0} }
polygons = {
  {1, 2, 3}, -- a triangle
  {2, 3, 4}, -- another one
  {4, 1, 2, 3}, -- a square
  {4,5,6} -- more triangles
}

function share_edge(p1, p2)
    local n,m = p1[#p1], p1[1]
    for i = 1,#p1 do
        if n == p2[#p2] and m == p2[1] then return true end
        for k = 1,#p2-1 do
            if n == p2[k] and m == p2[k+1] then return true end
        end
        n,m = p1[i], p1[i+1] -- next edge in p1
    end
    return false
end

share_edge(polygons[1], polygons[2]) --> true
share_edge(polygons[1], polygons[3]) --> true
share_edge(polygons[3], polygons[4]) --> false

[pgimeno]

What's the data structure for the polygons? If you have at least a polygons table and an edges per polygon table, maybe you can build a cross-reference table of polygons per edge, to make it easy to look up. Each edge would be shared by two polygons at most. You'd just need to check the polygons of each of the edges of the current polygon.

[Rishavs]

oh dear. that sucks.

I am working of a neighbour algorithm right now.
was hoping there was some way of avoiding it. Its getting messy with every line i write.

@vrld. thanks. i learn new things everytime on this forum. it will help me optimize my intersection a lot. I can simply remove all non neighbouring polygons from the check.

[Karai17]

You could used Winged Edge to process your polygons so that they become searchable. I used this in a game and it have good results.

https://github.com/karai17/lua-winged-edge

[deströyer]

We had a similar issue in this forum post, where there was a bug in how the Voronoi cells would be determined for certain seeds and sizes:
viewtopic.php?f=5&t=81092&p=191346#p190177

If i remember correctly, the data is;
points > make up lines > make up polys
so lines are shared between polys, and points are shared between lines

I wrote an algorithm for determining neighbouring polys, it is accurate but extremely inefficient - it checks angles between all the lines radiating from a point and "walks" around the interior of each poly. There is a test linked in the forum post, but it is for Love v 0.9 - I've put up a 0.10-version here: https://www.dropbox.com/s/96eozprad7igu ... 1.zip?dl=0

(the only difference is that love.graphics.point has been replaced with love.graphics.points)

It might be useful? My advice would be: if you are the person in control of how the polygons are created (and you are not trying to infer them from external data), you should attempt to prevent lines and points from overlapping, so that you have better control of which edges straddle which polygons, for example.