SDPTeam15/PolyEvents

View on GitHub
app/src/main/java/com/github/sdpteam15/polyevents/model/map/LatLngOperator.kt

Summary

Maintainability
A
0 mins
Test Coverage
A
98%
package com.github.sdpteam15.polyevents.model.map

import com.github.sdpteam15.polyevents.model.entity.RouteNode
import com.github.sdpteam15.polyevents.model.map.LatLngOperator.Polygon.Vertex
import com.github.sdpteam15.polyevents.model.map.LatLngOperator.PolygonOperationType.*
import com.google.android.gms.maps.model.LatLng
import java.util.*
import java.util.function.BiPredicate
import kotlin.math.abs
import kotlin.math.atan
import kotlin.math.sqrt

/**
 * Object containing methods to compute various metrics with LatLng
 * TODO? take into account the curvature of the earth to compute distances instead of considering latitude and longitude as cartesian coordinates
 */
object LatLngOperator {
    /**
     * Used to check if floating point values are close enough to be considered as equal
     */
    const val epsilon = 1e-10

    /**
     * Returns the coordinate-wise subtraction of the first point by the second one
     * @param point1 the first point
     * @param point2 the second point
     * @return the subtraction of point 1 by point 2
     */
    fun minus(point1: LatLng, point2: LatLng) =
        LatLng(point1.latitude - point2.latitude, point1.longitude - point2.longitude)

    /**
     * Returns the coordinate-wise addition of the first point by the second one
     * @param point1 the first point
     * @param point2 the second point
     * @return the addition of point 1 by point 2
     */
    fun plus(point1: LatLng, point2: LatLng) =
        LatLng(point1.latitude + point2.latitude, point1.longitude + point2.longitude)

    /**
     * Returns the coordinate-wise multiplication of the point by a scalar
     * @param point the point to multiply
     * @param nbr the scalar to multiply
     * @return the multiplication of the point by the given scalar
     */
    fun time(point: LatLng, nbr: Double) =
        LatLng(point.latitude * nbr, point.longitude * nbr)

    /**
     * Returns the coordinate-wise division of the point by a scalar
     * @param point the point to be divided
     * @param nbr the scalar to divide by
     * @return the division of the point by the given scalar
     */
    fun divide(point: LatLng, nbr: Double) =
        LatLng(point.latitude / nbr, point.longitude / nbr)

    /**
     * Returns the mean of the points
     * @param points list of points
     * @return the mean of the points
     */
    fun mean(points: List<LatLng>): LatLng {
        var latitude = 0.0
        var longitude = 0.0
        var nbr = 0
        for (point in points) {
            latitude += point.latitude
            longitude += point.longitude
            nbr += 1
        }
        return if (nbr != 0)
            LatLng(latitude / nbr, longitude / nbr)
        else
            LatLng(0.0, 0.0)
    }

    /**
     * Returns the angle in degrees between the horizontal x axis and the line passing through the two given points
     * @param start the first point
     * @param end the second point
     * @return the angle between the x axis and the line passing though start and end
     */
    fun angle(start: LatLng, end: LatLng) =
        (atan((start.latitude - end.latitude) / (start.longitude - end.longitude)) / Math.PI) * 180

    /**
     * Checks whether two angles are close enough to each other, i.e. if the difference between the lines described by the given angles is less than 20°.
     *
     * @param angle1 the first angle
     * @param angle2 the second angle
     * @return true if the angles are less than 20° apart, else return false
     */
    fun isTooParallel(angle1: Double, angle2: Double): Boolean {
        if (!(angle1 in -90.0..90.0 && angle2 in -90.0..90.0))
            throw IllegalArgumentException("angles must be in the range -90.0..90.0")
        var dif = abs(angle1 - angle2)
        dif = if (dif > 90) 180 - dif else dif
        return dif < 20
    }

    /**
     * Computes the scalar product between 2 points
     * @param point1 first point
     * @param point2 second point
     * @return distance between the points
     */
    fun scalar(point1: LatLng, point2: LatLng) =
        point1.latitude * point2.latitude + point1.longitude * point2.longitude

