How to get buffer polygon coordinates (latitude and longitude) in iOS?

Question

I have created one polygon on map with some set of coordinates. I need help regarding making one buffered polygon with some given distance outside of original polygon border.

so what i need a method with such algorithm in which i pass set of coordinates as input and should get buffered set of coordinates as output.

I tried to achieve this by using arcgis library for ios with bufferGeometry method of AGSGeometryEngine but problem is, this is tightly coupled and only will work their GIS Map but I am using Mapbox which is different Map. So I want one generic method which can resolve my problem independent to map.

Answer 1

The solution of @Ravikant Paudel though comprehensive didn't work for me so I have implemented the approach myself. Also, I implemented the approach in kotlin and adding it here so that someone else who is facing a similar problem will find it helpful.

Approach:

1. Find the angle of the angle bisector theta for every vertice of the polygon.
2. Draw a circle with radius = bufferedDistance / sin(angleBisctorTheta)
3. Find intersections of the circle and angle bisector.
4. Out of the 2 intersection points the one inside the polygon will give you the buffered vertice for the shrunk polygon and the outside point for the buffered polygon.
5. This approach does not account for the corner cases in which both points somehow fall inside or outside the polygon -> in which case the buffered polygon formed will be malformed.

Code:

private fun computeAngleBisectorTheta(
    prevLatLng: LatLng,
    currLatLng: LatLng,
    nextLatLng: LatLng
): Double {
    var phiBisector = 0.0
    try {
        val aPrime = getDeltaPrimeVector(prevLatLng, currLatLng)
        val cPrime = getDeltaPrimeVector(nextLatLng, currLatLng)

        val thetaA = atan2(aPrime[1], aPrime[0])
        val thetaC = atan2(cPrime[1], cPrime[0])

        phiBisector = (thetaA + thetaC) / 2.0
    } catch (e: Exception) {
        logger.error("[Error] in computeAngleBisectorSlope: $e")
    }
    return phiBisector
}

private fun getDeltaPrimeVector(
    aLatLng: LatLng,
    bLatLng: LatLng
): ArrayList<Double> {
    val arrayList: ArrayList<Double> = ArrayList<Double>(2)
    try {
        val aX = convertToXY(aLatLng.latitude)
        val aY = convertToXY(aLatLng.longitude)
        val bX = convertToXY(bLatLng.latitude)
        val bY = convertToXY(bLatLng.longitude)
        arrayList.add((aX - bX))
        arrayList.add((aY - bY))
    } catch (e: Exception) {
        logger.error("[Error] in getDeltaPrimeVector: $e")
    }
    return arrayList
}
private fun convertToXY(coordinate: Double) =
    EARTH_RADIUS * toRad(coordinate)

private fun convertToLatLngfromXY(coordinate: Double) =
    toDegrees(coordinate / EARTH_RADIUS)

private fun computeBufferedVertices(
    angle: Double, bufDis: Int,
    centerLatLng: LatLng
): ArrayList<LatLng> {
    var results = ArrayList<LatLng>()
    try {
        val distance = bufDis / sin(angle)
        var slope = tan(angle)
        var inverseSlopeSquare = sqrt(1 + slope * slope * 1.0)
        var distanceByInverseSlopeSquare = distance / inverseSlopeSquare
        var slopeIntoDistanceByInverseSlopeSquare = slope * distanceByInverseSlopeSquare

        var p1X: Double = convertToXY(centerLatLng.latitude) + distanceByInverseSlopeSquare
        var p1Y: Double =
            convertToXY(centerLatLng.longitude) + slopeIntoDistanceByInverseSlopeSquare
        var p2X: Double = convertToXY(centerLatLng.latitude) - distanceByInverseSlopeSquare
        var p2Y: Double =
            convertToXY(centerLatLng.longitude) - slopeIntoDistanceByInverseSlopeSquare

        val tempLatLng1 = LatLng(convertToLatLngfromXY(p1X), convertToLatLngfromXY(p1Y))
        results.add(tempLatLng1)
        val tempLatLng2 = LatLng(convertToLatLngfromXY(p2X), convertToLatLngfromXY(p2Y))
        results.add(tempLatLng2)
    } catch (e: Exception) {
        logger.error("[Error] in computeBufferedVertices: $e")
    }
    return results
}

