Skip to content

Split a sequence of points so that each subsequence is close to a desired length.

License

Notifications You must be signed in to change notification settings

invisiblefunnel/linebreak

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

linebreak

Split a sequence of points so that each subsequence is close to a desired length. This is useful, e.g., if you want to break a geographic LineString into a MultiLineString without interpolating new points or altering existing points. The algorithm is an adaptation of text justification using dynamic programming. Linebreak was originally designed to split OSM highways into smaller segments for more efficient storage in a tiled format.

Go

Usage

package main

import (
    "fmt"
    "math"

    "github.com/invisiblefunnel/linebreak"
)

func main() {
    line := [][2]float64{{0, 0}, {3, 8}, {4, 16}, {10, 23}, {11, 28}}

    dists := make([]float64, len(line)-1)
    for i := 0; i < len(line)-1; i++ {
        dists[i] = pointDist(line[i], line[i+1])
    }

    targetDist := 11.0
    linebreak.Solve(dists, targetDist, func(i, j int) {
        fmt.Println(lineDist(line[i:j+1]), line[i:j+1])
    })

    // 8.54400374531753 [[0 0] [3 8]]
    // 8.06225774829855 [[3 8] [4 16]]
    // 14.318563970885672 [[4 16] [10 23] [11 28]]
}

func pointDist(a, b [2]float64) float64 {
    dx := a[0] - b[0]
    dy := a[1] - b[1]
    return math.Sqrt(dx*dx + dy*dy)
}

func lineDist(points [][2]float64) float64 {
    var length float64
    for i := 0; i < len(points)-1; i++ {
        length += pointDist(points[i], points[i+1])
    }
    return length
}

About

Split a sequence of points so that each subsequence is close to a desired length.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages