1 /* 2 * Copyright (c) 2019 Martin Davis. 3 * 4 * All rights reserved. This program and the accompanying materials 5 * are made available under the terms of the Eclipse Public License 2.0 6 * and Eclipse Distribution License v. 1.0 which accompanies this distribution. 7 * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html 8 * and the Eclipse Distribution License is available at 9 * 10 * http://www.eclipse.org/org/documents/edl-v10.php. 11 */ 12 package org.locationtech.jts.operation.overlayng; 13 14 import java.util.ArrayList; 15 import java.util.HashMap; 16 import java.util.Map; 17 import java.util.Map.Entry; 18 19 import org.locationtech.jts.geom.Coordinate; 20 import org.locationtech.jts.geom.CoordinateSequence; 21 import org.locationtech.jts.geom.Geometry; 22 import org.locationtech.jts.geom.GeometryFactory; 23 import org.locationtech.jts.geom.Point; 24 import org.locationtech.jts.geom.PrecisionModel; 25 26 /** 27 * Performs an overlay operation on inputs which are both point geometries. 28 * <p> 29 * Semantics are: 30 * <ul> 31 * <li>Points are rounded to the precision model if provided 32 * <li>Points with identical XY values are merged to a single point 33 * <li>Extended ordinate values are preserved in the output, 34 * apart from merging 35 * <li>An empty result is returned as <code>POINT EMPTY</code> 36 * </ul> 37 * 38 * @author Martin Davis 39 * 40 */ 41 class OverlayPoints { 42 43 /** 44 * Performs an overlay operation on inputs which are both point geometries. 45 * 46 * @param geom0 the first geometry argument 47 * @param geom1 the second geometry argument 48 * @param opCode the code for the desired overlay operation 49 * @param pm the precision model to use 50 * @return the result of the overlay operation 51 */ overlay(int opCode, Geometry geom0, Geometry geom1, PrecisionModel pm)52 public static Geometry overlay(int opCode, Geometry geom0, Geometry geom1, PrecisionModel pm) { 53 OverlayPoints overlay = new OverlayPoints(opCode, geom0, geom1, pm); 54 return overlay.getResult(); 55 } 56 57 private int opCode; 58 private Geometry geom0; 59 private Geometry geom1; 60 private PrecisionModel pm; 61 private GeometryFactory geometryFactory; 62 private ArrayList<Point> resultList; 63 64 /** 65 * Creates an instance of an overlay operation on inputs which are both point geometries. 66 * 67 * @param geom0 the first geometry argument 68 * @param geom1 the second geometry argument 69 * @param opCode the code for the desired overlay operation 70 * @param pm the precision model to use 71 */ OverlayPoints(int opCode, Geometry geom0, Geometry geom1, PrecisionModel pm)72 public OverlayPoints(int opCode, Geometry geom0, Geometry geom1, PrecisionModel pm) { 73 this.opCode = opCode; 74 this.geom0 = geom0; 75 this.geom1 = geom1; 76 this.pm = pm; 77 geometryFactory = geom0.getFactory(); 78 } 79 80 /** 81 * Gets the result of the overlay. 82 * 83 * @return the overlay result 84 */ getResult()85 public Geometry getResult() { 86 Map<Coordinate, Point> map0 = buildPointMap(geom0); 87 Map<Coordinate, Point> map1 = buildPointMap(geom1); 88 89 resultList = new ArrayList<Point>(); 90 switch (opCode) { 91 case OverlayNG.INTERSECTION: 92 computeIntersection(map0, map1, resultList); 93 break; 94 case OverlayNG.UNION: 95 computeUnion(map0, map1, resultList); 96 break; 97 case OverlayNG.DIFFERENCE: 98 computeDifference(map0, map1, resultList); 99 break; 100 case OverlayNG.SYMDIFFERENCE: 101 computeDifference(map0, map1, resultList); 102 computeDifference(map1, map0, resultList); 103 break; 104 } 105 if (resultList.isEmpty()) 106 return OverlayUtil.createEmptyResult(0, geometryFactory); 107 108 return geometryFactory.buildGeometry(resultList); 109 } 110 computeIntersection(Map<Coordinate, Point> map0, Map<Coordinate, Point> map1, ArrayList<Point> resultList)111 private void computeIntersection(Map<Coordinate, Point> map0, Map<Coordinate, Point> map1, 112 ArrayList<Point> resultList) { 113 for ( Entry<Coordinate, Point> entry : map0.entrySet()) { 114 if (map1.containsKey(entry.getKey())) { 115 resultList.add( copyPoint( entry.getValue() ) ); 116 } 117 } 118 } 119 computeDifference(Map<Coordinate, Point> map0, Map<Coordinate, Point> map1, ArrayList<Point> resultList)120 private void computeDifference(Map<Coordinate, Point> map0, Map<Coordinate, Point> map1, 121 ArrayList<Point> resultList) { 122 for ( Entry<Coordinate, Point> entry : map0.entrySet()) { 123 if (! map1.containsKey(entry.getKey())) { 124 resultList.add( copyPoint( entry.getValue() ) ); 125 } 126 } 127 } 128 computeUnion(Map<Coordinate, Point> map0, Map<Coordinate, Point> map1, ArrayList<Point> resultList)129 private void computeUnion(Map<Coordinate, Point> map0, Map<Coordinate, Point> map1, 130 ArrayList<Point> resultList) { 131 132 // copy all A points 133 for (Point p : map0.values()) { 134 resultList.add( copyPoint( p ) ); 135 } 136 137 for ( Entry<Coordinate, Point> entry : map1.entrySet()) { 138 if (! map0.containsKey(entry.getKey())) { 139 resultList.add( copyPoint( entry.getValue() ) ); 140 } 141 } 142 } 143 copyPoint(Point pt)144 private Point copyPoint(Point pt) { 145 // if pm is floating, the point coordinate is not changed 146 if (OverlayUtil.isFloating(pm)) 147 return (Point) pt.copy(); 148 149 // pm is fixed. Round off X&Y ordinates, copy other ordinates unchanged 150 CoordinateSequence seq = pt.getCoordinateSequence(); 151 CoordinateSequence seq2 = seq.copy(); 152 seq2.setOrdinate(0, CoordinateSequence.X, pm.makePrecise(seq.getX(0))); 153 seq2.setOrdinate(0, CoordinateSequence.Y, pm.makePrecise(seq.getY(0))); 154 return geometryFactory.createPoint(seq2); 155 } 156 buildPointMap(Geometry geom)157 private HashMap<Coordinate, Point> buildPointMap(Geometry geom) { 158 HashMap<Coordinate, Point> map = new HashMap<Coordinate, Point>(); 159 for (int i = 0; i < geom.getNumGeometries(); i++) { 160 Geometry elt = geom.getGeometryN(i); 161 if (! (elt instanceof Point) ) { 162 throw new IllegalArgumentException("Non-point geometry input to point overlay"); 163 } 164 // don't add empty points 165 if (elt.isEmpty()) continue; 166 167 Point pt = (Point) elt; 168 Coordinate p = roundCoord(pt, pm); 169 /** 170 * Only add first occurrence of a point. 171 * This provides the merging semantics of overlay 172 */ 173 if (! map.containsKey(p)) 174 map.put(p, pt); 175 } 176 return map; 177 } 178 179 /** 180 * Round the key point if precision model is fixed. 181 * Note: return value is only copied if rounding is performed. 182 * 183 * @param pt 184 * @return 185 */ roundCoord(Point pt, PrecisionModel pm)186 static Coordinate roundCoord(Point pt, PrecisionModel pm) { 187 Coordinate p = pt.getCoordinate(); 188 if (OverlayUtil.isFloating(pm)) 189 return p; 190 Coordinate p2 = p.copy(); 191 pm.makePrecise(p2); 192 return p2; 193 } 194 195 } 196