private fun getVerticesOutsidePolygon(
    verticesArray: ArrayList<LatLng>,
    polygon: ArrayList<LatLng>
): LatLng {
    if (isPointInPolygon(
            verticesArray[0].latitude,
            verticesArray[0].longitude,
            polygon
        )
    ) {
        if (sPointInPolygon(
                verticesArray[1].latitude,
                verticesArray[1].longitude,
                polygon
            )
        ) {
            logger.error("[ERROR] Malformed polygon! Both Vertices are inside the polygon! $verticesArray")
        } else {
            return verticesArray[1]
        }
    } else {
        if (PolygonGeofenceHelper.isPointInPolygon(
                verticesArray[1].latitude,
                verticesArray[1].longitude,
                polygon
            )
        ) {
            return verticesArray[0]
        } else {
            logger.error("[ERROR] Malformed polygon! Both Vertices are outside the polygon!: $verticesArray")
        }
    }
    //returning a vertice anyway because there is no fall back policy designed if both vertices are inside or outside the polygon
    return verticesArray[0]
}

private fun toRad(angle: Double): Double {
    return angle * Math.PI / 180
}

private fun toDegrees(radians: Double): Double {
    return radians * 180 / Math.PI
}

private fun getVerticesInsidePolygon(
    verticesArray: ArrayList<LatLng>,
    polygon: ArrayList<LatLng>
): LatLng {
    if (isPointInPolygon(
            verticesArray[0].latitude,
            verticesArray[0].longitude,
            polygon
        )
    ) {
        if (isPointInPolygon(
                verticesArray[1].latitude,
                verticesArray[1].longitude,
                polygon
            )
        ) {
            logger.error("[ERROR] Malformed polygon! Both Vertices are inside the polygon! $verticesArray")
        } else {
            return verticesArray[0]
        }
    } else {
        if (PolygonGeofenceHelper.isPointInPolygon(
                verticesArray[1].latitude,
                verticesArray[1].longitude,
                polygon
            )
        ) {
            return verticesArray[1]
        } else {
            logger.error("[ERROR] Malformed polygon! Both Vertices are outside the polygon!: $verticesArray")
        }
    }
    //returning a vertice anyway because there is no fall back policy designed if both vertices are inside or outside the polygon
    return LatLng(0.0, 0.0)
}
fun getBufferedPolygon(
    polygon: ArrayList<LatLng>,
    bufferDistance: Int,
    isOutside: Boolean
): ArrayList<LatLng> {
    var bufferedPolygon = ArrayList<LatLng>()
    var isBufferedPolygonMalformed = false
    try {
        for (i in 0 until polygon.size) {
            val prevLatLng: LatLng = polygon[if (i - 1 < 0) polygon.size - 1 else i - 1]
            val centerLatLng: LatLng = polygon[i]
            val nextLatLng: LatLng = polygon[if (i + 1 == polygon.size) 0 else i + 1]
            val computedVertices =
                computeBufferedVertices(
                    computeAngleBisectorTheta(
                        prevLatLng, centerLatLng, nextLatLng
                    ), bufferDistance, centerLatLng
                )
            val latLng = if (isOutside) {
                getVerticesOutsidePolygon(
                    computedVertices,
                    polygon
                )
            } else {
                getVerticesInsidePolygon(
                    computedVertices,
                    polygon
                )
            }
            if (latLng.latitude == 0.0 && latLng.longitude == 0.0) {
                isBufferedPolygonMalformed = true
                break
            }
            bufferedPolygon.add(latLng)
        }
        if (isBufferedPolygonMalformed) {
            bufferedPolygon = polygon
            logger.error("[Error] Polygon generated is malformed returning the same polygon: $polygon , $bufferDistance, $isOutside")
        }
    } catch (e: Exception) {
        logger.error("[Error] in getBufferedPolygon: $e")
    }
    return bufferedPolygon
}

You'll need to pass an array of points present in the polygon in the code and the buffer distance the third param is to get the outside buffer or the inside buffer. (Note: I am assuming that the vertices in this list are adjacent to each other).

I have tried to keep this answer as comprehensive as possible. Please feel free to suggest any improvements or a better approach.

You can find the detailed math behind the above code on my portfolio page.

1. Finding angle bisector
2. To approximate latitude and longitude to a 2D cartesian coordinate system.
3. To check if the point is inside a polygon I am using the approach mentioned in this geeks for geeks article

Answer 2

I have same problem in my app and finally found the solution by the help of this site

I am an android developer and my code may not be useful to you but the core concept is same.

