cancel
Showing results for 
Search instead for 
Did you mean: 

Using polygon areas in Bounding Box Query

DMF194
Node Clone

Hi all,

Currently I have a lot of positional data (include lat and long) representing millions of nodes.

Original plan was to use bounding box query to put those nodes from above into clusters/region.

Spatial searches

I realized there are only 2 options, a)spatial bounding box search and b)spatial distance searches.

There is no option for polygons which I have available from postgreSQL.

Is there a way to use polygon shapes/areas/length to do spatial grouping of nodes into regions? Any suggestions will be appreciated.

13 REPLIES 13

You can get the same effect of an index-backed within-polygon search by first converting the polygon to a bounding box, searching and then filtering by the original polygon. This requires two additional functions:

  • Convert polygon to bounding box
  • Filter results by polygon

I discussed this approach in the GraphConnect 2018 presentation. I covered it in a little more detail in a followup meeting, which you can see in the video at All About Neo4j Spatial (Neo4j Online Meetup #44) - YouTube.

In that video I had written the two functions in the namespace amanzi.*, however, since then we have created a newer library called spatial-algorithms that has two functions:

  • spatial.boundingBox
  • spatial.algo.withinPolygon

You can find this library at GitHub - neo4j-contrib/spatial-algorithms: Spatial algorithms for both cartesian and geographic data

Hi @craig.taverner,

Thanks for pointing me in the right direction.

Now, I am creating relationships between nodes: Position and nodes:Region using the bounding box method.

match (r:region {region_name: '12 Ulu'}
match (p:position {deviceid: 2284} where point.withinBBox(p.positions_point, r.first_coor, r.last_coor)
call apoc.create.relationship(p, "IN")

r.first_coor, r.last_coor and p.positions_point all have the format point({srid:4326,x:104,y:2.97})

The code snippet has provided some errors, so do correct me if I am wrong.

My question is how to use the spatial.boundingBox or spatial.algo.withinPolygon to incorporate into the above query.

Any suggestions are welcomed.

Are r.first_coor and r.last_coor really the bottom left and top right of the polygon? The names make me think they are just the first and last coordinates of the polygon.

Do you perhaps have a list of coordinates for the entire polygon, because that is what you really need. For example, I could imagine you have a r.coordinates which is an array of point instances. Then you could do the following:

MATCH (r:region {region_name: '12 Ulu'}
WITH spatial.boundingBox(r.coordinates) as bbox
MATCH (p:position {deviceid: 2284} where point.withinBBox(p.positions_point, bbox.min, bbox.max)
CREATE (p)-[:IN]->(r)

I do not know why you wanted to use APOC to create relationships, so I replaced that with normal Cypher.

Yes r.first_coor and r.last_coor represent the min and max points of the polygon.

Currently I have polygon data type, which is long list of coordinates.

I have also looked into the github link and checked all the latest versions, using the link below.

There is no version for neo4j v4.4 which is what I am currently using.

I have installed the latest plugin spatial-algorithms-algo-0.2.5-neo4j-4.2.11.jar but when I try to find the spatial.algo.withinPolygon within the neo4j browser, it is unable to find it.

call dbms.procedures()
yield name where name starts with 'spatial.algo.withinPolygon'
return name

Is there a version of spatial algorithms meant for neo4j 4.4?

I took a look at this over the weekend, and there is no spatial-algorithms release for Neo4j 4.3 or Neo4j 4.4. So I did a test port to 4.3, but there are some changes in the kernel relating to cursor closing that has prevented completion of this port. I'll see if I can get some support to fix that, and then port to 4.4 as well later.

The other option you have is to try extracting just the withinPolygon function or try use the older version from the spatial3d library.

Hi @craig.taverner ,

I appreciate that you looked into my issue regarding the spatial-algorithms.

Personally, I think I will wait for more news on the fix. I honestly have no idea how to extract the withinPolygon and since my organization still plans on using the latest Neo4j 4.4, I do not think trying the older version of spatial3d library would be of any use either.

Lastly, I was hoping if there any additional resources on how to use withinPolygon and other use cases for it, utilizing Python drivers to display onto Neomap or into OpenStreetMap. Other than the sources listed below:

Neo4j Docs
Grandstack/GraphQL

Any suggestions are welcome,

I have managed to port this library to Neo4j 4.4. See the release at Release Spatial Algorithms 0.2.5-neo4j-4.4.3 · neo4j-contrib/spatial-algorithms · GitHub

The main challenge was the preceding port to Neo4j 4.3, which involved some bigger algorithm changes to cope with a change in behaviour in the Neo4j kernel. But once that was done, porting to Neo4j 4.4 was trivial.

Regarding documentation of withinPolyon, there is only the test code at spatial-algorithms/UserDefinedFunctionsTest.java at master · neo4j-contrib/spatial-algorithms · GitH...

Hi @craig.taverner ,

I have tried to import the jar file in the link you provided below.

Unfortunately, when I restarted my Neo4j 4.4.11 desktop application to apply the changes, it refused to connect to my Neo4j db instance

A coworker of mine who uses Neo4j 4.4.12 desktop application was able to connect to Neo4j db instance after importing the plugin, however it still produces 0 results using the query below to check

call dbms.procedures()
yield name where name starts with 'spatial.algo.withinPolygon'
return name

That is the latest update I have for using the spatial algorithms

As a workaround, I currently using this function

match (n:Node)
call spatial.intersects('geom',n)
yield Node return node.name

The below function is what I use to create the node

unwind [{name:'a',latitude:0.79157,longitude:101.3333}] as point
merge (n:Node{name:point.name,
latitude:point.latitude,
longitude:point.longitude})

Note, I have imported shape file prior to this to extract my POLYGON data

Any suggestions would be appreciated

A few comments:

  • The spatial.algo.withinPolygon() function is a function not a procedure, so you will not find it using dbms.procedures() but need to look using dbms.functions().
  • Also, the procedure spatial.intersects() is provided by the spatial library, which itself is not ported to Neo4j 4.4. The latest release of that library is for 4.2.
  • Using the two libraries together should work, but it not something I've tested much. But you should then use the 4.2 version of both libraries in Neo4j 4.2. If you want to use Neo4j 4.4, only the spatial-algorithms library has been ported to that so far.
  • Am am not very familiar with Neo4j Desktop, so I do not know for sure why it could not connect, but if you can find the Neo4j log files (neo4j.log and debug.log) it is very likely that they will contain the errors encountered starting Neo4j. If you find that, you can post it here and we can see what the problem is.

Hi @craig.taverner,

Appreciate the comments, for now I am just using the link below

I was able to call the function spatial.algo.withinPolygon() successfully.

But I am unclear as to how to use the information in my imported shape file and using it with the spatial.algo function. and I keep getting the error below

My conclusion is that I do not understand the logic to access the data for my SpatialLayer node created.

The below code was used to add the node

call spatial.addWKTLayer('geom','geom');
call spatial.importShapefileToLayer('geom','import/shapefile/admin_region.shp');

Finally, I wish to create a cypher to use the spatial.algo.withinPolygon to create a relationship between my SpatialLayer node with my nodes

OK. So it looks like you are using two libraries together. This means you need to understand the different internal structures of the geometries as understood by those two libraries in order to pass data from one to the other. A polygon in the spatial library could be a WKT string, while a polygon in the algorithms library is always a list of points, and it will never understand WKT, so you need to convert it to a list of points.

Also, the query you are using to get the polygon will not work because you are looking for a geometry on the SpatialLayer node which never has geometries, so s.geom will always have value null, and that is why you got that error.

The SpatialLayer node is just the root of a data tree containing all the data you want. You can traverse that tree using Cypher, but that is not the intention. It is intended to be searched using the spatial procedures provided by the spatial library.

While I could point out errors in the queries you provide here, I think in order to properly support you, I would need to know what the original data is that you imported, and what type of queries you are trying to perform? For example, it seems like you have two different types of data and want to use one to search the other. I could speculate further, but it would be better if you simply describe the situation here, and then I can give more comprehensive support.

For example, you could say:

  • We have polygons imported as WKT from, shapefiles
  • We have points imported as latitude/longitude properties of nodes
  • We want to find a particular polygon from the shapefile
  • And use it to find points within the polygon

Then I could describe a query that would work for this scenario.

Agreed @craig.taverner,

The situation is as you describe

We have polygons imported as WKT from, shapefiles
We have points imported as latitude/longitude properties of nodes
We want to find a particular polygon from the shapefile
And use it to find points(from the imported nodes) within the polygon

Lastly, the shapefiles I imported as WKT layer, has null values as shown below.

I notice the property values stored in the SpatialLayer node is in string and uses () brackets, and it cannot be treated as a list, I have tried using the apoc.convert.toList and it still converts to string and not as a list.

Hope that this helps. Is there any function or procedure that can help to convert info in one type of spatial library to spatial algo library.

Any suggestions are appreciated.

OK. I think there are two parts you are missing:

  • Finding the polygons to use for the search
  • Converting WKT into a list of native points for use in the spatial.algo.withinPolygon function

Before I explain more about how to fix those two points, have you considered just using the spatial library by itself? I mean store both polygons and points using that library, instead of mixing and matching two different ways of working with geospatial data? The advantage would be not having to worry about WKT conversion. The disadvantage would be slower searching for points because the spatial index used by the spatial library is not nearly as well optimized as the spatial index used by native Neo4j points.

Anyway, back to the main answer. The first thing is to find the polygon. The Cypher expression you used would find all kinds of nodes in the graph, only some of which are actual data nodes, which is why you are getting null values (you are finding index nodes, and anything connected to the layer, even config setting nodes). You could write a more complex Cypher expression to avoid this, but that would be missing the point of the spatial library. It comes with a number of procedures for spatial search. I don't know what polygon you are looking for, but can suggest a few functions, like spatial.withinDistance, or spatial.intersects. Then you will have the polygon (or polygons) with WKT geometries, and can use that for the point search.

The second thing would be to convert the WKT into points. This is not trivial, because there is no existing function I can see that does this job directly. The spatial library has a function spatial.asGeometrywhich converts the WKT into an internal Neo4j geometry type, but no other code understands that type. You need a function that generates the list of points from that type. This would be very easy to write, but currently does not exist in either of the libraries you are trying to use. It could probably be added to either one, or written by yourself.

Nodes 2022
Nodes
NODES 2022, Neo4j Online Education Summit

On November 16 and 17 for 24 hours across all timezones, you’ll learn about best practices for beginners and experts alike.