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