RingSelfIntCheck.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.List;
import java.util.Map;
import java.util.Set;

import Jama.EigenvalueDecomposition;
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.Requirement;
import de.hft.stuttgart.citydoctor2.check.RequirementType;
import de.hft.stuttgart.citydoctor2.check.ResultStatus;
import de.hft.stuttgart.citydoctor2.check.error.DegeneratedRingError;
import de.hft.stuttgart.citydoctor2.check.error.PointTouchesEdgeError;
import de.hft.stuttgart.citydoctor2.check.error.RingEdgeIntersectionError;
import de.hft.stuttgart.citydoctor2.checks.Checks;
import de.hft.stuttgart.citydoctor2.checks.util.CollectionUtils;
import de.hft.stuttgart.citydoctor2.datastructure.BoundingBox;
import de.hft.stuttgart.citydoctor2.datastructure.Edge;
import de.hft.stuttgart.citydoctor2.datastructure.Geometry;
import de.hft.stuttgart.citydoctor2.datastructure.LinearRing;
import de.hft.stuttgart.citydoctor2.datastructure.Vertex;
import de.hft.stuttgart.citydoctor2.math.CovarianceMatrix;
import de.hft.stuttgart.citydoctor2.math.DistanceResult;
import de.hft.stuttgart.citydoctor2.math.Matrix3x3d;
import de.hft.stuttgart.citydoctor2.math.OrthogonalRegressionPlane;
import de.hft.stuttgart.citydoctor2.math.Segment3d;
import de.hft.stuttgart.citydoctor2.math.Vector3d;
import de.hft.stuttgart.citydoctor2.parser.ParserConfiguration;

/**
 * Checks whether a ring self intersects. Also checks if a point is too close to
 * an edge of the ring.
 * 
 * @author Matthias Betz
 *
 */
public class RingSelfIntCheck extends Check {

	private static final String EPSILON_NAME = "minVertexDistance";

	// check requirement class for default parameters
	private double degeneratedRingTolerance = 0.01;
	private double epsilon = Checks.MIN_VERTEX_DISTANCE_DEFAULT;

	
	private static final List<CheckId> dependencies;

	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);
		dependencies = Collections.unmodifiableList(deps);
	}


	@Override
	public void init(Map<String, String> parameters, ParserConfiguration config) {
		String epsilonString = parameters.get(EPSILON_NAME);
		if (epsilonString != null) {
			epsilon = Double.parseDouble(epsilonString);
		}
		if (parameters.containsKey(Requirement.DEGENERATED_RING_TOLERANCE)) {
			degeneratedRingTolerance = Double.parseDouble(parameters.get(Requirement.DEGENERATED_RING_TOLERANCE));
		}
	}

	@Override
	public void check(LinearRing lr) {
		checkRingJava(lr);
	}

	private void checkRingJava(LinearRing lr) {
		// check for tiny edge as well
		// store all used points in temporary list
		List<Vertex> vertices = lr.getVertices();
		Vector3d centroid = CovarianceMatrix.getCentroid(vertices);
		EigenvalueDecomposition ed = OrthogonalRegressionPlane.decompose(vertices, centroid);
		if (checkEigenvalues(lr, vertices, ed)) {
			// found tiny edge error, abort further checking
			return;
		}
		
		
		List<Edge> edges = getEdgesForRing(lr);

		for (Edge e : edges) {
			if (checkForPointsTouchingEdge(lr, e)) {
				return;
			}
		}

		for (int i = 0; i < edges.size() - 1; i++) {
			Edge e1 = edges.get(i);

			for (int j = i + 1; j < edges.size(); j++) {
				Edge e2 = edges.get(j);
				if (e1.getConnectionPoint(e2) != null) {
					continue;
				}
				Segment3d s1 = new Segment3d(e1.getFrom(), e1.getTo());
				Segment3d s2 = new Segment3d(e2.getFrom(), e2.getTo());
				DistanceResult dr = s1.getDistanceResult(s2);
				if (dr.getDistance() < epsilon) {
					// intersection
					CheckError err = new RingEdgeIntersectionError(lr, e1, e2, dr.getPoint1());
					CheckResult cr = new CheckResult(this, ResultStatus.ERROR, err);
					lr.addCheckResult(cr);
					return;
				}
			}
		}

		// no errors detected
		CheckResult cr = new CheckResult(this, ResultStatus.OK, null);
		lr.addCheckResult(cr);
	}
	
	private boolean checkEigenvalues(LinearRing lr, List<Vertex> points, EigenvalueDecomposition ed) {
		Matrix3x3d mat = new Matrix3x3d(ed.getV().getArray());
		List<Vector3d> rotatedVertices = new ArrayList<>();
		for (Vertex v : points) {
			rotatedVertices.add(mat.mult(v));
		}
		BoundingBox bbox = BoundingBox.ofPoints(rotatedVertices);

		int nrOfEigenvaluesBelowTolerance = 0;
		if (bbox.getWidth() < degeneratedRingTolerance) {
			nrOfEigenvaluesBelowTolerance++;
		}
		if (bbox.getHeight() < degeneratedRingTolerance) {
			nrOfEigenvaluesBelowTolerance++;
		}
		if (bbox.getDepth() < degeneratedRingTolerance) {
			nrOfEigenvaluesBelowTolerance++;
		}

		if (nrOfEigenvaluesBelowTolerance >= 2) {
			CheckError err = new DegeneratedRingError(lr);
			lr.addCheckResult(new CheckResult(this, ResultStatus.ERROR, err));
			return true;
		}
		return false;
	}

	private boolean checkForPointsTouchingEdge(LinearRing lr, Edge e1) {
		Segment3d seg = new Segment3d(e1.getFrom(), e1.getTo());
		for (Vertex v : lr.getVertices()) {
			if (v != e1.getFrom() && v != e1.getTo() && seg.getDistance(v) < epsilon) {
				CheckError err = new PointTouchesEdgeError(lr, e1, v);
				CheckResult cr = new CheckResult(this, ResultStatus.ERROR, err);
				lr.addCheckResult(cr);
				return true;
			}
		}
		return false;
	}

	private List<Edge> getEdgesForRing(LinearRing lr) {
		List<Edge> edges = new ArrayList<>();
		Geometry geom = lr.getParent().getParent();
		for (int i = 0; i < lr.getVertices().size() - 1; i++) {
			Vertex v1 = lr.getVertices().get(i);
			Vertex v2 = lr.getVertices().get(i + 1);
			Edge e = geom.getEdge(v1, v2);
			if (e == null) {
				throw new IllegalStateException("Edge between v1=" + v1 + " to v2=" + v2 + " is missing");
			}
			edges.add(e);
		}
		return edges;
	}

	@Override
	public List<CheckId> getDependencies() {
		return dependencies;
	}

	@Override
	public Set<Requirement> appliesToRequirements() {
		return CollectionUtils.singletonSet(Requirement.R_GE_R_SELF_INTERSECTION);
	}

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

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

	@Override
	public CheckId getCheckId() {
		return CheckId.C_GE_R_SELF_INTERSECTION;
	}
}