    /**
     * Computes the euclidean distance between 2 points
     * @param start first point
     * @param end second point
     * @return distance between the points
     */
    fun euclideanDistance(start: LatLng, end: LatLng): Double =
        euclideanDistance(start.longitude, start.latitude, end.longitude, end.latitude)

    /**
     * Computes the squared euclidean norm
     * @param point point
     */
    fun squaredNorm(point: LatLng) =
        squaredNorm(point.longitude, point.latitude)

    /**
     * Computes the euclidean norm
     * @param point point
     */
    fun norm(point: LatLng) =
        sqrt(squaredNorm(point))

    /**
     * Computes the squared euclidean norm
     * @param dx distance in x
     * @param dy distance in y
     */
    fun squaredNorm(dx: Double, dy: Double) =
        dx * dx + dy * dy

    /**
     * Computes the euclidean distance between 2 points
     * @param startX first point x coordinate
     * @param startY first point y coordinate
     * @param endX second point x coordinate
     * @param endY second point y coordinate
     * @return distance between the points
     */
    fun euclideanDistance(startX: Double, startY: Double, endX: Double, endY: Double): Double =
        sqrt(squaredEuclideanDistance(startX, startY, endX, endY))

    /**
     * Computes the squared euclidean distance between 2 points
     * @param startX first point x coordinate
     * @param startY first point y coordinate
     * @param endX second point x coordinate
     * @param endY second point y coordinate
     * @return squared euclidean distance between the points
     */
    fun squaredEuclideanDistance(
        startX: Double,
        startY: Double,
        endX: Double,
        endY: Double
    ): Double {
        val dx = startX - endX
        val dy = startY - endY
        return squaredNorm(dx, dy)
    }

    /**
     * Computes the squared euclidean distance between 2 points
     * @param start first point
     * @param end second point
     * @return squared euclidean distance between the points
     */
    fun squaredEuclideanDistance(start: LatLng, end: LatLng): Double =
        squaredEuclideanDistance(start.longitude, start.latitude, end.longitude, end.latitude)

    /**
     * Returns the intersection point between 2 segments
     * @param start1 start of the first segment
     * @param end1 end of the first segment
     * @param start2 start of the second segment
     * @param end2 end of the second segment
     * @return The intersection point of the two segments, null if the two segments do not intersect
     */
    fun getIntersection(start1: LatLng, end1: LatLng, start2: LatLng, end2: LatLng): LatLng? {

        val coefs = getIntersectionCoefficients(start1, end1, start2, end2) ?: return null
        return plus(start1, time(minus(end1, start1), coefs.first))
    }

    /**
     * Checks is a point is on a given segment
     * @param start the segment start
     * @param end the segment end
     * @param point the point to be checked if on the segment or not
     * @return true if the point is on the segment, false otherwise
     */
    fun isOnSegment(start: LatLng, end: LatLng, point: LatLng): Boolean {
        val a = minus(point, start)
        val b = minus(end, start)
        //if projection on the segment is (almost) the same, return checks if the point lies inside the boundaries formed by the two points
        return if (euclideanDistance(minus(point, start), project(a, b)) > epsilon*10000) {
            false
        } else {

            ((point.latitude in start.latitude..end.latitude && point.longitude in start.longitude..end.longitude) ||
                    (point.latitude in start.latitude..end.latitude && point.longitude in end.longitude..start.longitude) ||
                    (point.latitude in end.latitude..start.latitude && point.longitude in end.longitude..start.longitude) ||
                    (point.latitude in end.latitude..start.latitude && point.longitude in start.longitude..end.longitude))
        }
    }

    /**
     * Computes the projection of the vector a on the vector b
     * @param a the vector to project
     * @param b the vector on which we want to project
     * @return the projection of a on b
     */
    fun project(a: LatLng, b: LatLng): LatLng {
        return time(b, scalar(a, divide(b, squaredNorm(b))))
    }

    /**
     * Checks if a point lies inside a Rectangle
     * https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle
     * @param point the point
     * @param rectangle the rectangle
     * @return true if the point is inside the rectangle, else false
     */
    fun isInRectangle(point: LatLng, rectangle: List<LatLng>): Boolean {
        val ab = minus(rectangle[1], rectangle[0])
        val ad = minus(rectangle[3], rectangle[0])
        val am = minus(point, rectangle[0])
        return (scalar(am, ab) in -epsilon..squaredNorm(ab) + epsilon &&
                scalar(am, ad) in -epsilon..squaredNorm(ad) + epsilon)
    }