1. At first we need to find the bearing of the line with the help of two points LatLng points.(i have done by using computeDistanceAndBearing(double lat1, double lon1,double lat2, double lon2) function)

2. Now to get the buffering of certain point we need to give the buffering distance ,LatLng point and bearing (which i obtain from computeDistanceAndBearing function).(I have done this by using computeDestinationAndBearing(double lat1, double lon1,double brng, double dist) function ). from single LatLng point we get two points by producing them with their bearing with certain distance.

3. Now we need to find the interestion point of the two point to get the buffering that we want. for this remember to take new obtain point and bearing of another line and same with another. This helps to obtain new intersection point with buffering you want.(i have done this in my function computeIntersectionPoint(LatLng p1, double brng1, LatLng p2, double brng2))

4. Do this to all the polygon points and then you get new points whichyou joint to get buffering.

This is the way i have done in my android location app whis is

Here is my code //computeDistanceAndBearing(double lat1, double lon1, double lat2, double lon2)

public static double[] computeDistanceAndBearing(double lat1, double lon1,
                                                 double lat2, double lon2) {
    // Based on http://www.ngs.noaa.gov/PUBS_LIB/inverse.pdf
    // using the "Inverse Formula" (section 4)
    double results[] = new double[3];
    int MAXITERS = 20;
    // Convert lat/long to radians
    lat1 *= Math.PI / 180.0;
    lat2 *= Math.PI / 180.0;
    lon1 *= Math.PI / 180.0;
    lon2 *= Math.PI / 180.0;

    double a = 6378137.0; // WGS84 major axis
    double b = 6356752.3142; // WGS84 semi-major axis
    double f = (a - b) / a;
    double aSqMinusBSqOverBSq = (a * a - b * b) / (b * b);

    double L = lon2 - lon1;
    double A = 0.0;
    double U1 = Math.atan((1.0 - f) * Math.tan(lat1));
    double U2 = Math.atan((1.0 - f) * Math.tan(lat2));

    double cosU1 = Math.cos(U1);
    double cosU2 = Math.cos(U2);
    double sinU1 = Math.sin(U1);
    double sinU2 = Math.sin(U2);
    double cosU1cosU2 = cosU1 * cosU2;
    double sinU1sinU2 = sinU1 * sinU2;

    double sigma = 0.0;
    double deltaSigma = 0.0;
    double cosSqAlpha = 0.0;
    double cos2SM = 0.0;
    double cosSigma = 0.0;
    double sinSigma = 0.0;
    double cosLambda = 0.0;
    double sinLambda = 0.0;

    double lambda = L; // initial guess
    for (int iter = 0; iter < MAXITERS; iter++) {
        double lambdaOrig = lambda;
        cosLambda = Math.cos(lambda);
        sinLambda = Math.sin(lambda);
        double t1 = cosU2 * sinLambda;
        double t2 = cosU1 * sinU2 - sinU1 * cosU2 * cosLambda;
        double sinSqSigma = t1 * t1 + t2 * t2; // (14)
        sinSigma = Math.sqrt(sinSqSigma);
        cosSigma = sinU1sinU2 + cosU1cosU2 * cosLambda; // (15)
        sigma = Math.atan2(sinSigma, cosSigma); // (16)
        double sinAlpha = (sinSigma == 0) ? 0.0 : cosU1cosU2 * sinLambda
                / sinSigma; // (17)
        cosSqAlpha = 1.0 - sinAlpha * sinAlpha;
        cos2SM = (cosSqAlpha == 0) ? 0.0 : cosSigma - 2.0 * sinU1sinU2
                / cosSqAlpha; // (18)

        double uSquared = cosSqAlpha * aSqMinusBSqOverBSq; // defn
        A = 1 + (uSquared / 16384.0) * // (3)
                (4096.0 + uSquared * (-768 + uSquared * (320.0 - 175.0 * uSquared)));
        double B = (uSquared / 1024.0) * // (4)
                (256.0 + uSquared * (-128.0 + uSquared * (74.0 - 47.0 * uSquared)));
        double C = (f / 16.0) * cosSqAlpha * (4.0 + f * (4.0 - 3.0 * cosSqAlpha)); // (10)
        double cos2SMSq = cos2SM * cos2SM;
        deltaSigma = B
                * sinSigma
                * // (6)
                (cos2SM + (B / 4.0)
                        * (cosSigma * (-1.0 + 2.0 * cos2SMSq) - (B / 6.0) * cos2SM
                        * (-3.0 + 4.0 * sinSigma * sinSigma)
                        * (-3.0 + 4.0 * cos2SMSq)));

        lambda = L
                + (1.0 - C)
                * f
                * sinAlpha
                * (sigma + C * sinSigma
                * (cos2SM + C * cosSigma * (-1.0 + 2.0 * cos2SM * cos2SM))); // (11)

        double delta = (lambda - lambdaOrig) / lambda;
        if (Math.abs(delta) < 1.0e-12) {
            break;
        }
    }

    double distance = (b * A * (sigma - deltaSigma));
    results[0] = distance;
    if (results.length > 1) {
        double initialBearing = Math.atan2(cosU2 * sinLambda, cosU1 * sinU2
                - sinU1 * cosU2 * cosLambda);
        initialBearing *= 180.0 / Math.PI;
        results[1] = initialBearing;
        if (results.length > 2) {
            double finalBearing = Math.atan2(cosU1 * sinLambda, -sinU1 * cosU2
                    + cosU1 * sinU2 * cosLambda);
            finalBearing *= 180.0 / Math.PI;
            results[2] = finalBearing;
        }
    }

    return results;
}

