Spatial Containment

[Alireza Rezaei Mahdiraji]

Hi All,

I would like to find nodes of the graph which are completely (not partially) contained in a given
Envelope. I tried several GeoPipeline methods but it seems they all consider partial containment.
Any idea?

Thanks,
Best,
Alireza

[Craig Taverner]

Hi,

I can see two ways in the Java API to do this. One is the 'within' filter in the GeoPipeline.

• See example usage in the test code at 
• See the implementation using JTS in the code at https://github.com/neo4j-contrib/spatial/blob/master/src/main/java/org/neo4j/gis/spatial/pipes/filtering/FilterWithin.java#L47

And the other is the older, but still functional use of CQL for within queries:

• See an example using dynamic layers at https://github.com/neo4j-contrib/spatial/blob/master/src/test/java/org/neo4j/gis/spatial/TestDynamicLayers.java#L138
• And the implementation at https://github.com/neo4j-contrib/spatial/blob/master/src/main/java/org/neo4j/gis/spatial/filter/SearchCQL.java#L56
  

A direct usage of the SearchCQL class is also possible, but I did not see a test case for it. It was used by the GeoServer integration though.

Regards, Craig

--
You received this message because you are subscribed to the Google Groups "Neo4j" group.
To unsubscribe from this group and stop receiving emails from it, send an email to neo4j+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Alireza Rezaei Mahdiraji]

Hi Craig,

Probably the first option is a faster option, right? I heard using CQL from within Java code
is not as efficient as using the pure Java.

BTW, which test code you are referring too? I Tried to find an exmaple which uses FilterWithin but I was hopeless.

Thanks,
Best,
Alireza

[Alireza Rezaei Mahdiraji]

I tried this snippet:

GeometryFactory gf = layer.getGeometryFactory();
Geometry geom = gf.toGeometry(envelope);
List<Node> nodes = GeoPipeline.startWithinSearch(layer, geom).toNodeList();

but the result still contains nodes which are not fully inside the envelope.

What am I missing?

Thanks,

Alireza


On Tuesday, September 2, 2014 10:35:38 AM UTC+2, Craig Taverner wrote:

[Craig Taverner]

Hi Alireza,

Probably the first option is a faster option, right? I heard using CQL from within Java code
is not as efficient as using the pure Java.

Yes, if the only constraint is embedded in CQL, then the code will not use the index. If you send an additional bbox it will use the index for the first pass, and CQL for the refined search, and that will be quite fast. Using the GeoPipe API is a safer bet, using the Index always (because it makes the bbox for the index search automatically).

BTW, which test code you are referring too? I Tried to find an exmaple which uses FilterWithin but I was hopeless.

Sorry, I forgot to attach the link. Here it is: https://github.com/neo4j-contrib/spatial/blob/master/src/test/java/org/neo4j/gis/spatial/pipes/GeoPipesTest.java#L169

Regards, Craig

[Craig Taverner]

Hi Alireza,

That code looks OK. Could you send me some sample data? I could try this myself and see what the problem is. The code underneath is using the JTS function Geometry.within(Geometry) and that is strictly defined. See http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/geom/Geometry.html#within(com.vividsolutions.jts.geom.Geometry).

But if I try your data I could double-check if there is perhaps an issue in how we use this.

Regards, Craig

[Alireza Rezaei Mahdiraji]

Hi Craig,

I attached the neo4j database folder for the toy example I am using.

The envelop I am using is as follow: xmin: 0.5, xmax: 1.5,  ymin: -0.5, ymax: 1.5

This envelop only contains one graph vertex fully, the vertex with x=1 and y=1
but code returns several other results too which are partially contained by the envelop.

Thanks,
Best,
Alireza

[Alireza Rezaei Mahdiraji]

Hi Craig,

Have you received my sample data set?

Thanks,

Alireza

On Wednesday, September 3, 2014 5:08:36 PM UTC+2, Craig Taverner wrote:

