Find neighbouring Polygons Java

Question

I have a series of Polygons, created using the JTS Topology Suite. Each polygon is a set of points, longitudes and latitudes that form a shape, as shown below.

((lat1,lon1),(lat2,lon2),....(lat1,lon1))

I want to find each of these polygons neighbours, the other shapes that are physically next to them. I have thought of looking for matching points, but obviously that won't work in all cases. I was wondering if there is any package that will check to see if polygons share the same edge that I could use in this situation? Or if not then another way to do this in Java.

Thanks.

Answer 1

There was in fact a very simple way to do this. I created an arraylist containing an array of objects. The object referenced the name/id of the polygon, the actual polygon coordinates and then a string that would contain ids of any neighbours.

In JTS Topology suite there is a method that you can call on polygons called touches that returns a boolean; so I had a double for loop, going through my arraylist twice and calling the method touches on polygon(i) so:

arraylist<object[]>..
//where in the array the objects are
object[0] = id
object[1] = polygon
object[2] = neighbours

for (int i=0;i<arraylist;i++)
  for (int j=0;j<arraylist;j++)
    if (i)[1].touches(j)[1]
      update i[2]..

It's probably not the best method but it seems to work.

Answer 2

Since you are looking for shared edges, you can create a hash table uses the edge as the key and a list of polygons that have that edge as its item.

Then you go through each polygon and fill up the table. Which is linear in the number of edges.

Then you go through the table and look for edges that are tied to multiple polygons, which is what you are looking for. This is linear in the number of unique edges.

I'm not sure how Java implement hash tables, so it might be a bit of work to get this setup. Make sure the edges are sorted to prevent the edge (A,B) being different from the edge (B,A), which will mess up the algorithm.

As for libraries, seems like what you're trying to do might be a bit specialized, and thus not sure you'll find library implementations, hence why I outlined an algorithm.

Answer 3

If you are using JTS geometries anyway you can use the spatial relations that can be used with any Geometry object.

Use touches if you can ensure that at least one point between neighbours is in common and their interiors do not intersect.

Use intersects if you cannot ensure that the interiors do not intersect. Depending on the datasource this is probably the better choice.

Given the polygons a method to get the neighbours can look like this:

public ArrayList<Polygon> getNeighbourList(Polygon center, ArrayList<Polygon> possibleNeighbourList){
    // result list
    ArrayList realNeighbourList = new ArrayList();
    for(Polygon p : possibleNeighbourList){
        // check if current polygon is a neighbour of the center polygon by using the spatial relation touches or intersects
        if(center.intersects(p)){
            realNeighbourList.add(p);
        }
    }
    return realNeighbourList;
}