Finding neighbours on an arbitrary polygon grid

General discussion about LÖVE, Lua, game development, puns, and unicorns.
Post Reply
User avatar
Rishavs
Party member
Posts: 103
Joined: Sat Oct 17, 2009 5:29 am
Contact:

Finding neighbours on an arbitrary polygon grid

Post by Rishavs » Thu Jul 14, 2016 10:27 am

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?

User avatar
Tanner
Party member
Posts: 166
Joined: Tue Apr 10, 2012 1:51 am

Re: Finding neighbours on an arbitrary polygon grid

Post by Tanner » Thu Jul 14, 2016 10:57 am

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.

User avatar
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

Re: Finding neighbours on an arbitrary polygon grid

Post by vrld » Thu Jul 14, 2016 11:34 am

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
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine

User avatar
pgimeno
Party member
Posts: 1785
Joined: Sun Oct 18, 2015 2:58 pm

Re: Finding neighbours on an arbitrary polygon grid

Post by pgimeno » Thu Jul 14, 2016 1:58 pm

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.

User avatar
Rishavs
Party member
Posts: 103
Joined: Sat Oct 17, 2009 5:29 am
Contact:

Re: Finding neighbours on an arbitrary polygon grid

Post by Rishavs » Thu Jul 14, 2016 3:46 pm

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.

User avatar
Karai17
Party member
Posts: 879
Joined: Sun Sep 02, 2012 10:46 pm

Re: Finding neighbours on an arbitrary polygon grid

Post by Karai17 » Tue Jul 19, 2016 6:22 pm

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
STI - An awesome Tiled library
LÖVE3D - A 3D library for LÖVE 0.10+

Dev Blog | GitHub | excessive ❤ moé

User avatar
deströyer
Prole
Posts: 27
Joined: Thu Jun 27, 2013 7:59 pm
Contact:

Re: Finding neighbours on an arbitrary polygon grid

Post by deströyer » Thu Jul 21, 2016 12:18 pm

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.

Post Reply

Who is online

Users browsing this forum: pgimeno and 5 guests