InteriorDisconnectedCheck.java

/*-
 *  Copyright 2020 Beuth Hochschule für Technik Berlin, Hochschule für Technik Stuttgart
 * 
 *  This file is part of CityDoctor2.
 *
 *  CityDoctor2 is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  CityDoctor2 is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with CityDoctor2.  If not, see <https://www.gnu.org/licenses/>.
 */
package de.hft.stuttgart.citydoctor2.checks.geometry;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import de.hft.stuttgart.citydoctor2.check.Check;
import de.hft.stuttgart.citydoctor2.check.CheckError;
import de.hft.stuttgart.citydoctor2.check.CheckId;
import de.hft.stuttgart.citydoctor2.check.CheckResult;
import de.hft.stuttgart.citydoctor2.check.CheckType;
import de.hft.stuttgart.citydoctor2.check.Checkable;
import de.hft.stuttgart.citydoctor2.check.DefaultParameter;
import de.hft.stuttgart.citydoctor2.check.ResultStatus;
import de.hft.stuttgart.citydoctor2.check.Unit;
import de.hft.stuttgart.citydoctor2.check.error.PolygonInteriorDisconnectedError;
import de.hft.stuttgart.citydoctor2.datastructure.LinearRing;
import de.hft.stuttgart.citydoctor2.datastructure.Polygon;
import de.hft.stuttgart.citydoctor2.datastructure.Vertex;
import de.hft.stuttgart.citydoctor2.math.Segment3d;
import de.hft.stuttgart.citydoctor2.math.graph.CycleNode;
import de.hft.stuttgart.citydoctor2.parser.ParserConfiguration;

public class InteriorDisconnectedCheck extends Check {
	
	private static final String EPSILON_NAME = "Epsilon";
	
	private static final List<CheckId> dependencies;
	private static final List<Class<? extends Checkable>> applicableToClasses;
	private static final List<DefaultParameter> defaultParameters;
	
	static {
		ArrayList<CheckId> deps = new ArrayList<>();
		deps.add(CheckId.C_GE_R_TOO_FEW_POINTS);
		deps.add(CheckId.C_GE_R_NOT_CLOSED);
		deps.add(CheckId.C_GE_R_DUPLICATE_POINT);
		deps.add(CheckId.C_GE_P_INTERSECTING_RINGS);
		deps.add(CheckId.C_GE_P_NON_PLANAR);
		dependencies = Collections.unmodifiableList(deps);

		ArrayList<Class<? extends Checkable>> classes = new ArrayList<>();
		classes.add(Polygon.class);
		applicableToClasses = Collections.unmodifiableList(classes);
		
		ArrayList<DefaultParameter> defaultParameter = new ArrayList<>();
		defaultParameter.add(new DefaultParameter(EPSILON_NAME, "0.0001", Unit.METER));
		defaultParameters = Collections.unmodifiableList(defaultParameter);
	}
	
	private double epsilon = 0.0001;
	
	@Override
	public void init(Map<String, String> params, ParserConfiguration config) {
		String epsilonString = params.get(EPSILON_NAME);
		if (epsilonString == null) {
			epsilon = 0.0001;
		} else {
			epsilon = Double.parseDouble(epsilonString);
		}
	}
	
	public InteriorDisconnectedCheck() {
		super(CheckId.C_GE_P_INTERIOR_DISCONNECTED);
	}
	
	@Override
	public void check(Polygon p) {
		if (p.getInnerRings().isEmpty()) {
			// no interior rings means polygon is ok
			CheckResult cr = new CheckResult(this, ResultStatus.OK, null);
			p.addCheckResult(cr);
		}
		Map<LinearRing, CycleNode> nodeMap = new HashMap<>();
		setupNodeMap(p, nodeMap);
		List<LinearRing> rings = new ArrayList<>();
		rings.add(p.getExteriorRing());
		rings.addAll(p.getInnerRings());
		for (int i = 0; i < rings.size() - 1; i++) {
			LinearRing ring = rings.get(i);
			List<Segment3d> segments = createSegmentsFromRing(ring);
			for (int j = i + 1; j < rings.size(); j++) {
				LinearRing borderingRing = rings.get(j);
				if (isRingTouchingBorderingRing(p, nodeMap, ring, segments, borderingRing)) {
					return;
				}
			}
		}
		
		for (CycleNode node : nodeMap.values()) {
			if (node.hasMoreThan2CycleDepth(null)) {
				// found ring in graph with more than 1 node
				// collect rings
				node.resetVisit();
				List<LinearRing> connectedRings = node.getConnectedRings();
				CheckError err = new PolygonInteriorDisconnectedError(p, connectedRings);
				CheckResult cr = new CheckResult(this, ResultStatus.ERROR, err);
				p.addCheckResult(cr);
				return;
			}
			// check next node, reset visit status
			node.resetVisit();
		}

		CheckResult cr = new CheckResult(this, ResultStatus.OK, null);
		p.addCheckResult(cr);
	}

	private boolean isRingTouchingBorderingRing(Polygon p, Map<LinearRing, CycleNode> nodeMap, LinearRing ring,
			List<Segment3d> segments, LinearRing borderingRing) {
		for (Segment3d seg : segments) {
			for (int k = 0; k < borderingRing.getVertices().size() - 1; k++) {
				Vertex v = borderingRing.getVertices().get(k);
				if (seg.getDistance(v) < epsilon) {
					CycleNode n1 = nodeMap.get(ring);
					CycleNode n2 = nodeMap.get(borderingRing);
					boolean added1 = n1.addChild(n2);
					boolean added2 = n2.addChild(n1);
					if (!added1 || !added2) {
						List<LinearRing> connectedRings = new ArrayList<>();
						connectedRings.add(n1.getValue());
						connectedRings.add(n2.getValue());
						CheckError err = new PolygonInteriorDisconnectedError(p, connectedRings);
						CheckResult cr = new CheckResult(this, ResultStatus.ERROR, err);
						p.addCheckResult(cr);
						return true;
					}
					
				}
			}
		}
		return false;
	}

	private List<Segment3d> createSegmentsFromRing(LinearRing ring) {
		List<Segment3d> segments = new ArrayList<>();
		for (int k = 0; k < ring.getVertices().size() - 1; k++) {
			Vertex v1 = ring.getVertices().get(k);
			Vertex v2 = ring.getVertices().get(k + 1);
			segments.add(new Segment3d(v1, v2));
		}
		return segments;
	}

	private void setupNodeMap(Polygon p, Map<LinearRing, CycleNode> nodeMap) {
		CycleNode ext = new CycleNode(p.getExteriorRing());
		nodeMap.put(ext.getValue(), ext);
		for (LinearRing lr : p.getInnerRings()) {
			CycleNode node = new CycleNode(lr);
			nodeMap.put(lr, node);
		}
	}
	
	@Override
	public List<DefaultParameter> getDefaultParameter() {
		return defaultParameters;
	}

	@Override
	public List<Class<? extends Checkable>> getApplicableToClasses() {
		return applicableToClasses;
	}
	
	@Override
	public List<CheckId> getDependencies() {
		return dependencies;
	}

	@Override
	public CheckType getType() {
		return CheckType.GEOMETRY;
	}

	@Override
	public Check createNewInstance() {
		return new InteriorDisconnectedCheck();
	}
}