Keeping Your Maps Accurate: Detecting Loops and Intersections in Polylines

Introduction

Polylines are an essential component in mapping and navigation applications, used to represent the geometry of roads and transportation networks. Each polyline is a series of connected line segments defined by consecutive points in a list of (latitude, longitude) coordinates. Polylines can be stored in encoded format, which, when decoded, yields a list of lat, lng pairs. Polylines can be stored in encoded format as explained here, https://developers.google.com/maps/documentation/utilities/polylinealgorithm

However, polylines can be subject to errors and inaccuracies. In the context of this post, the error we would be referring to would be because of incorrect stop locations of some intermediate stops in a route. These issues are indicated by the intersections or loops in the polyline, which can cause problems for applications that rely on accurate polyline data.

In this post, we'll focus on detecting intersection issues caused by incorrect stop locations using a simple algorithm. We'll examine an example of an incorrect polyline that contains an intersection due to a misplaced stop location. Finally, we'll demonstrate how to programmatically detect issues in stored polylines to ensure that mapping and navigation applications function accurately and reliably.

Understanding polyline issues

In the above image, the intersection in this polyline is clearly visible. Issue is because of the incorrect stop location of Sewri - Chembur Rd, GTB Nagar, Lalbaug, Sion East, Sion. If the location of this stop is correctly put on the other side of road, this issue would not occur.

Now, let's assume we have this polyline stored in our database and we want to detect any issues in the stored polyline. This will help us keeping our maps accurate.

When we moved the stop location to the other side of road, this issue gets resolved.

Programmatic detection of intersections in polyline

Although there are some advanced intersection detection algorithms such as Bentley-Ottmann or Sweep Line Algorithm, we'll try to detect intersections using a simple algorithm which is very easy to understand.

Algorithm:

The algorithm for detecting self-intersections and loops in a polyline involves comparing each line segment of the polyline with all the other segments to detect any intersection between them. If an intersection is found, it indicates that the polyline has a self-intersection or a loop.

We iterate over each segment of the polyline, and for each segment, we iterate over all the other segments to check for intersection. We use the equation of lines to check for intersection between two line segments. If an intersection is detected, we add the intersection point to a list of intersections.

Code:

def detect_polyline_issues(polyline):
    """
    Detects any issues (loops or intersections) in an open polyline. Returns list of intersections in a polyline
    """
    def intersect(p1, q1, p2, q2):
        """
        Returns True if the line segments p1-q1 and p2-q2 intersect.
        """
        o1 = orientation(p1, q1, p2)
        o2 = orientation(p1, q1, q2)
        o3 = orientation(p2, q2, p1)
        o4 = orientation(p2, q2, q1)

        if (o1 != o2 and o3 != o4) or (o1 == 0 and on_segment(p1, p2, q1)) or (o2 == 0 and on_segment(p1, q2, q1)) or (o3 == 0 and on_segment(p2, p1, q2)) or (o4 == 0 and on_segment(p2, q1, q2)):
            return True

        return False

    def orientation(p, q, r):
        """
        Returns the orientation of the ordered triplet (p, q, r).
        """
        val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
        if val == 0:
            return 0
        return 1 if val > 0 else 2

    def on_segment(p, q, r):
        """
        Returns True if point q lies on line segment pr.
        """
        if q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1]):
            return True

        return False
        n = len(polyline)
        if n < 4:
            return False

    n = len(polyline)
    intersections = set()
    if n < 4:
        return []

    # Check for intersections
    for i in range(n - 3):
        for j in range(i + 2, n - 1):
            if intersect(polyline[i], polyline[i + 1], polyline[j], polyline[j + 1]):
                intersections.add(polyline[i])
    if len(intersections) > 0:
        return list(intersections)

    return []

Here is a brief explanation of each function in the detect_polyline_issues method:

detect_polyline_issues(polyline) - This is the main function that takes in a polyline, which is a list of (latitude, longitude) pairs, and returns a list of intersections in the polyline.

intersect(p1, q1, p2, q2) - This function takes in two line segments defined by their endpoints, p1 and q1 for the first segment and p2 and q2 for the second segment, and determines whether they intersect. It returns True if they intersect and False otherwise.

orientation(p, q, r) - This function takes in three points, p, q, and r, and determines their orientation. Specifically, it calculates the cross product of vectors pq and qr. If this value is positive, the orientation is counter-clockwise, if it is negative the orientation is clockwise, and if it is zero, the points are collinear.

on_segment(p, q, r) - This function takes in three points, p, q, and r, and determines whether q lies on the line segment pr. It returns True if q lies on the line segment and False otherwise.

The main function first checks if the polyline has fewer than 4 points, in which case it cannot contain any intersections. If the polyline has 4 or more points, it loops through all pairs of line segments in the polyline and checks if they intersect using the intersect function. If an intersection is found, the intersections set is updated with the intersection point. Finally, the function returns a list of intersection points or an empty list if no intersections were found.

The limitation of this method is that its a little slow as compared to advanced intersection detection algorithms and this should only be used when your routes aren't too big.

Conclusion

To detect polyline issues, we have implemented a simple algorithm based on line segment intersection detection.
By running this algorithm on stored polylines, we can identify any incorrect stop locations that cause loops or intersections in the polyline, allowing us to correct these errors and ensure accurate polyline data for navigation and mapping applications.