Last active
January 17, 2017 23:04
-
-
Save MattReimer/e94524f1fedc7c1e5bd08f1fc8fda444 to your computer and use it in GitHub Desktop.
I was having trouble finding the line segment at a distance "dist" along a LineString using shapely. This is what I came up with.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def bisectLineSearch(dist, line): | |
""" | |
Use a bisect approach to get the index of the start of the line segment that contains | |
the distance specified. | |
:param dist: The distance along the line | |
:param line: The line in question | |
:return: index along the line just before we encounter 'dist' length | |
""" | |
arr = list(line.coords) | |
def _recurse(idx, ss, count=1): | |
# These are the expensive calls. We want to do them as little as possible. | |
pt = Point(arr[idx]) | |
# Past a certain point we start decrementing instead of halving | |
newss = ss / 2 if ss > 3 else ss - 1 | |
proj = line.project(pt) | |
dir = 1 if proj < dist else -1 | |
# Return if we've run out of steps or we've found the culprit | |
if proj == dist: | |
return idx | |
elif ss <= 0: | |
return idx if dir > 0 else idx - 1 | |
else: | |
return _recurse(int(idx + newss * dir), newss, count+1) | |
maxind = len(arr)-1 | |
lineind = _recurse(maxind, maxind) | |
# Note: we've got an endpoint condition here. If we're at the end of the line | |
# just return the last point so we can make a valid line segment out of it. | |
return lineind if lineind < maxind else lineind -1 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment