Linestring calculations and relations

General
1

Hi, Im new to backendless and trying to see if I can achieve what I want here, I hope this qualifies as an appropriate question.
Im hoping to have each user upload a linestring of coordinates for the route they are taking.
In the picture below I have represented these in red and green
When a user makes a note on their route I want to send it back to all vehicles who have a route that includes this point. This means the green route user would be notified of point A , but NOT point B
The issue is that the line strings are made of made of many points, sometimes many hundreds of meters apart so a radius search is often inappropriate and a bounding box search is too broad. Ideally I’d like to have a function that returns true if point A is alongRoute and then ping all the devices that have routes that also contain point A. I also need there to be some tolerance for error (10-20m) as no point will fall exactly within a given corridor.

My question then is : do these functions exist within backendless ,
if so thats great
if not can how can I write my own code serverside to iterate through all these points and using some coordinate math and determine if that point falls within a corridor made between one point and the next.
(I have the code to do that, just want to know if I can implement it within backendless)

image
image947Ă—668 246 KB

2

Hi James,

Can this problem be reduced to knowing if two (or more) linestrings have a point of intersection? The way I read your description is it appears that way, but I am afraid I missed something.

Regards,
Mark

3

Almost :slight_smile: but not quite;
For the following reasons.

1/The devices generate the routes offline, not on a common server, and therefore may have different versions of openstreetmap roads, which mean someone can edit/adjust the roads and change the position of the nodes (which have no common index that I can get hold of programatically) , these nodes can be edited quite frequently . I have various ideas for ensuring consistency including staging versions and running different servers for each version but it gets messy fast. Offline routing is a must for this app.

2/ Whilst comparing exact nodes could tell me where the routes intersect and decouple, it wouldn’t tell me if point A is on or near either one of those routes because point A is a user generated location ,
image

it has a different lat/lng to the nodes used on the route. It may also be several meters off the route but near enough for my purposes to be relevant . If a route contains a long straight road with no side roads the nodes can be several hundred meters apart.

I have coded some math in java that I use on the devices that can determine if a point is within 2 nodes, with a tolerance, like so, it’s much more specific than a square bounding box and alters its shape to the bearing, rather than a boundingbox that varies with bearing.

The node index tells me where it is on the route, but the node index is redundant off the device as it won’t apply to another users route.
image
But if I could run that code for each two nodes on the route (server side) then that would suffice.
but, I also need to go through the other users (can narrow it down by road name) and compare their routes to check that that point , is between two points on their routes so I can notify them there is new data on their route.

So to clarify,
When starting a route, each user would upload all points on their route, and the names of all the roads on their route to a table on your servers db.

They then download all of the existing notes/ points on the db that
a) have common roadnames,
and
b) fall between the nodes on the the requesting users (entire) route. (perhaps minus the roads they have already traversed)

This is then stored on the devices local db, and I determine further relevancy locally with bearings/time etc

When a user makes a note (ice, accident etc) this is sent to the server with the roadname and the lat/lng location.
then the server adds it to the db,
and then sends that data, (or sends a push message signalling the device to poll the db) to pull any new data) to ALL users who have a route that is traversing the same road name/s , and where their route has a nodes that encompasses the new data as shown by the green box.

4

Thank you for such a detailed explanation, James! What I am trying to do is to wrap my mind around these concepts from the perspective of how the data can be represented using the data structures and spatial types we support. And then translate everything you wrote into an algorithmic problem.

So say we have objects of type Route in the database. Each route has some metadata, but most importantly it has a LINESTRING value defining individual turn points (or nodes which make up the route). The routes are somehow mapped to users/devices.

Additionally, there is a data table which contains “user uploaded points”, I assume we can use the POINT type for that. Let’s call that entity UserUploadedPoint. What you’re looking for is a way to determine which routes have specific UserUploadedPoint and then notify the devices associated with those routes.

The challenge here is the UserUploadedPoint object may be within the vicinity of a route, therefore the functions we provide out of the box to determine If a point is exactly on a LINESTRING will not work. To make it work though, the routes need to be extrapolated and presented as a collection of POLYGON values. Because once you do that, then the database will do all the work to determine if UserUploadedPoint is within the geometry.

1 Like
5

Hi Mark,
Thanks , Yes, ok , so you need the 4 points of each of the many polygons on the route. Let me see if I can produce those device side

1 Like