//computeDestinationAndBearing(double lat1, double lon1,double brng, double dist)

public static double[] computeDestinationAndBearing(double lat1, double lon1,
                                                    double brng, double dist) {
    double results[] = new double[3];
    double a = 6378137, b = 6356752.3142, f = 1 / 298.257223563; // WGS-84
    // ellipsiod
    double s = dist;
    double alpha1 = toRad(brng);
    double sinAlpha1 = Math.sin(alpha1);
    double cosAlpha1 = Math.cos(alpha1);

    double tanU1 = (1 - f) * Math.tan(toRad(lat1));
    double cosU1 = 1 / Math.sqrt((1 + tanU1 * tanU1)), sinU1 = tanU1 * cosU1;
    double sigma1 = Math.atan2(tanU1, cosAlpha1);
    double sinAlpha = cosU1 * sinAlpha1;
    double cosSqAlpha = 1 - sinAlpha * sinAlpha;
    double uSq = cosSqAlpha * (a * a - b * b) / (b * b);
    double A = 1 + uSq / 16384
            * (4096 + uSq * (-768 + uSq * (320 - 175 * uSq)));
    double B = uSq / 1024 * (256 + uSq * (-128 + uSq * (74 - 47 * uSq)));
    double sinSigma = 0, cosSigma = 0, deltaSigma = 0, cos2SigmaM = 0;
    double sigma = s / (b * A), sigmaP = 2 * Math.PI;

    while (Math.abs(sigma - sigmaP) > 1e-12) {
        cos2SigmaM = Math.cos(2 * sigma1 + sigma);
        sinSigma = Math.sin(sigma);
        cosSigma = Math.cos(sigma);
        deltaSigma = B
                * sinSigma
                * (cos2SigmaM + B
                / 4
                * (cosSigma * (-1 + 2 * cos2SigmaM * cos2SigmaM) - B / 6
                * cos2SigmaM * (-3 + 4 * sinSigma * sinSigma)
                * (-3 + 4 * cos2SigmaM * cos2SigmaM)));
        sigmaP = sigma;
        sigma = s / (b * A) + deltaSigma;
    }

    double tmp = sinU1 * sinSigma - cosU1 * cosSigma * cosAlpha1;
    double lat2 = Math.atan2(sinU1 * cosSigma + cosU1 * sinSigma * cosAlpha1,
            (1 - f) * Math.sqrt(sinAlpha * sinAlpha + tmp * tmp));
    double lambda = Math.atan2(sinSigma * sinAlpha1, cosU1 * cosSigma - sinU1
            * sinSigma * cosAlpha1);
    double C = f / 16 * cosSqAlpha * (4 + f * (4 - 3 * cosSqAlpha));
    double L = lambda
            - (1 - C)
            * f
            * sinAlpha
            * (sigma + C * sinSigma
            * (cos2SigmaM + C * cosSigma * (-1 + 2 * cos2SigmaM * cos2SigmaM)));
    double lon2 = (toRad(lon1) + L + 3 * Math.PI) % (2 * Math.PI) - Math.PI; // normalise
    // to
    // -180...+180

    double revAz = Math.atan2(sinAlpha, -tmp); // final bearing, if required

    results[0] = toDegrees(lat2);
    results[1] = toDegrees(lon2);
    results[2] = toDegrees(revAz);
    return results;
}