    /**
     * Check if a point is very close to an other one (used to compensate floating point error)
     * @param p1 first point
     * @param p2 second point
     * @return true is the points are very close, else false
     */
    private fun isCloseTo(p1: LatLng, p2: LatLng): Boolean {
        return (euclideanDistance(p1, p2) < epsilon)
    }


    /**
     * Finds the closest polygonal area to the given node
     * @param node the node
     * @param areas the polygonal areas
     * @return The closest polygonal area
     */
    fun closestPolygonArea(node: RouteNode, areas:List<List<LatLng>>): List<LatLng> {
        var closest: List<LatLng>? = null
        var mindist = Double.MAX_VALUE
        for (polygon in areas) {
            for (i in polygon.indices) {
                val nearestPoint = RouteMapHelper.getNearestPoint(
                    RouteNode.fromLatLong(polygon[i]),
                    RouteNode.fromLatLong(polygon[(i + 1) % polygon.size]),
                    node.toLatLng()
                ).toLatLng()
                val dist = squaredEuclideanDistance(node.toLatLng(), nearestPoint)
                if (dist < mindist) {
                    closest = polygon
                    mindist = dist
                }
            }
        }
        return closest!!
    }

    /**
     * Represents a polygon by a linked list of vertices.
     * @param points initial list of points
     */
    class Polygon(points: List<LatLng>) {
        // removes last vertex if it is the same as the first one
        private var vertices: List<Vertex> = points.dropLastWhile { points[0] == it }.map {
            Vertex(
                xy = it,
                next = null,
                prev = null,
                intersect = false,
                entry_exit = null,
                neighbor = null
            )
        }

        init {
            for (idx in vertices.indices) {
                vertices[idx].next = vertices[(idx + 1) % vertices.size]
                vertices[idx].prev = vertices[(idx - 1 + vertices.size) % vertices.size]
            }
        }

        val start = vertices[0]

        /**
         * Iterates over the polygon from start and going to the "next" Vertex at each iteration
         * @param function function to apply at each iteration
         */
        fun foreach(function: (Vertex) -> Unit) {
            var v = start
            do {
                function(v)
                v = v.next!!
            } while (v != start)
        }

        /**
         * Gets the list of LatLng from the polygon
         * @return the list of LatLng points
         */
        fun toLatLongList(): MutableList<LatLng> {
            val list = mutableListOf<LatLng>()
            foreach { list.add(it.xy) }
            return list
        }


        /**
         * Represents a polygon vertex as a linked list element
         * @param xy latitude and longitude coordinates
         * @param next next linked list element
         * @param prev previous linked list element
         * @param intersect true if the point is an intersection point with an other polygon, else false
         * @param entry_exit null if not on an intersection point, true if the intersection is an entry point to the other polygon,
         *      regarding the "next" path of the current polygon, false if the intersection is an exit point from the other polygon.
         * @param neighbor if the point is an intersection, represents the copy of this point on the other polygon
         */
        data class Vertex(
            val xy: LatLng,
            var next: Vertex?,
            var prev: Vertex?,
            var intersect: Boolean,
            var entry_exit: Boolean?,
            var neighbor: Vertex?
        ) {
            override fun toString(): String {
                return xy.toString()
            }
        }
    }

    /**
     * Returns the coefficients between 0.0 and 1.0 representing the distance between the starts and the intersection point
     * @param start1 start of the first segment
     * @param end1 end of the first segment
     * @param start2 start of the second segment
     * @param end2 end of the second segment
     * @return null if no intersection, else returns the pair of ratios
     */
    private fun getIntersectionCoefficients(
        start1: LatLng,
        end1: LatLng,
        start2: LatLng,
        end2: LatLng
    ): Pair<Double, Double>? {
        val denom =
            (((start1.latitude - end1.latitude) * (start2.longitude - end2.longitude)) - ((start1.longitude - end1.longitude) * (start2.latitude - end2.latitude)))

        if (abs(denom) < epsilon) {
            //the lines are parallel
            return null
        }
        val t =
            ((start1.latitude - start2.latitude) * (start2.longitude - end2.longitude) - (start1.longitude - start2.longitude) * (start2.latitude - end2.latitude)) / denom
        val s =
            ((end1.latitude - start1.latitude) * (start1.longitude - start2.longitude) - (end1.longitude - start1.longitude) * (start1.latitude - start2.latitude)) / denom
        if (!(t in 0.0 - epsilon..1.0 + epsilon && s in 0.0 - epsilon..1.0 + epsilon)) {
            //the intersection point is outside the boundaries formed by the extremities of the segments
            return null
        }
        return Pair(t, s)
    }

