topic Re: Find the shortest possible line that intersects all points in Spatial Data Science Questions

Find the shortest possible line that intersects all points

MikeMcMahon — Mon, 01 Dec 2014 21:48:01 GMT

Hi All,

I thought this would be straightforward, but it's not (at least, not for me). I am trying to do exactly as the title describes - I have a point shapefile consisting of points, and I would like to find the shortest possible path (ie polyline) that goes through all of them.

I don't think Network Analyst is appropriate, since these are marine sampling sites, and there are no roads. I just want to find the shortest possible path the boat has to take to hit all of the sites.

If we want to get fancy, the following additions would be handy, but at this stage, I'd settle for anything:

could add a polygon shapefile showing the coastline, and the landmasses we have to avoid
start and end positions would also be handy to add (so that the last point doesn't leave us 100 miles offshore).

Has anyone had to do this?

Cheers!

Re: Find the shortest possible line that intersects all points

DanPatterson_Retired — Mon, 01 Dec 2014 21:53:15 GMT

What you refer to is a spanning tree. There is a toolbox that I created here, that works with projected shapefiles which reside in a folder not a geodatabase. The data must be projected since it is a planar tree and not a geodesic solution

Re: Find the shortest possible line that intersects all points

MikeMcMahon — Mon, 01 Dec 2014 22:21:06 GMT

Thank you Dan - that looks like exactly what I need. I haven't played around with it too much yet, but the initial results are very promising.

Thanks again!