[Craig Taverner]

Hi Alireza,

I opened your graph in the neo4j server and looked around, and then also write some Java test code (based on your snippet) to see what I could see. The main conclusion is that I see two nodes (not one) that are in the envelope, nodes with n.id=2 and n.id=10.

I've attached screenshots of the Neo4j browser looking at the data, a graph view showing the nodes and the spatial layer connected to them, and a cypher query that lists the key properties. The cypher query I used was:

MATCH (n) WHERE has(n.gtype) RETURN id(n), n.id, n.gtype, n.x, n.y, n.bbox, n.dim, n.eid

Some interesting points I can see:

• There are definitely two nodes with x=1, y=1 which should be inside Envelope(0.5,1.5,0.5,1.5).
• The use of a property 'id' is allowed, but a little confusing because it is easy to think that might be the node id (see that I'm listing the node id and the node property 'id' just to be clear)
• I'm surprised by the fact that there are three different gtype values: 1, 2, 3, which mean POINT, LINESTRING, POLYGON respectively, but clearly these are all points (they have only x,y information). This means that these objects were not created by the Neo4j Spatial library, but created by some other code? How did you create them? I suspect there is something not quite right there.
• The BBox values for POINT objects should be points themselves (ie. (x1,y1) == (x2,y2)). And in fact I see for all objects with gtype==1, this is true. For other objects, you have bigger bounding boxes, which makes sense for the type, but since they are actually only points, it no longer makes sense.
• When I look into the layer node, I see that the GeometryEncoder is the SimplePointEncoder, consistent with the observation that all data are x,y pairs (Points)
• But I see the layer implementation is the EditableLayerImpl, which is more often used for WKT Geometries (allowing LineString and Polygon also).

The test code that I wrote was in Java and based on your sample. The main part of the code looks like this:

SpatialDatabaseService spatial = new SpatialDatabaseService(graphDb);

Layer layer = spatial.getLayer(layerName);

GeometryFactory gf = layer.getGeometryFactory();

Envelope envelope = new Envelope(0.5, 1.5, 0.5, 1.5);

Geometry geom = gf.toGeometry(envelope);

try (Transaction tx = graphDb.beginTx()) {

List<Node> nodes = GeoPipeline.startWithinSearch(layer, geom).toNodeList();

for (Node node : nodes) {

System.out.println("Node[" + node.getId() + ":" + node.getProperty("id") + "]: " + nodeXY(node) + " - "

+ nodeBBox(node));

}

assertEquals("Only one node should be in envelope", nodes.size(), 2);

tx.success();

}

This test passes on the two nodes that look like Point(1,1) as expected. However, since you probably meant the second one to be a LineString (gtype=2), it probably was supposed to intersect the envelope, not be included. But since you use the SimplePointEncoder, it will be seen as a point at 1,1, so it will be included.

My understanding is that you created the data incorrectly, using a SimplePointEncoder for data that you meant to be LineString and Polygon. I suggest that you rather use the WKT encoder. Do not create the nodes yourself, but use the layer.add(Geometry) to create them for you, and then add your own properties to them afterward, so you are sure the geoemtry information is correctly created.

Regards, Craig

[Alireza Rezaei Mahdiraji]

Hi Craig,

The semantic of the data is of geometrical sgapes as follows:

1-there are vertices which have their own coordinates and I created them using
Point p = runningLayer.getGeometryFactory().createPoint(coord);
and then add them to the layer:
SpatialDatabaseRecord v = runningLayer.add(p);
and then set their properties.

2-there are edges which are linked to their vertices but I also build a linestring object for them using :

LineString lineString = runningLayer.getGeometryFactory().createLineString(coord);

3-there are 2D shapes (here triangles) which are connected to their edges and I created them using :
Polygon poly = runningLayer.getGeometryFactory().createPolygon(coordinates);

Which part of the creation is wrong?

Another question is: to answer geometrical query would it be enough to store only vertices as geometry type
and edges and 2D shapes as normal nodes?

These objects have their own "id", that is why I set that as a property, I assume we do not have control over neo4j
property, i.e., we cannot set it right?

Thanks,
Alireza

[Alireza Rezaei Mahdiraji]

My layer was defined using SimplePointEncoder.class but I changed to WTK:

runningLayer = (EditableLayer)
                graphDBSpatial.getOrCreateLayer(layerName,
                    WKBGeometryEncoder.class,
                        EditableLayerImpl.class,
                            geomEncoderConfig);  

This works fine, i.e., for the envelope it returns only one object which is a vertex,
I tried another envelope (0.5,1.5, - 0.5,1.5) and it works fine too (returns three objects which is correct).

However, I am not sure if my definition of layer is correct.

Best,
Alireza

[Craig Taverner]

Hi Alireza,

Which part of the creation is wrong?

Only that you are adding LineString and Polygon to a layer created with SimplePointEncoder, which will not be able to store anything other than Point correctly. We should actually throw an exception when you do this, but apparently we just store one point of the geometry instead.

 

Another question is: to answer geometrical query would it be enough to store only vertices as geometry type
and edges and 2D shapes as normal nodes?

You could store only points in the SimplePoint layer, and model the lines and polygons as edges yourself in your graph (by connecting the points). This is a valid approach. But in his case you cannot perform JTS functions on the LineString and Polygon, because they will know be known as Geometries by the library. You need to do that logic yourself, because the connectedness is only known by your own data model.

However, your case is also ideal for creating your own GeometryEncoder, one that understands Point, LineString and Polygon, and understands that the Point objects are parts of the LineString or Polygon objects in the same connected graph. This is what we did for the OpenStreetMap model, which is a fully connected graph. However, it is not trivial. And it has to be coded by you because it is very specific to your data model. Only you know how you have decided to connect things together in the graph.

 

These objects have their own "id", that is why I set that as a property, I assume we do not have control over neo4j
property, i.e., we cannot set it right?

It is not wrong to create a property of name 'id', but it is a bit ambiguous. I'd feel safer to use a more specific name like 'my_id', or something meaningful to your domain.

[Craig Taverner]

Switching to WKT or WKB like this means that your cases will work, because you now have an index that understands Point, LineString and Polygon correctly. This is the easiest solution to your immediate needs.

The only option that might be better was the one I suggested in a previous email, where you create your own GeometryEncoder class that can, for example, allow the same Point node to also be part of the LineString geometry. This will allow you to analyse your data in a more graphy way, but does require that you really know what you are doing. It should be considered 'advanced' usage of the spatial library.

[Alireza Rezaei Mahdiraji]

Hi Craig,

Thanks a lot for elaborate answer.

The snippet from you by changing to WK encoder seems to work.
A related question in this case is (I do not know if I should send it as a
separate post or not):

I want to build a graph out of the result of this query, is there any such
solution already in Neo4j, i.e., to recieve a query result as yet another graph not
just a list of node?

Thanks,
Alireza

[Craig Taverner]

I want to build a graph out of the result of this query, is there any such
solution already in Neo4j, i.e., to recieve a query result as yet another graph not
just a list of node?

This sounds very domain specific. What kind of graph do you want? I would assume you would need to build whatever graph you want yourself.

However, if the graph you are talking about is the graph structure of the geometries themselves, then I recommend my previous suggestion, with a custom GeometryEncoder that allows the LineString and Polygon geometries to already be graphs. In that case your data model for a three point Polygon could be (p)-[:points]->(a)-[:first]->(b)->[:next]->(c)-[:last]->(a), where (a), (b) and (c) could all be Point Geometries in your index, and (p) would be the polygon containing those three points. The bbox and gtype for each point is stored on the a,b,c nodes, and the bbox and gtype of the entire polygon is stored on the (p) node, and your GeometryEncoder knows how to convert from graphs to Geometry objects and back.

This way you control entirely the data model, while still being able to use the spatial library for geometry searches.

[Alireza Rezaei M]

Any example on how to build such customized GeometryEncoder?

Alireza

--
You received this message because you are subscribed to a topic in the Google Groups "Neo4j" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/neo4j/svcOw_S0l1A/unsubscribe.
To unsubscribe from this group and all its topics, send an email to neo4j+un...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
Best Regards

Alireza Rezaei Mahdiraji

[Craig Taverner]

Yes, look at the ones included in the library. See one I made as a sample years ago that can encode a LineString as a chain of connected nodes: https://github.com/neo4j-contrib/spatial/blob/master/src/main/java/org/neo4j/gis/spatial/encoders/SimpleGraphEncoder.java

You could copy this and extent it to handle Point, LineString and Polygon. The OSMGeometryEncoder is one that can handle those types, but it uses a more complex graph model you perhaps don't want to be burdened by. I think the graph model I suggested in my earlier mail, and the sample code linked to here, are more appropriate for you.

--

You received this message because you are subscribed to the Google Groups "Neo4j" group.

To unsubscribe from this group and stop receiving emails from it, send an email to neo4j+un...@googlegroups.com.

[Alireza Rezaei M]

Thanks a lot Craig,

I will look at it and perhaps come back with some questions. In that case, should I write in this post

or create a new one?

Alireza

[Craig Taverner]

That's your call. The subject has changed a lot, so you could write a new one, but if you want all this discussion together, keep this one.

[Alireza Rezaei Mahdiraji]

Hi Craig,

Are we limited to only 2D bbox for querying? In general, are any 3D queries are supported in Neo4j spatial?

Best,
Alireza

[Craig Taverner]

Hi Alireza,

A few years ago we started refactoring the RTree to support n-dimensional objects, but this work was not completed. So currently only 2D is supported. Can you tell me more about your use case? I would like to know about cases for 3D so we can think again about future support.

Regards, Craig

[Alireza Rezaei Mahdiraji]

Hi Craig,

Out of top of my head is 3D bounding box (range sub-setting) and slicing queries.
I write you if I needed more cases.

So, currently, there is no way to support a 3D bbox query or slice in neo4j spatial except
directly checking the axes values, right?

Thanks,
Alireza

[Alireza Rezaei Mahdiraji]

Hi Craig,


What would be the best way to import such data into Neo4j.
The sample file that I have first list all vertices with their coordinates and then
all polygons with the list of their corresponding vertex id list.
The edges are inferred from this two list.

My current script is extremely slow for verices around 20000 and polygon around 35000.

Thanks,
Alireza

[Craig Taverner]

Hi Alireza,

Sounds like you need a unique key to connect vertices during the edges import. You called this the 'vertix id'. We had the same problem importing OSM data in the OSMImporter class. In that code we used the lucene index to store the osm-id for the vertices. This works fine for moderate sized data, but does not scale that well. But it should be OK for 20000 vertices. Are you using lucene? Or some other way to lookup vertices by id?

My vote for data as small as 20k vertices is to make your own id-mapping structure. For example, if the veritix id is in a well known range (eg. 0..20000) then make an array where the array index is the vertice id and the value is the neo4j node-id. If it is not in a well known range, use a HashMap. Both will be faster than lucene for small data sizes, but will not scale obviously.

Regards, Craig

[Alireza Rezaei Mahdiraji]

Hi Craig,

I use my own id-mapping data structure (hashmap). What you said about lucene is interesting, becuase yesterday I thought about doing so.

What I do now, first I create the nodes for point geometries, then I start creating polygon nodes, extract the list of edges for each polygon, create
node for each edge, connect polygon to its edges using neo4j relationships and connect edges to their corresponding points' nodes.
I thought maybe a top-down approach works better but I need to try it: i.e., create polygon nodes, extract edges and create edge node, connect polygon to edges,
create points and connect edges to points.

Any opinion?

Thanks,
Alireza