Finding minimum tolerance - Githubissues

perliedman / geojson-path-finder

Find shortest path through a network of GeoJSON

https://www.liedman.net/geojson-path-finder/

ISC License

300 stars 86 forks source link

Finding minimum tolerance #89

Closed ofekkazes closed 1 year ago

ofekkazes commented 1 year ago

``Hi,

First, thank you for the great library.

I currently am trying to create a walking directions for an indoor map. The GeoJSON I am using for walking is:

{"features":[{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.057522,32.810122],[35.057438,32.810179],[35.057359,32.810105],[35.057254,32.809999],[35.057363,32.809925]],"type":"LineString"},"id":"02a0641ae555d72c209656f6b53fb9b6"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.053533,32.808279],[35.053449,32.80823],[35.053541,32.808099],[35.053864,32.808314],[35.053981,32.808177],[35.054153,32.807972],[35.054279,32.807863]],"type":"LineString"},"id":"0b43dc7c9303785374a104c561fe2d3b"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.054516,32.809134],[35.054621,32.809025],[35.054558,32.808982],[35.054659,32.808866],[35.054818,32.808824],[35.054542,32.808676],[35.054422,32.808603]],"type":"LineString"},"id":"295d00c4d454da1fc72c28a77240ae9a"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.053598,32.808505],[35.05343,32.808392],[35.053535,32.808275],[35.054504,32.808896],[35.054361,32.809023],[35.05468,32.809234],[35.054853,32.809333],[35.054987,32.809196],[35.056023,32.809845]],"type":"LineString"},"id":"31a8a2915d6e38ca5e312ccd53be4bc1"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.054712,32.809459],[35.054985,32.809177],[35.054922,32.809128],[35.055102,32.808941],[35.055496,32.809184],[35.055551,32.809089],[35.055643,32.809019],[35.055782,32.808987],[35.056117,32.809181],[35.056398,32.809382],[35.05665,32.809554],[35.056947,32.80972],[35.056809,32.809889],[35.056658,32.810052],[35.056482,32.810224],[35.056025,32.809852]],"type":"LineString"},"id":"3d39b4472d246785655cbce69066c87e"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.056126,32.808227],[35.055967,32.808111],[35.055879,32.808192],[35.05577,32.808114],[35.055971,32.807892],[35.056147,32.807818],[35.056261,32.807712],[35.056273,32.807688]],"type":"LineString"},"id":"3eb67e0909c672e670ff3afaa784a7ea"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.054581,32.808642],[35.054011,32.808279],[35.053944,32.80823]],"type":"LineString"},"id":"41a42d6087f2b13bda57c1079f1d6642"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.05725,32.810003],[35.057178,32.809946],[35.056767,32.810242]],"type":"LineString"},"id":"43b9f038be300c2decc905e4c92f084f"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.054839,32.808383],[35.055087,32.808542],[35.054806,32.808827]],"type":"LineString"},"id":"4eb6d701ae7b57b76bf4d8ed4b99274b"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.058021,32.810947],[35.057833,32.810665],[35.057627,32.810394],[35.057443,32.810186]],"type":"LineString"},"id":"51b5a7d8a913ddedc9c89527c1c4d946"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.056344,32.807614],[35.056256,32.80755],[35.056177,32.80754],[35.056135,32.807504],[35.056118,32.807455],[35.056009,32.807483],[35.05587,32.807564],[35.055745,32.807617],[35.055866,32.807695],[35.055757,32.8078],[35.05556,32.807984]],"type":"LineString"},"id":"669d6194fd79fa4133d461b9a385129e"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.055722,32.808944],[35.056278,32.808312],[35.056131,32.808217],[35.056282,32.808079],[35.056366,32.807997],[35.056496,32.807847],[35.056269,32.807688],[35.056533,32.807403],[35.056605,32.807378],[35.056681,32.807389],[35.057197,32.807741],[35.057235,32.807774],[35.057084,32.807904],[35.056971,32.808028],[35.05703,32.80807],[35.056665,32.808461],[35.056556,32.808475],[35.056384,32.808391],[35.056275,32.80831]],"type":"LineString"},"id":"69c7050a99f9672078e354a4615ff0c1"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.054958,32.808923],[35.055162,32.808721],[35.055258,32.808667],[35.055355,32.808686],[35.055711,32.808936],[35.055782,32.808988]],"type":"LineString"},"id":"75ff84b9ea7b1ecc09816c3a26c58b17"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.058063,32.810743],[35.058172,32.810898],[35.057984,32.810951],[35.057627,32.811011],[35.05738,32.810778],[35.057107,32.810507]],"type":"LineString"},"id":"7dd62df01b39d272c0ebafb40ff34d8c"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.054712,32.809471],[35.055413,32.809923],[35.055488,32.809972],[35.055551,32.809905],[35.056294,32.81037],[35.056474,32.810229],[35.056654,32.810335],[35.056759,32.810233],[35.057107,32.810511],[35.056893,32.810666]],"type":"LineString"},"id":"821ac1c719cea0bc73b068fb7b2a6343"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.054313,32.807902],[35.054443,32.807782],[35.05511,32.80818],[35.05529,32.808297],[35.05555,32.80806],[35.055558,32.807986],[35.055365,32.807993],[35.055454,32.807884],[35.054787,32.80745]],"type":"LineString"},"id":"8b01929de4febac5cd4daa7ea6033a96"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.054282,32.808757],[35.05446,32.808565]],"type":"LineString"},"id":"b573bd37a1c009e04d0bbece4a143c3a"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.054275,32.807873],[35.054309,32.807912],[35.05425,32.807983],[35.054732,32.8083],[35.054854,32.808385],[35.054594,32.808635]],"type":"LineString"},"id":"b70ae63e83e414959adc66e96f54eb63"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.055552,32.808019],[35.055669,32.807987],[35.055795,32.808072]],"type":"LineString"},"id":"cca134a2160c84b4fda97d01c7187b46"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.057254,32.809731],[35.057279,32.809583],[35.057456,32.809491]],"type":"LineString"},"id":"d06acba99f518baa63ef82b87984f931"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.056024,32.809852],[35.056435,32.809347],[35.05672,32.80908],[35.056926,32.808924],[35.057345,32.809203],[35.057463,32.809298],[35.057752,32.809587],[35.057907,32.80976],[35.058232,32.810089],[35.058513,32.810407],[35.058609,32.810537],[35.058412,32.810664],[35.058183,32.810824]],"type":"LineString"},"id":"dcc3f47f0b135b93233a52d8bed9052b"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.054805,32.808827],[35.055058,32.808985]],"type":"LineString"},"id":"e19356f825eb44e487e03b6a550480d4"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.054267,32.807881],[35.055143,32.807172],[35.055219,32.807112],[35.055026,32.806915],[35.054892,32.806812],[35.054514,32.807105],[35.05422,32.807366],[35.053851,32.807697],[35.05378,32.807792],[35.053583,32.807673],[35.053369,32.807835],[35.053935,32.808223]],"type":"LineString"},"id":"eea1e195389c0bb93105ccd485098acc"},{"type":"Feature","properties":{},"geometry":{"coordinates":[[35.055409,32.80819],[35.056278,32.808782],[35.056378,32.808673],[35.056752,32.808934],[35.0571,32.809177],[35.057297,32.809318],[35.057393,32.809441],[35.057498,32.809526],[35.057808,32.809851],[35.058152,32.810235],[35.058378,32.810475],[35.058366,32.810563],[35.058135,32.8107],[35.058039,32.810753],[35.057854,32.810552],[35.057565,32.810182],[35.057393,32.809953],[35.057275,32.809865],[35.057258,32.80978],[35.057242,32.809742],[35.057359,32.809653],[35.057527,32.809562]],"type":"LineString"},"id":"fa546f35b3a2cf176b0db06965d84370"}],"type":"FeatureCollection"}

