CODEWITHSUNDEEP
algorithmmathgeo
Ryan
Ryan

Reputation: 877

Nearest road given latitude & longitude

I have a database which contains all the waypoints for each road in the UK.

I am trying to build a navigation app, given the users latitude & longitude it will calculate the nearest road from the database & display the name

Snippet of JSON representation of database

[
{
    "NAME": "Trinity Road",
    "coordinates": [
        [
            1.7595267,
            52.4778475
        ],
        [
            1.7587864,
            52.4774
        ]
    ]
},
{
    "NAME": "Wilde Street",
    "coordinates": [
        [
            1.7593497,
            52.4795499
        ],
        [
            1.7594677,
            52.4795041
        ],
        [
            1.7598164,
            52.4793277
        ]
    ]
}
]

The issue I have come against is correctly finding the nearest road. I cannot find any suitable algorithms that given a point will find the nearest path/line

It cannot simply compare the coordinates as the nearest road may be between 2 way-points (rules out 'Closest pair of points problem').

Can someone suggest a suitable algorithm?

Best possible solution I can think of is a weighted grid/matrix where the roads have weights depending on their proximity to the user & then to pick the highest value road immediately surrounding the user (but this could be expensive).

I would like to solve this without using a web api such as google-maps, nor PostGIS (having to use sqlite - mobile app)

Upvotes: 0

Views: 1022

Answers (2)

AlexWien
AlexWien

Reputation: 28727

Using a quadtree is the correct approach to limit the search space. Parametrize the quad tree such that it will not have more than 100 lines per quad node.

You don't need an (complex) voronoi diagram.

After the search in the quad tree the result will be a list of lines that overlapp the quad node.

Now use a distanceToLineSegment(Point, point0, point1); (search Internet for that name)

take the shortest distance.

you have to tranform the Points on the fly Prior to the call of distanceToLineSegment, sucht that they are in cartesian space. Use the Center of the quad node as tranformation Center.

Upvotes: 0

Cybercartel
Cybercartel

Reputation: 12592

You can use a r-tree or a quadtree to limit the search space and then a voronoi diagram to find the nearest road. Then you can use 2 points or more of the road to feed the voronoi diagram and then search the diagram for the voronoi cell containing the location. Perhaps you can try a weighted voronoi diagram. You can download my php class additivley weighted voronoi diagram @ https://awvd.codeplex.com/.

Upvotes: 3

Related Questions