private static double toRad(double angle) {
    return angle * Math.PI / 180;
}

private static double toDegrees(double radians) {
    return radians * 180 / Math.PI;
}

//computeIntersectionPoint(LatLng p1, double brng1, LatLng p2, double brng2)

    public static LatLng computeIntersectionPoint(LatLng p1, double brng1, LatLng p2, double brng2) {
    double lat1 = toRad(p1.latitude), lng1 = toRad(p1.longitude);
    double lat2 = toRad(p2.latitude), lng2 = toRad(p2.longitude);
    double brng13 = toRad(brng1), brng23 = toRad(brng2);
    double dlat = lat2 - lat1, dlng = lng2 - lng1;
    double delta12 = 2 * Math.asin(Math.sqrt(Math.sin(dlat / 2) * Math.sin(dlat / 2)
            + Math.cos(lat1) * Math.cos(lat2) * Math.sin(dlng / 2) * Math.sin(dlng / 2)));

    if (delta12 == 0) return null;


    double initBrng1 = Math.acos((Math.sin(lat2) - Math.sin(lat1) * Math.cos(delta12)) / (Math.sin(delta12) * Math.cos(lat1)));

    double initBrng2 = Math.acos((Math.sin(lat1) - Math.sin(lat2) * Math.cos(delta12)) / (Math.sin(delta12) * Math.cos(lat2)));

    double brng12 = Math.sin(lng2 - lng1) > 0 ? initBrng1 : 2 * Math.PI - initBrng1;
    double brng21 = Math.sin(lng2 - lng1) > 0 ? 2 * Math.PI - initBrng2 : initBrng2;


    double alpha1 = (brng13 - brng12 + Math.PI) % (2 * Math.PI) - Math.PI; 
    double alpha2 = (brng21 - brng23 + Math.PI) % (2 * Math.PI) - Math.PI; 

    double alpha3 = Math.acos(-Math.cos(alpha1) * Math.cos(alpha2) + Math.sin(alpha1) * Math.sin(alpha2) * Math.cos(delta12));
    double delta13 = Math.atan2(Math.sin(delta12) * Math.sin(alpha1) * Math.sin(alpha2), Math.cos(alpha2) + Math.cos(alpha1) * Math.cos(alpha3));
    double lat3 = Math.asin(Math.sin(lat1) * Math.cos(delta13) + Math.cos(lat1) * Math.sin(delta13) * Math.cos(brng13));
    double dlng13 = Math.atan2(Math.sin(brng13) * Math.sin(delta13) * Math.cos(lat1), Math.cos(delta13) - Math.sin(lat1) * Math.sin(lat3));
    double lng3 = lng1 + dlng13;

    return new LatLng(toDegrees(lat3), (toDegrees(lng3) + 540) % 360 - 180); 
}

I will suggest you to go through the the above site and get the knowledge as i had also done the same.

Hope this may help , i know the is not in ios but the concept is same as i done my project by changing code of javascript.

Cheers !!!

Answer 3

My requirement was something similar to this. I ended up writing up my own algo for this. https://github.com/RanaRanvijaySingh/PolygonBuffer
All you need to use is this line

double distance = 0.0001;
List bufferedPolygonList = AreaBuffer.buffer(pointList, distance);

It gives you a list of buffered polygon points at a given distance from your original polygon.

Answer 4

I would recommend to use Turf.js library for buffering and many basic gis operations. You would be able to retrieve each edge from the path that returned. For geometry buffer, it is easy to use, quite light weighted and it works without any problem for my applications using MapBox.js or leaflet.
More details : Turf.js Buffer

But if you are looking for a geodesic distance buffer that could be problem. I would use Arcgis Javascript API

Answer 5

Take a look at BOOST this is a big C++ library, you may find library/source code for almost everything up there like, buffer methods with different types such as miter,round,square.

Just install the latest version of the Boost which I guess is 1.58.0 right now, and take a look at BOOST/Geometry/Strategies/Cartesian/buffer[Something]-Square/Miter/Round

Here it is a good document

You need to convert your geodetic coordinates (lat/long) to cartesian (x/y) and use the Boost library and reverse the conversion. you do not need to use ArcGIS or any other GIS library at all.