    /**
     * creates a new intersection vertex between start and stop at a distance alpha (0 < alpha < 1)
     * @param start starting node
     * @param stop ending node
     * @param alpha distance between start and stop
     * @return new intersection vertex
     */
    private fun createIntersectionVertex(start: Vertex, stop: Vertex, alpha: Double) = Vertex(
        xy = plus(start.xy, time(minus(stop.xy, start.xy), alpha)),
        next = null,
        prev = null,
        intersect = true,
        entry_exit = null,
        neighbor = null
    )

    /**
     * Checks if the given point is in the given polygon
     * Draws a line from the point to infinity, if the ray crosses the polygon an even number of times, the point lies inside the polygon
     * @param point the point
     * @param polygon the polygon
     * @return true if the point is in the polygon, else retun false
     */
    fun pointInsidePolygon(point: LatLng, polygon: Polygon): Boolean {
        // https://en.wikipedia.org/wiki/Point_in_polygon#:~:text=One%20simple%20way%20of%20finding,an%20even%20number%20of%20times.
        val maxLat = 90.0 // LatLng does not have a positive infinity for Lat, 90.0 is the max value
        var curVertex = polygon.start
        var nbOfIntersections = 0

        // keep track of the last intersection we crossed, to not count twice when the ray crosses a node
        var lastIntersection: LatLng?
        var currentIntersection: LatLng? = null
        do {
            //if point is on a segment, immediately we consider the point inside the polygon
            if (isOnSegment(curVertex.xy, curVertex.next!!.xy, point)) return true


            lastIntersection = currentIntersection
            currentIntersection = getIntersection(
                curVertex.xy,
                curVertex.next!!.xy,
                point,
                LatLng(
                    maxLat,
                    // trick to prevent vertical lines intersections
                    point.longitude + 0.123456
                )
            )

            if (
                currentIntersection != null &&
                if (lastIntersection != null) {
                    // don't count twice when the ray crosses a node
                    !isCloseTo(lastIntersection, currentIntersection)
                } else {
                    true
                }
            //if intersection add to the count
            ) {
                nbOfIntersections++
            }
            curVertex = curVertex.next!!
        } while (curVertex != polygon.start)
        return nbOfIntersections % 2 == 1

    }


    /**
     * Represents theoretical set operation we can make on polygons
     */
    enum class PolygonOperationType {
        UNION,          // A ∪ B
        INTERSECTION,   // A ∩ B
        DIFFERENCE      // A \ B
    }