When defining starting position and end position I found that using different tolerances give different outputs - as noted in the documentation, lines are merged on larger tolerances. However sometimes using { tolerance: 0.00009 }, and sometimes { tolerance: 0.0001 } to show routes is not optimized for my code - as I do not know when to set lower tolerance, and using too low tolerance returns no routes.

For example: Start Point - [35.0543, 32.8090] End Point - [35.054818, 32.808824] Required Tolerance - 0.0001

Start Point - [35.0543, 32.8090] End Point - [35.05626378,32.8080659095] Required Tolerance - 0.00009

Is there a way of calculating the minimum tolerance for a given start and end points?

Thank you Ofek

ofekkazes commented 1 year ago

My code snippet is as follows:

import nearestPointOnLine from "@turf/nearest-point-on-line";
import PathFinder from "geojson-path-finder";
import { point, points, polygon, lineString } from "@turf/helpers";

const pathFinder = new PathFinder.default({/*GeoJSON Input*/}, { tolerance: 0.00009 });
var first = nearestPointOnLine(res, point([35.0543, 32.8090]), {units: "meters"})
var last = nearestPointOnLine(res, point([35.05626374504888,32.808065019239095]), {units: "meters"})
const finder = pathFinder.findPath(first, last)
console.log(JSON.stringify(lineString(finder.path)))

perliedman commented 1 year ago

Hi there, you shouldn't have to adjust tolerance depending on start or end points. However, the start and end points you give, rounded to the current tolerance, must be vertices in the routing network. If you're not certain start and end points are in the network, what you usually want is to find the closest point of the network and set that as input - exactly how you do that is considered outside the scope of the library, but you can look at the demo code for inspiration.

Related issue: https://github.com/perliedman/geojson-path-finder/issues/86