Class Geometry

java.lang.Object
org.openstreetmap.josm.tools.Geometry

public final class Geometry extends Object
Some tools for geometry related tasks.
  • Field Details

  • Constructor Details

  • Method Details

    • addIntersections

      public static Set<Node> addIntersections(List<Way> ways, boolean test, 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

      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

      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

      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

      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:
      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
    • closestPointTo

      private static EastNorth closestPointTo(EastNorth p1, EastNorth p2, EastNorth point, boolean segmentOnly)
    • closestPointToSegment

      public static EastNorth closestPointToSegment(EastNorth segmentP1, EastNorth segmentP2, EastNorth point)
      Calculates closest point to a line segment.
      Parameters:
      segmentP1 - First point determining line segment
      segmentP2 - Second point determining line segment
      point - Point for which a closest point is searched on line segment [P1,P2]
      Returns:
      segmentP1 if it is the closest point, segmentP2 if it is the closest point, a new point if closest point is between segmentP1 and segmentP2.
      Since:
      3650
      See Also:
    • closestPointToLine

      public static EastNorth closestPointToLine(EastNorth lineP1, EastNorth lineP2, EastNorth point)
      Calculates closest point to a line.
      Parameters:
      lineP1 - First point determining line
      lineP2 - Second point determining line
      point - Point for which a closest point is searched on line (P1,P2)
      Returns:
      The closest point found on line. It may be outside the segment [P1,P2].
      Since:
      4134
      See Also:
    • 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 Area getArea(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 Path2D buildPath2DLatLon(List<? extends ILatLon> polygon, 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 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 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(List<? extends INode> first, 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

      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(Area a1, 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

      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(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, 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 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:
      IllegalArgumentException - if way is not closed (see Way.isClosed()).
    • isClockwise

      public static boolean isClockwise(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:
      IllegalArgumentException - if way is not closed (see Way.isClosed()).
      See Also:
    • 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
    • getCentroid

      public static EastNorth getCentroid(List<? extends INode> nodes)
      Compute the centroid/barycenter of nodes
      Parameters:
      nodes - Nodes for which the centroid is wanted
      Returns:
      the centroid of nodes
      See Also:
    • getCentroidEN

      public static EastNorth getCentroidEN(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(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:
    • isNodeInsideMultiPolygon

      public static boolean isNodeInsideMultiPolygon(INode node, Relation multiPolygon, Predicate<Way> isOuterWayAMatch)
      Tests if the node 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).
      Parameters:
      node - node
      multiPolygon - multipolygon
      isOuterWayAMatch - allows to decide if the immediate outer way of the multipolygon is a match
      Returns:
      true if the node is inside the multipolygon
    • isPolygonInsideMultiPolygon

      public static boolean isPolygonInsideMultiPolygon(List<? extends INode> nodes, Relation multiPolygon, 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
    • isPolygonInsideMultiPolygon

      public static boolean isPolygonInsideMultiPolygon(List<? extends INode> nodes, Pair<List<MultipolygonBuilder.JoinedPolygon>,List<MultipolygonBuilder.JoinedPolygon>> outerInner, 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
      outerInner - result of MultipolygonBuilder.joinWays(Relation)
      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
      Since:
      15069
    • filterInsideAnyPolygon

      public static List<IPrimitive> filterInsideAnyPolygon(Collection<IPrimitive> primitives, IPrimitive polygon)
      Find all primitives in the given collection which are inside the given polygon.
      Parameters:
      primitives - the primitives
      polygon - the closed way or multipolygon relation
      Returns:
      a new list containing the found primitives, empty if polygon is invalid or nothing was found.
      Since:
      15730
      See Also:
    • filterInsidePolygon

      public static List<IPrimitive> filterInsidePolygon(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 List<IPrimitive> filterInsideMultipolygon(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

      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(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
    • getAreaAndPerimeter

      public static Geometry.AreaAndPerimeter getAreaAndPerimeter(List<? extends ILatLon> nodes, Projection projection)
      Calculate area and perimeter length of a polygon in the given projection.
      Parameters:
      nodes - the list of nodes representing the polygon
      projection - the projection to use for the calculation, null defaults to ProjectionRegistry.getProjection()
      Returns:
      area and perimeter
      Since:
      13638 (signature)
    • getClosestPrimitive

      public static <T extends OsmPrimitive> T getClosestPrimitive(OsmPrimitive osm, 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> Collection<T> getClosestPrimitives(OsmPrimitive osm, 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, 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> Collection<T> getFurthestPrimitives(OsmPrimitive osm, 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(WaySegment ws1, WaySegment ws2)
      Get the distance between different WaySegments
      Parameters:
      ws1 - A WaySegment
      ws2 - A 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
    • 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