    /**
     * Computes the theoretical set union between polygons (just like in Venn diagrams).
     * @param polygons List of polygons, each polygon is represented by a list of its corners (in LatLng)
     * @return a list of disjoint shapes. Each shape is a Pair,
     *      the first element is a single polygon representing the outside border of the shape,
     *      the second element is the list of disjoint holes (polygon) in that shape.
     */
    fun polygonsUnion(polygons: List<List<LatLng>>): MutableList<Pair<MutableList<LatLng>, MutableList<MutableList<LatLng>>?>> {
        //rectangles that have not been merged
        val remainingRectangles = polygons.toMutableList() //deep copy

        val finalShape =
            mutableListOf<Pair<MutableList<LatLng>, MutableList<MutableList<LatLng>>?>>()
        // at each iteration we merge rectangles that overlap together and add them to the finalShape
        while (remainingRectangles.isNotEmpty()) {
            // the external border of the current "rectangle merging" and its eventual holes
            var outerShape = remainingRectangles.removeFirst().toMutableList()
            var holes = mutableListOf<MutableList<LatLng>>()
            // we form a queue to take first the rectangles that have not been looked at before
            // checking with rectangles that are verified outside the zone
            val queuedRectangles = ArrayDeque(remainingRectangles)
            // rectangles that do not intersect with the current rectangle merging
            val notIntersecting = mutableListOf<List<LatLng>>()
            while (queuedRectangles.isNotEmpty()) {
                val rectangle = queuedRectangles.pollFirst()!!
                val unionShape = polygonOperation(
                    Polygon(outerShape),
                    Polygon(rectangle),
                    UNION
                )
                // if union is disjoint, there will be 2 shapes in unionShape
                if (unionShape.size > 1) {
                    notIntersecting.add(rectangle)
                    continue
                }
                // there is an intersection
                while (notIntersecting.isNotEmpty()) {
                    queuedRectangles.addLast(notIntersecting.removeFirst())
                }
                remainingRectangles.remove(rectangle)
                // the new hole is the difference between the old holes and the new added rectangle
                val newHoles = unionShape[0].second ?: mutableListOf()
                for (hole in holes.toMutableList()) {
                    for (newHole in polygonOperation(
                        Polygon(hole),
                        Polygon(rectangle), DIFFERENCE
                    )) {
                        newHoles.add(newHole.first)
                    }
                }
                holes = newHoles
                // the outerShape is the union between the old polygon and the new added rectangle
                outerShape = unionShape[0].first
            }

            if (holes.isEmpty()) {
                finalShape.add(Pair(outerShape, null))
            } else {
                finalShape.add(Pair(outerShape, holes))
            }
        }

        return finalShape
    }


    /**
     * Useful for the polygonOperation algorithm
     */
    private const val entry = true
    private const val exit = false

