Last modified on: Thursday, July 12, 2018 at 20:25
Author Info
Name:
Hee Jae Hong
Mentor:
Richard Hennigan
End of Camp Presentation Content
Title of project:
Finding the Shortest Path Between Two Points on a Rough Terrain
Goal of the project:
Use topography and image analysis to find the shortest length of a path connecting two coordinate locations (specifically on the surface of the Earth) without exceeding a certain slope
Add the most representative image of your project here. (We recommend just 1 image, if you add more, we will make a collage of the images.)
Image:
Summary of Results:
The distance of the path is dependent on the relative elevations of the terrain, more specifically, the minimization of gradient at each point on the path.
Future work:
- Cut down run time
- Automatic detection of optimal threshold (adjust binarize level)...manipulate?
- Expand to any 3D surface
- Automatic detection of optimal threshold (adjust binarize level)...manipulate?
- Expand to any 3D surface
Additional Code Content
gradient=GradientFilter[terrainImage,1];bin=Binarize[gradient,threshold];
Note: Everything above this bar is in your 2 minute presentation. Make sure it fits on 2 slides.
Detailed Project Notes
Code
Code
shortestDistance[c1_,c2_,quality_,threshold_]:=Module[{pos1,pos2,dist,bounds,br,center,geoRange,realPixelSize,data,terrainImage,gradient,d,m,rel,xn,yn,edges,graph,v,bin,del,pg,path,pix1,pix2,fullTerrain,mag,mesh,newPath,dropOne,testPath,scaledLength,actualLength,$size},pos1=GeoPosition[c1];pos2=GeoPosition[c2];dist=GeoDistance[pos1,pos2];bounds=CoordinateBounds[{pos1[[1]],pos2[[1]]}];br=Max[#2-#1&@@@bounds];(*whatisthe#2and#1??*)center=Mean[{pos1[[1]],pos2[[1]]}];geoRange=Transpose[{center-br,center+br}];data=GeoElevationData[Transpose@geoRange];$size=Replace[quality,{1{50,50},2{200,200},3{300,300},4{400,400}}];realPixelSize=pixelSize[geoRange,$size];terrainImage=ImageResize[Image[QuantityMagnitude[data]],$size];gradient=GradientFilter[terrainImage,1];d=#2-#1&@@@geoRange;m=#1&@@@geoRange;rel=Round[Reverse[$size*(#[[1]]-m)/d]&/@{pos1,pos2}];{xn,yn}=ImageDimensions[gradient];edges=DeleteDuplicatesBy[Flatten@Table[{Pixel[i,j]Pixel[i-1,j],Pixel[i,j]Pixel[i+1,j],Pixel[i,j]Pixel[i,j-1],Pixel[i,j]Pixel[i,j+1]},{i,2,xn-1},{j,2,yn-1}],Sort];graph=Graph[edges];v=VertexList[graph];bin=Binarize[gradient,threshold];(*inlineabove,adjustgradientcutoff*)del=Pixel@@@PixelValuePositions[bin,White];{pix1,pix2}=Pixel@@@rel;(*commandbelowtakesthelongesttime*)pg=FastVertexDelete[graph,Complement[Intersection[v,del],{pix1,pix2}]];path=Replace[FindShortestPath[pg,pix1,pix2],Except[_List]{}];If[path==={},bin=bin;"Error: There is no path.",bin=ImageMultiply[bin,Erosion[ReplacePixelValue[ConstantImage[White,$size],List@@@pathBlack],1]];fullTerrain=ImageAdjust@Image[QuantityMagnitude[data]];mag=ImageDimensions[fullTerrain]/$size;mesh=ImageMesh[bin,Method"Exact",DataRangeTranspose[{{1,1},ImageDimensions[bin]}]];newPath=List@@@path[[2;;-2]];dropOne=Function[path,Replace[SelectFirst[Range[2,Length[path]-1],RegionDisjoint[mesh,Line[Delete[path,#]]]&],{d_IntegerDelete[path,d],_path}]];testPath=FixedPoint[dropOne,newPath];scaledLength=N@Total[EuclideanDistance@@@Partition[testPath,2,1]](*withdropOnefunction*);actualLength=scaledLength*realPixelSize(*inmiles*);Grid[{{"Raw Graph: ",ImageResize[HighlightImage[bin,Line[List@@@path]],500]},{"Smoothened Graph: ",ImageResize[HighlightImage[bin,Line[testPath]],500]},{"Terrain with path marked in red: ",HighlightImage[fullTerrain,{Line[mag*{##}&@@@testPath]}]},{"Distance: ",actualLength},{HighlightImage[ImageAdjust@GradientFilter[terrainImage,1],{Line[{##}-0.5&@@@testPath]}]}},AlignmentLeft]]]
Conclusions in Detail
Conclusions in Detail
The threshold in binarization does not correspond with the actual slope in a way that is easy to notice: the correlation between threshold and slope is not well defined and is hard to implement because the threshold is based on relative steepness while slope is a set numerical value at each point.
All Visualizations
All Visualizations
Data Sources Links/References
Data Sources Links/References
no data required for project
Background Info Links/References
Background Info Links/References
◼
Rick
◼
wolfram community
Keywords
Keywords
◼
binarize
◼
vertex delete
◼
gradient
Other information
Other information