Repository navigation
Intersection between two routes (linestrings) #159
Description
Hi
I'm really sorry for asking such a noob question, but is this library the correct one to estimate:
- If a route is within distance of a point (I have a bunch of routes)
- If two routes intersect each other
- Get all intersecting routes for a given route (this may be pre-calculated)
- Points of intersection (there may be many! or inifnite if routes go together)
I plan to use this on Android /offline
Activity
dsmiley commentedon Mar 23, 2018
Yes. Each route is a LineString, and you could test intersection against a circle (point-radius).
Yes.
This is the same as the previous question? At least, in Spatial4j, you can test routes against each other. This is O(N) with the number of routes to test if you want to know the intersecting routes for a particular route. If you have many, you'll have to look elsewhere for some persistent indexing approach (e.g. Lucene/Solr).
No, sorry. The primary geometry/shape feature in Spatial4j is computing a relationship between a pair of shapes. There is no further information on where shapes touch/intersect.
SebaSOFT commentedon Mar 23, 2018
Thanks, at least if I know to be interacting I can test for segments and apply simple math to that
( https://github.com/MartinThoma/algorithms/tree/master/crossingLineCheck/Geometry/src )
there are about 60 tracks with no more than 20 points each so a pre-calculation would not be that much of a burden and it can be cached.
Regards
ChangooLee commentedon Apr 16, 2018
Hello,
I'm using this for flight route calculation. Thanks in advance.
Could you show me an example that test intersection of LineString against a circle?
Best regards
dsmiley commentedon Apr 16, 2018
Ouch; I was wrong! Anything can be intersected against a rectangle or point, but relations that don't involve either (circle, line, polygon) are not universally supported. It would be really nice if circle-line intersection was supported; ah well.
As an alternative, consider using JTS. JTS has a LineString. For a circle you can approximate it. JTS has a utility somewhere for producing a polygonal circle given a center point and radius.
ChangooLee commentedon Apr 19, 2018
Thanks for your information.
I don't know why but, somehow, it worked... you can check with radius 7 and 8.
org.locationtech.jts.io.WKTReader wktReader = new org.locationtech.jts.io.WKTReader();
Shape line = ctxNotGeo.makeShape(wktReader.read("LINESTRING(5 10, -10 -20, 20 10)"));
System.out.println(line.relate(ctxNotGeo.makeCircle(10, -10, 8)));
dsmiley commentedon Apr 19, 2018
Oops; I was wrong; that was embarrassing. I was looking at the Spatial4j-native BufferedLineString shape but forgot that the JtsGeometry wrapper is in play here which does relate with a Circle. Just be aware that this logic works in a cartesian space, so will be inaccurate if you're using it in a "geo" context ("geo" is Spatial4j's lingo for a spherical world model). Thus if your points are decimal degrees lat/lon, this relation will become increasingly inaccurate away from the equator.