Package org.openstreetmap.josm.tools

Class Geometry

  • public final class Geometry
extends java.lang.Object
    Some tools for geometry related tasks.

    • Method Detail

      • addIntersections

        public static java.util.Set<Node> addIntersections​(java.util.List<Way> ways,
                                                   boolean test,
                                                   java.util.List<Command> cmds)
        Will find all intersection and add nodes there for list of given ways. Handles self-intersections too. And makes commands to add the intersection points to ways.

        Prerequisite: no two nodes have the same coordinates.

        Parameters:
        ways - a list of ways to test
        test - if true, do not build list of Commands, just return nodes
        cmds - list of commands, typically empty when handed to this method. Will be filled with commands that add intersection nodes to the ways.
        Returns:
        set of new nodes, if test is true the list might not contain all intersections

      • isToTheRightSideOfLine

        public static <N extends INode> boolean isToTheRightSideOfLine​(N lineP1,
                                                               N lineP2,
                                                               N lineP3,
                                                               N testPoint)
        Tests if given point is to the right side of path consisting of 3 points.

        (Imagine the path is continued beyond the endpoints, so you get two rays starting from lineP2 and going through lineP1 and lineP3 respectively which divide the plane into two parts. The test returns true, if testPoint lies in the part that is to the right when traveling in the direction lineP1, lineP2, lineP3.)

        Type Parameters:
        N - type of node
        Parameters:
        lineP1 - first point in path
        lineP2 - second point in path
        lineP3 - third point in path
        testPoint - point to test
        Returns:
        true if to the right side, false otherwise

      • angleIsClockwise

        public static <N extends INode> boolean angleIsClockwise​(N commonNode,
                                                         N firstNode,
                                                         N secondNode)
        This method tests if secondNode is clockwise to first node.
        Type Parameters:
        N - type of node
        Parameters:
        commonNode - starting point for both vectors
        firstNode - first vector end node
        secondNode - second vector end node
        Returns:
        true if first vector is clockwise before second vector.

      • getSegmentSegmentIntersection

        public static EastNorth getSegmentSegmentIntersection​(EastNorth p1,
                                                      EastNorth p2,
                                                      EastNorth p3,
                                                      EastNorth p4)
        Finds the intersection of two line segments.
        Parameters:
        p1 - the coordinates of the start point of the first specified line segment
        p2 - the coordinates of the end point of the first specified line segment
        p3 - the coordinates of the start point of the second specified line segment
        p4 - the coordinates of the end point of the second specified line segment
        Returns:
        EastNorth null if no intersection was found, the EastNorth coordinates of the intersection otherwise
        See Also:
        getSegmentSegmentIntersection(ILatLon, ILatLon, ILatLon, ILatLon)

      • getSegmentSegmentIntersection

        public static ILatLon getSegmentSegmentIntersection​(ILatLon p1,
                                                    ILatLon p2,
                                                    ILatLon p3,
                                                    ILatLon p4)
        Finds the intersection of two line segments.
        Parameters:
        p1 - the coordinates of the start point of the first specified line segment
        p2 - the coordinates of the end point of the first specified line segment
        p3 - the coordinates of the start point of the second specified line segment
        p4 - the coordinates of the end point of the second specified line segment
        Returns:
        LatLon null if no intersection was found, the LatLon coordinates of the intersection otherwise
        Since:
        18553
        See Also:
        getSegmentSegmentIntersection(EastNorth, EastNorth, EastNorth, EastNorth)

      • getSegmentSegmentIntersection

        private static double[] getSegmentSegmentIntersection​(double x1,
                                                      double y1,
                                                      double x2,
                                                      double y2,
                                                      double x3,
                                                      double y3,
                                                      double x4,
                                                      double y4)
        Get the segment-segment intersection of two line segments
        Parameters:
        x1 - The x coordinate of the first point (first segment)
        y1 - The y coordinate of the first point (first segment)
        x2 - The x coordinate of the second point (first segment)
        y2 - The y coordinate of the second point (first segment)
        x3 - The x coordinate of the third point (second segment)
        y3 - The y coordinate of the third point (second segment)
        x4 - The x coordinate of the fourth point (second segment)
        y4 - The y coordinate of the fourth point (second segment)
        Returns:
        null if no intersection was found, otherwise [x, y]

      • getLineLineIntersection

        public static EastNorth getLineLineIntersection​(EastNorth p1,
                                                EastNorth p2,
                                                EastNorth p3,
                                                EastNorth p4)
        Finds the intersection of two lines of infinite length.
        Parameters:
        p1 - first point on first line
        p2 - second point on first line
        p3 - first point on second line
        p4 - second point on second line
        Returns:
        EastNorth null if no intersection was found, the coordinates of the intersection otherwise
        Throws:
        java.lang.IllegalArgumentException - if a parameter is null or without valid coordinates

      • segmentsParallel

        public static boolean segmentsParallel​(EastNorth p1,
                                       EastNorth p2,
                                       EastNorth p3,
                                       EastNorth p4)
        Check if the segment p1 - p2 is parallel to p3 - p4
        Parameters:
        p1 - First point for first segment
        p2 - Second point for first segment
        p3 - First point for second segment
        p4 - Second point for second segment
        Returns:
        true if they are parallel or close to parallel

      • angleIsClockwise

        public static boolean angleIsClockwise​(EastNorth commonNode,
                                       EastNorth firstNode,
                                       EastNorth secondNode)
        This method tests if secondNode is clockwise to first node.

        The line through the two points commonNode and firstNode divides the plane into two parts. The test returns true, if secondNode lies in the part that is to the right when traveling in the direction from commonNode to firstNode.

        Parameters:
        commonNode - starting point for both vectors
        firstNode - first vector end node
        secondNode - second vector end node
        Returns:
        true if first vector is clockwise before second vector.

      • getArea

        public static java.awt.geom.Area getArea​(java.util.List<? extends INode> polygon)
        Returns the Area of a polygon, from its list of nodes.
        Parameters:
        polygon - List of nodes forming polygon
        Returns:
        Area for the given list of nodes (EastNorth coordinates)
        Since:
        6841

      • buildPath2DLatLon

        public static java.awt.geom.Path2D buildPath2DLatLon​(java.util.List<? extends ILatLon> polygon,
                                                     java.awt.geom.Path2D path2d)
        Builds a path from a list of nodes
        Parameters:
        polygon - Nodes, forming a closed polygon
        path2d - path to add to; can be null, then a new path is created
        Returns:
        the path (LatLon coordinates)
        Since:
        13638 (signature)

      • getAreaEastNorth

        public static java.awt.geom.Area getAreaEastNorth​(IPrimitive p)
        Calculate area in east/north space for given primitive. Uses MultipolygonCache for multipolygon relations.
        Parameters:
        p - the primitive
        Returns:
        the area in east/north space, might be empty if the primitive is incomplete or not closed or a node since 15938

      • getAreaLatLon

        public static java.awt.geom.Area getAreaLatLon​(Relation multipolygon)
        Returns the Area of a polygon, from the multipolygon relation.
        Parameters:
        multipolygon - the multipolygon relation
        Returns:
        Area for the multipolygon (LatLon coordinates)

      • polygonIntersection

        public static Geometry.PolygonIntersection polygonIntersection​(java.util.List<? extends INode> first,
                                                               java.util.List<? extends INode> second)
        Tests if two polygons intersect.
        Parameters:
        first - List of nodes forming first polygon
        second - List of nodes forming second polygon
        Returns:
        intersection kind

      • polygonIntersection

        public static Geometry.PolygonIntersection polygonIntersection​(java.awt.geom.Area a1,
                                                               java.awt.geom.Area a2)
        Tests if two polygons intersect. It is assumed that the area is given in East North points.
        Parameters:
        a1 - Area of first polygon
        a2 - Area of second polygon
        Returns:
        intersection kind
        Since:
        6841

      • polygonIntersection

        public static Geometry.PolygonIntersection polygonIntersection​(java.awt.geom.Area a1,
                                                               java.awt.geom.Area a2,
                                                               double eps)
        Tests if two polygons intersect.
        Parameters:
        a1 - Area of first polygon
        a2 - Area of second polygon
        eps - an area threshold, everything below is considered an empty intersection
        Returns:
        intersection kind

      • polygonIntersectionResult

        public static Pair<Geometry.PolygonIntersection,​java.awt.geom.Area> polygonIntersectionResult​(java.awt.geom.Area a1,
                                                                                                    java.awt.geom.Area a2,
                                                                                                    double eps)
        Calculate intersection area and kind of intersection between two polygons.
        Parameters:
        a1 - Area of first polygon
        a2 - Area of second polygon
        eps - an area threshold, everything below is considered an empty intersection
        Returns:
        pair with intersection kind and intersection area (never null, but maybe empty)
        Since:
        15938

      • checkIntersection

        private static boolean checkIntersection​(java.awt.geom.Area inter,
                                         double eps)
        Check an intersection area which might describe multiple small polygons. Return true if any of the polygons is bigger than the given threshold.
        Parameters:
        inter - the intersection area
        eps - an area threshold, everything below is considered an empty intersection
        Returns:
        true if any of the polygons is bigger than the given threshold

      • nodeInsidePolygon

        public static boolean nodeInsidePolygon​(INode point,
                                        java.util.List<? extends INode> polygonNodes)
        Tests if point is inside a polygon. The polygon can be self-intersecting. In such case the contains function works in xor-like manner.
        Parameters:
        polygonNodes - list of nodes from polygon path.
        point - the point to test
        Returns:
        true if the point is inside polygon.

      • closedWayArea

        public static double closedWayArea​(Way way)
        Returns area of a closed way in square meters.
        Parameters:
        way - Way to measure, should be closed (first node is the same as last node)
        Returns:
        area of the closed way.

      • multipolygonArea

        public static double multipolygonArea​(Relation multipolygon)
        Returns area of a multipolygon in square meters.
        Parameters:
        multipolygon - the multipolygon to measure
        Returns:
        area of the multipolygon.

      • computeArea

        public static java.lang.Double computeArea​(IPrimitive osm)
        Computes the area of a closed way and multipolygon in square meters, or null for other primitives
        Parameters:
        osm - the primitive to measure
        Returns:
        area of the primitive, or null
        Since:
        13638 (signature)

      • isClockwise

        public static boolean isClockwise​(Way w)
        Determines whether a way is oriented clockwise.

        Internals: Assuming a closed non-looping way, compute twice the area of the polygon using the formula 2 * area = sum (X[n] * Y[n+1] - X[n+1] * Y[n]). If the area is negative the way is ordered in a clockwise direction.

        See https://paulbourke.net/geometry/polyarea/

        Parameters:
        w - the way to be checked.
        Returns:
        true if and only if way is oriented clockwise.
        Throws:
        java.lang.IllegalArgumentException - if way is not closed (see Way.isClosed()).

      • isClockwise

        public static boolean isClockwise​(java.util.List<? extends INode> nodes)
        Determines whether path from nodes list is oriented clockwise.
        Parameters:
        nodes - Nodes list to be checked.
        Returns:
        true if and only if way is oriented clockwise.
        Throws:
        java.lang.IllegalArgumentException - if way is not closed (see Way.isClosed()).
        See Also:
        isClockwise(Way)

      • getSegmentAngle

        public static double getSegmentAngle​(EastNorth p1,
                                     EastNorth p2)
        Returns angle of a segment defined with 2 point coordinates.
        Parameters:
        p1 - first point
        p2 - second point
        Returns:
        Angle in radians (-pi, pi]

      • getCornerAngle

        public static double getCornerAngle​(EastNorth p1,
                                    EastNorth common,
                                    EastNorth p3)
        Returns angle of a corner defined with 3 point coordinates.
        Parameters:
        p1 - first point
        common - Common end point
        p3 - third point
        Returns:
        Angle in radians (-pi, pi]

      • getNormalizedAngleInDegrees

        public static double getNormalizedAngleInDegrees​(double angle)
        Get angles in radians and return its value in range [0, 180].
        Parameters:
        angle - the angle in radians
        Returns:
        normalized angle in degrees
        Since:
        13670

      • getCentroidEN

        public static EastNorth getCentroidEN​(java.util.List<EastNorth> nodes)
        Compute the centroid/barycenter of nodes
        Parameters:
        nodes - Coordinates for which the centroid is wanted
        Returns:
        the centroid of nodes
        Since:
        13712

      • getCenter

        public static EastNorth getCenter​(java.util.List<? extends INode> nodes)
        Compute the center of the circle closest to different nodes.

        Ensure exact center computation in case nodes are already aligned in circle. This is done by least square method. Let be a_i x + b_i y + c_i = 0 equations of bisectors of each edges. Center must be intersection of all bisectors. 

                  [ a1  b1  ]         [ -c1 ]
 With A = [ ... ... ] and Y = [ ... ]
          [ an  bn  ]         [ -cn ]
        An approximation of center of circle is (At.A)^-1.At.Y
        Parameters:
        nodes - Nodes parts of the circle (at least 3)
        Returns:
        An approximation of the center, of null if there is no solution.
        Since:
        6934
        See Also:
        getCentroid(java.util.List<? extends org.openstreetmap.josm.data.osm.INode>)

      • isPolygonInsideMultiPolygon

        public static boolean isPolygonInsideMultiPolygon​(java.util.List<? extends INode> nodes,
                                                  Relation multiPolygon,
                                                  java.util.function.Predicate<Way> isOuterWayAMatch)
        Tests if the polygon formed by nodes is inside the multipolygon multiPolygon. The nullable argument isOuterWayAMatch allows to decide if the immediate outer way of the multipolygon is a match. For repeated tests against multiPolygon better use filterInsideMultipolygon(java.util.Collection<org.openstreetmap.josm.data.osm.IPrimitive>, org.openstreetmap.josm.data.osm.Relation).

        If nodes contains exactly one element, then it is checked whether that one node is inside the multipolygon.

        Parameters:
        nodes - nodes forming the polygon
        multiPolygon - multipolygon
        isOuterWayAMatch - allows to decide if the immediate outer way of the multipolygon is a match
        Returns:
        true if the multipolygon is valid and the polygon formed by nodes is inside the multipolygon

      • filterInsidePolygon

        public static java.util.List<IPrimitive> filterInsidePolygon​(java.util.Collection<IPrimitive> primitives,
                                                             IWay<?> polygon)
        Find all primitives in the given collection which are inside the given polygon. Unclosed ways and multipolygon relations with unclosed outer rings are ignored.
        Parameters:
        primitives - the primitives
        polygon - the polygon
        Returns:
        a new list containing the found primitives, empty if polygon is invalid or nothing was found.
        Since:
        15069 (for List of primitives, 15730 for a Collection of primitives)

      • filterInsideMultipolygon

        public static java.util.List<IPrimitive> filterInsideMultipolygon​(java.util.Collection<IPrimitive> primitives,
                                                                  Relation multiPolygon)
        Find all primitives in the given collection which are inside the given multipolygon. Members of the multipolygon are ignored. Unclosed ways and multipolygon relations with unclosed outer rings are ignored.
        Parameters:
        primitives - the primitives
        multiPolygon - the multipolygon relation
        Returns:
        a new list containing the found primitives, empty if multipolygon is invalid or nothing was found.
        Since:
        15069

      • filterInsideMultipolygon

        public static java.util.List<IPrimitive> filterInsideMultipolygon​(java.util.Collection<IPrimitive> primitives,
                                                                  Relation multiPolygon,
                                                                  java.util.Map<IRelation<?>,​Pair<java.util.List<MultipolygonBuilder.JoinedPolygon>,​java.util.List<MultipolygonBuilder.JoinedPolygon>>> cache)
        Find all primitives in the given collection which are inside the given multipolygon. Members of the multipolygon are ignored. Unclosed ways and multipolygon relations with unclosed outer rings are ignored.
        Parameters:
        primitives - the primitives
        multiPolygon - the multipolygon relation
        cache - The cache to avoid calculating joined inner/outer ways multiple times (see MultipolygonBuilder.joinWays(Relation))
        Returns:
        a new list containing the found primitives, empty if multipolygon is invalid or nothing was found.
        Since:
        19336

      • getAreaAndPerimeter

        public static Geometry.AreaAndPerimeter getAreaAndPerimeter​(java.util.List<? extends ILatLon> nodes)
        Calculate area and perimeter length of a polygon.

        Uses current projection; units are that of the projected coordinates.

        Parameters:
        nodes - the list of nodes representing the polygon
        Returns:
        area and perimeter

      • getClosestPrimitive

        public static <T extends OsmPrimitive> T getClosestPrimitive​(OsmPrimitive osm,
                                                             java.util.Collection<T> primitives)
        Get the closest primitive to osm from the collection of OsmPrimitive primitives

        The primitives should be fully downloaded to ensure accuracy.

        Note: The complexity of this method is O(n*m), where n is the number of children osm has plus 1, m is the number of children the collection of primitives have plus the number of primitives in the collection.

        Type Parameters:
        T - The return type of the primitive
        Parameters:
        osm - The primitive to get the distances from
        primitives - The collection of primitives to get the distance to
        Returns:
        The closest OsmPrimitive. This is not determinative. To get all primitives that share the same distance, use getClosestPrimitives(org.openstreetmap.josm.data.osm.OsmPrimitive, java.util.Collection<T>).
        Since:
        15035

      • getClosestPrimitives

        public static <T extends OsmPrimitive> java.util.Collection<T> getClosestPrimitives​(OsmPrimitive osm,
                                                                                    java.util.Collection<T> primitives)
        Get the closest primitives to osm from the collection of OsmPrimitive primitives

        The primitives should be fully downloaded to ensure accuracy.

        Note: The complexity of this method is O(n*m), where n is the number of children osm has plus 1, m is the number of children the collection of primitives have plus the number of primitives in the collection.

        Type Parameters:
        T - The return type of the primitive
        Parameters:
        osm - The primitive to get the distances from
        primitives - The collection of primitives to get the distance to
        Returns:
        The closest OsmPrimitives. May be empty.
        Since:
        15035

      • getFurthestPrimitive

        public static <T extends OsmPrimitive> T getFurthestPrimitive​(OsmPrimitive osm,
                                                              java.util.Collection<T> primitives)
        Get the furthest primitive to osm from the collection of OsmPrimitive primitives

        The primitives should be fully downloaded to ensure accuracy.

        It does NOT give the furthest primitive based off of the furthest part of that primitive

        Note: The complexity of this method is O(n*m), where n is the number of children osm has plus 1, m is the number of children the collection of primitives have plus the number of primitives in the collection.

        Type Parameters:
        T - The return type of the primitive
        Parameters:
        osm - The primitive to get the distances from
        primitives - The collection of primitives to get the distance to
        Returns:
        The furthest OsmPrimitive. This is not determinative. To get all primitives that share the same distance, use getFurthestPrimitives(org.openstreetmap.josm.data.osm.OsmPrimitive, java.util.Collection<T>)
        Since:
        15035

      • getFurthestPrimitives

        public static <T extends OsmPrimitive> java.util.Collection<T> getFurthestPrimitives​(OsmPrimitive osm,
                                                                                     java.util.Collection<T> primitives)
        Get the furthest primitives to osm from the collection of OsmPrimitive primitives

        The primitives should be fully downloaded to ensure accuracy.

        It does NOT give the furthest primitive based off of the furthest part of that primitive

        Note: The complexity of this method is O(n*m), where n is the number of children osm has plus 1, m is the number of children the collection of primitives have plus the number of primitives in the collection.

        Type Parameters:
        T - The return type of the primitive
        Parameters:
        osm - The primitive to get the distances from
        primitives - The collection of primitives to get the distance to
        Returns:
        The furthest OsmPrimitives. It may return an empty collection.
        Since:
        15035

      • getDistance

        public static double getDistance​(OsmPrimitive one,
                                 OsmPrimitive two)
        Get the distance between different OsmPrimitives
        Parameters:
        one - The primitive to get the distance from
        two - The primitive to get the distance to
        Returns:
        The distance between the primitives in meters (or the unit of the current projection, see Projection). May return Double.NaN if one of the primitives is incomplete.

        Note: The complexity is O(n*m), where (n,m) are the number of child objects the OsmPrimitives have.

        Since:
        15035

      • getDistanceWayNode

        public static double getDistanceWayNode​(Way way,
                                        Node node)
        Get the distance between a way and a node
        Parameters:
        way - The way to get the distance from
        node - The node to get the distance to
        Returns:
        The distance between the way and the node in meters (or the unit of the current projection, see Projection). May return Double.NaN if the primitives are incomplete.
        Since:
        15035

      • getClosestWaySegment

        public static WaySegment getClosestWaySegment​(Way way,
                                              OsmPrimitive primitive)
        Get the closest WaySegment from a way to a primitive.
        Parameters:
        way - The Way to get the distance from and the WaySegment
        primitive - The OsmPrimitive to get the distance to
        Returns:
        The WaySegment that is closest to primitive from way. If there are multiple WaySegments with the same distance, the last WaySegment with the same distance will be returned. May return null if the way has fewer than two nodes or one of the primitives is incomplete.
        Since:
        15035

      • getDistanceWayWay

        public static double getDistanceWayWay​(Way w1,
                                       Way w2)
        Get the distance between different ways. Iterates over the nodes of the ways, complexity is O(n*m) (n,m giving the number of nodes)
        Parameters:
        w1 - The first Way
        w2 - The second Way
        Returns:
        The shortest distance between the ways in meters (or the unit of the current projection, see Projection). May return Double.NaN.
        Since:
        15035

      • getDistanceSegmentSegment

        public static double getDistanceSegmentSegment​(Node ws1Node1,
                                               Node ws1Node2,
                                               Node ws2Node1,
                                               Node ws2Node2)
        Get the distance between different WaySegments
        Parameters:
        ws1Node1 - The first node of the first WaySegment
        ws1Node2 - The second node of the second WaySegment
        ws2Node1 - The first node of the second WaySegment
        ws2Node2 - The second node of the second WaySegment
        Returns:
        The distance between the two WaySegments in meters (or the unit of the current projection, see Projection). May return Double.NaN.
        Since:
        15035

      • getLatLonFrom

        public static ILatLon getLatLonFrom​(ILatLon original,
                                    double angle,
                                    double offset)
        Create a new LatLon at a specified distance. Currently uses WGS84, but may change randomly in the future. This does not currently attempt to be hugely accurate. The actual location may be off depending upon the distance and the elevation, but should be within 0.0002 meters.
        Parameters:
        original - The originating point
        angle - The angle (from true north) in radians
        offset - The distance to the new point in the current projection's units
        Returns:
        The location at the specified angle and distance from the originating point
        Since:
        18109

      • getSegmentNodeDistSq

        private static double getSegmentNodeDistSq​(EastNorth s1,
                                           EastNorth s2,
                                           EastNorth p)
        Calculate closest distance between a line segment s1-s2 and a point p
        Parameters:
        s1 - start of segment
        s2 - end of segment
        p - the point
        Returns:
        the square of the euclidean distance from p to the closest point on the segment