PartitionedUnion.java

/*
 * Copyright (c) 2021 Martin Davis.
 *
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
 * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
 * and the Eclipse Distribution License is available at
 *
 * http://www.eclipse.org/org/documents/edl-v10.php.
 */
package org.locationtech.jts.operation.union;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.prep.PreparedGeometry;
import org.locationtech.jts.geom.prep.PreparedGeometryFactory;
import org.locationtech.jts.geom.util.PolygonExtracter;

/**
 * Unions a set of polygonal geometries by partitioning them
 * into connected sets of polygons.
 * This works best for a <i>sparse</i> set of polygons.
 * Sparse means that if the geometries are partioned
 * into connected sets, the number of sets
 * is a significant fraction of the total number of geometries.
 * The algorithm used provides performance and memory advantages
 * over the {@link CascadedPolygonUnion} algorithm.
 * It also has the advantage that it does not alter input geometries
 * which do not intersect any other input geometry.
 * <p>
 * Non-sparse sets are computed correctly, but may be slower than using cascaded union.
 * 
 * @author Martin Davis
 *
 */
public class PartitionedUnion {
  
  public static Geometry union(Geometry geoms)
  {
    List polys = PolygonExtracter.getPolygons(geoms);
    PartitionedUnion op = new PartitionedUnion(polys);
    return op.union();
  }

  private Geometry[] inputPolys;
  
  public PartitionedUnion(Collection<Geometry> polys)
  {
    this.inputPolys = toArray(polys);
  }
  
  private static Geometry[] toArray(Collection<Geometry> polys) {
    return polys.toArray(new Geometry[0]);
  }
  
  public Geometry union()
  {
    if (inputPolys.length == 0)
      return null;
    
    SpatialPartition part = new SpatialPartition(inputPolys, new SpatialPartition.EquivalenceRelation() {
      
      @Override
      public boolean isEquivalent(int i, int j) {
         //return inputPolys[i].intersects(inputPolys[j]);
        //*
         PreparedGeometry pg = PreparedGeometryFactory.prepare(inputPolys[i]);
         return pg.intersects(inputPolys[j]);
         //*/
      }
    });
    
    //--- compute union of each set
    GeometryFactory geomFactory = inputPolys[0].getFactory();
    List<Geometry> unionGeoms = new ArrayList<Geometry>();
    int numSets = part.getCount();
    for (int i = 0; i < numSets; i++) {
      Geometry geom = union(part, i);
      unionGeoms.add(geom);
    }
    return geomFactory.buildGeometry(unionGeoms);
  }

  private Geometry union(SpatialPartition part, int s) {
    //--- one geom in partition, so just copy it
    if (part.getSize(s) == 1) {
      return part.getGeometry(s, 0).copy();
    }

    List<Geometry> setGeoms = new ArrayList<Geometry>();
    for (int i = 0; i < part.getSize(s); i++) {
      setGeoms.add( part.getGeometry(s, i) );
    }
    return CascadedPolygonUnion.union(setGeoms);
  }
}