    /**
     * Computes theoretical set operations between the subject and the clip polygon
     * As the polygons can be non convex, the resulting shape may have holes, this is why we use this return type.
     * Inspired from : https://dl.acm.org/doi/abs/10.1145/274363.274364
     * @param subject "subject" polygon
     * @param clip "clip" polygon
     * @param polygonOperationType
     *      UNION :         subject ∪ clip
     *      INTERSECTION :  subject ∩ clip
     *      DIFFERENCE      subject \ clip
     * @return a list of disjoint shapes. Each shape is a Pair,
     *      the first element is a single polygon representing the outside border of the shape,
     *      the second element is the list of disjoint holes (polygon) in that shape.
     */
    fun polygonOperation(
        subject: Polygon,
        clip: Polygon,
        polygonOperationType: PolygonOperationType
    ): MutableList<Pair<MutableList<LatLng>, MutableList<MutableList<LatLng>>?>> {

        /** Phase 1 : find intersection points between subject and clip, and setup them in double linked lists
         * Each double linked list contains all the points of a polygon.
         * There is a link from one linked list to an other at each intersection point of the polygons so we can jump from one to the other
         */

        var curVertP1 = subject.start
        var curVertP2 = clip.start
        do {
            //we don't want to take into account when a point we used is too close
            if (!(isCloseTo(curVertP1.xy, curVertP2.xy) ||
                        isCloseTo(curVertP1.next!!.xy, curVertP2.xy) ||
                        isCloseTo(curVertP1.xy, curVertP2.next!!.xy) ||
                        isCloseTo(curVertP1.next!!.xy, curVertP2.next!!.xy))

            ) {

                val inter = getIntersectionCoefficients(
                    curVertP1.xy,
                    curVertP1.next!!.xy,
                    curVertP2.xy,
                    curVertP2.next!!.xy
                )
                if (inter != null) {
                    //create a vertex for each list at the intersection point
                    val v1 = createIntersectionVertex(curVertP1, curVertP1.next!!, inter.first)
                    val v2 = createIntersectionVertex(curVertP2, curVertP2.next!!, inter.second)
                    //link v1 and v2
                    v1.neighbor = v2
                    v2.neighbor = v1

                    //place v1 in first linked list, v2 in second linkedlist
                    v1.next = curVertP1.next
                    v1.prev = curVertP1
                    curVertP1.next!!.prev = v1
                    curVertP1.next = v1

                    v2.next = curVertP2.next
                    v2.prev = curVertP2
                    curVertP2.next!!.prev = v2
                    curVertP2.next = v2


                }
            }
            curVertP2 = curVertP2.next!!
            if (curVertP2 == clip.start) {
                curVertP1 = curVertP1.next!!
            }
        } while (curVertP1 != subject.start || curVertP2 != clip.start)

        val shape = checkForTrivialCases(subject, clip, polygonOperationType)
        if (shape != null) return shape

        /** Phase 2 : Set entry and exit points
         * Let's see polygons as directed graph represented by the linked lists in the "next" direction
         * At each intersection, if we enter in the other polygon, we place an "entry" marker,
         *      if we leave the other polygon interior, we place an "exit" marker
         */

        // list that keeps track of intersections on subject polygon, useful for Phase 3
        val subjectIntersections = mutableListOf<Vertex>()


        setEntriesExits(subject, clip, subjectIntersections)
        setEntriesExits(clip, subject, null)

        /** Phase 3 Draw the resulting polygons and holes
         * We start at an intersection point and given the operation.
         * We follow the polygons and switch from one to the other to "draw" the resulting polygon
         * For union, at each intersection, we switch to the other polygon and we must follow the "outside" path
         * For intersection, at each intersection, we switch to the other polygon and we must follow the "inside" path
         * For difference, at each intersection, we switch to the other polygon and
         *      we follow the "outside" path of the subject polygon and "inside" path of the clip polygon
         *
         * The result is a list of disjoint polygons.
         */

        val polygons = mutableListOf<MutableList<LatLng>>()
        while (subjectIntersections.isNotEmpty()) {
            val firstIntersection = subjectIntersections.first()
            val newPolygon = mutableListOf(firstIntersection.xy)
            var current = firstIntersection
            var isOnSubject = true
            do {
                subjectIntersections.removeIf { isCloseTo(it.xy, current.xy) }
                if (when (polygonOperationType) {
                        UNION -> !current.entry_exit!!
                        INTERSECTION -> current.entry_exit!!
                        DIFFERENCE -> current.entry_exit!! != isOnSubject
                    }
                ) {
                    // draw the line over next values until the next intersection
                    do {
                        current = current.next!!
                        newPolygon.add(current.xy)
                    } while (!current.intersect)

                } else {
                    // draw the line over prev values until the next intersection
                    do {
                        current = current.prev!!
                        newPolygon.add(current.xy)
                    } while (!current.intersect)
                }
                // switch to the corresponding vertex on the other polygon
                current = current.neighbor!!
                isOnSubject = !isOnSubject
                // repeat until a polygon is closed
            } while (current != firstIntersection)
            polygons.add(newPolygon)
        }


        /** Phase 4 : Return in correct format
         * We must now return the correct values from our drawing of phase 3
         * If we are in UNION mode, there can only be a single shape with holes at this point
         * If we are in INTERSECTION mode, there can only be disjoint polygons without holes
         * If we are in DIFFERENCE mode, there can only be disjoint polygons without holes
         */


        return when (polygonOperationType) {
            //union of 2 overlapping polygons can only give a single zone with holes inside
            UNION -> mutableListOf(
                separateOutsidePolygonFromHoles(
                    polygons
                )
            )
            //intersection of 2 polygons without holes can only give polygons without holes
            INTERSECTION, DIFFERENCE ->
                polygons.map { Pair(it, null) }.toMutableList()
        }
    }

    /**
     * Check if the resulting zones are one inside an other or disjoint
     * In this case we can return directly the trivial value relative to each operation
     * for example union of disjoint polygons is simply both polygons
     * or intersection of disjoint polygons is empty
     * or subtraction of a zone by an inner zone is the enclosing zone with the inner zone as its hole
     * @param subject subject polygon
     * @param clip clip polygon
     * @param polygonOperationType
     *      UNION :         subject ∪ clip
     *      INTERSECTION :  subject ∩ clip
     *      DIFFERENCE      subject \ clip
     * @return
     *
     */
    private fun checkForTrivialCases(
        subject: Polygon,
        clip: Polygon,
        polygonOperationType: PolygonOperationType
    ): MutableList<Pair<MutableList<LatLng>, MutableList<MutableList<LatLng>>?>>? {
        var existingIntersections = false
        var subjectInClip = true
        var clipInSubject = true
        var subjectAndClipSeparated = true
        subject.foreach {
            existingIntersections = existingIntersections || it.intersect
            if (pointInsidePolygon(it.xy, clip)) subjectAndClipSeparated = false
            else subjectInClip = false
        }
        clip.foreach {
            existingIntersections = existingIntersections || it.intersect
            if (pointInsidePolygon(it.xy, subject)) subjectAndClipSeparated = false
            else clipInSubject = false
        }

        if (subjectInClip && clipInSubject) {
            //polygons are the same
            return when (polygonOperationType) {
                UNION, INTERSECTION -> mutableListOf(
                    Pair(
                        subject.toLatLongList(), null
                    )
                )
                DIFFERENCE -> mutableListOf()
            }
        }

        // check for each operation if the subject is totally included in clip without intersecting edges
        // same with clip in subject and check for disjoint polygons too
        if (!existingIntersections) {
            when (polygonOperationType) {
                UNION -> {
                    if (subjectInClip) return mutableListOf(
                        Pair(
                            clip.toLatLongList(), null
                        )
                    )
                    if (clipInSubject) return mutableListOf(
                        Pair(
                            subject.toLatLongList(), null
                        )
                    )
                    if (subjectAndClipSeparated) return mutableListOf(
                        Pair(subject.toLatLongList(), null),
                        Pair(clip.toLatLongList(), null)
                    )
                }
                INTERSECTION -> {
                    if (subjectInClip) return mutableListOf(
                        Pair(
                            subject.toLatLongList(), null
                        )
                    )
                    if (clipInSubject) return mutableListOf(
                        Pair(
                            clip.toLatLongList(), null
                        )
                    )
                    if (subjectAndClipSeparated) return mutableListOf()
                }
                DIFFERENCE -> {
                    if (subjectInClip) return mutableListOf()
                    if (clipInSubject) return mutableListOf(
                        Pair(
                            subject.toLatLongList(), mutableListOf(clip.toLatLongList())
                        )
                    )
                    if (subjectAndClipSeparated) return mutableListOf(
                        Pair(
                            subject.toLatLongList(), null
                        )
                    )
                }
            }
        }
        return null
    }

    /**
     * Used in phase2 of polygonOperation
     * Sets the entry/exit markers at each intersection of polygon1.
     * We walk on polygon1 and at each intersection with polygon2, we set the entry/exit alternatively
     * Also adds the intersection points to the subjectIntersection list
     * @param polygon1 the subject polygon
     * @param polygon2 the clip polygon
     * @param subjectIntersections the list of intersections
     */
    private fun setEntriesExits(
        polygon1: Polygon,
        polygon2: Polygon,
        subjectIntersections: MutableList<Vertex>?
    ) {
        var status = if (pointInsidePolygon(polygon1.start.xy, polygon2)) {
            exit
        } else {
            entry
        }
        polygon1.foreach {
            if (it.intersect) {
                it.entry_exit = status
                status = !status
                // add all intersections of the first polygon for phase 3
                subjectIntersections?.add(it)

            }
        }
    }

    /**
     * Used only in union mode, to find the enclosing outside polygon and its holes.
     * @param polygons list of polygons from phase 3
     * @return the enclosing shape with its holes
     */
    private fun separateOutsidePolygonFromHoles(polygons: MutableList<MutableList<LatLng>>): Pair<MutableList<LatLng>, MutableList<MutableList<LatLng>>?> {
        if (polygons.size == 1) {
            return Pair(polygons[0], null)
        }
        fun findOutsidePolygon(polygons: MutableList<MutableList<LatLng>>): MutableList<LatLng> {
            var outsidePolygon = polygons[0]
            for (polygon in polygons.drop(1)) {
                if (pointInsidePolygon(outsidePolygon[0], Polygon(polygon))) {
                    outsidePolygon = polygon
                }
            }
            return outsidePolygon
        }

        val outside = findOutsidePolygon(polygons)
        polygons.remove(outside)
        return Pair(outside, polygons)
    }

}