PlanarCheck.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 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.CheckType;
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.NonPlanarPolygonDistancePlaneError;
import de.hft.stuttgart.citydoctor2.check.error.NonPlanarPolygonNormalsDeviation;
import de.hft.stuttgart.citydoctor2.check.error.DegeneratedPolygonError;
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.CovarianceMatrix;
import de.hft.stuttgart.citydoctor2.math.OrthogonalRegressionPlane;
import de.hft.stuttgart.citydoctor2.math.Plane;
import de.hft.stuttgart.citydoctor2.math.Triangle3d;
import de.hft.stuttgart.citydoctor2.math.Vector3d;
import de.hft.stuttgart.citydoctor2.parser.ParserConfiguration;
import de.hft.stuttgart.citydoctor2.tesselation.JoglTesselator;
import de.hft.stuttgart.citydoctor2.tesselation.TesselatedPolygon;

/**
 * Check class to check for planarity issues
 * 
 * @author Matthias Betz
 *
 */
public class PlanarCheck extends Check {

	private static final String DISTANCE = "distance";
	private static final String DISTANCE_TOLERANCE = "distanceTolerance";
	private static final String ANGLE_TOLERANCE = "angleTolerance";
	private static final String TYPE = "type";
	private static final String DEGENERATED_POLYGON_TOLERANCE = "degeneratedPolygonTolerance";

	private static final List<CheckId> dependencies;
	private static final List<DefaultParameter> defaultParameters;

	static {
		ArrayList<CheckId> deps = new ArrayList<>(4);
		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_R_SELF_INTERSECTION);
		dependencies = Collections.unmodifiableList(deps);

		ArrayList<DefaultParameter> defParameters = new ArrayList<>(3);
		defParameters.add(new DefaultParameter(TYPE, DISTANCE, Unit.NONE));
		defParameters.add(new DefaultParameter(DISTANCE_TOLERANCE, "0.01", Unit.METER));
		defParameters.add(new DefaultParameter(ANGLE_TOLERANCE, "1", Unit.DEGREE));
		defParameters.add(new DefaultParameter(DEGENERATED_POLYGON_TOLERANCE, "0.00000", Unit.METER));
		defaultParameters = Collections.unmodifiableList(defParameters);

	}

	private String planarCheckType = DISTANCE;

	private double rad = Math.toRadians(1);
	private double delta = 0.01;
	private double degeneratedPolygonTolerance = 0.00000;

	@Override
	public void init(Map<String, String> parameters, ParserConfiguration config) {
		if (parameters.containsKey(TYPE)) {
			planarCheckType = parameters.get(TYPE).toLowerCase();
		}
		if (parameters.containsKey(ANGLE_TOLERANCE)) {
			rad = Math.toRadians(Double.parseDouble(parameters.get(ANGLE_TOLERANCE)));
		}
		if (parameters.containsKey(DISTANCE_TOLERANCE)) {
			delta = Double.parseDouble(parameters.get(DISTANCE_TOLERANCE));
		}
		if (parameters.containsKey(DEGENERATED_POLYGON_TOLERANCE)) {
			degeneratedPolygonTolerance = Double.parseDouble(parameters.get(DEGENERATED_POLYGON_TOLERANCE));
		}
	}

	@Override
	public List<DefaultParameter> getDefaultParameter() {
		return defaultParameters;
	}

	@Override
	public void check(Polygon p) {
		if (DISTANCE.equals(planarCheckType)) {
			planarDistance(p);
		} else if ("angle".equals(planarCheckType)) {
			// check for tiny edge as well
			// store all used points in temporary list
			Vector3d eigenvalues = calculatedEigenvalues(p);
			if (checkEigenvalues(p, eigenvalues)) {
				// found tiny edge error, abort further checking
				return;
			}
			planarNormalDeviation(p);
		} else if ("both".equals(planarCheckType)) {
			planarDistance(p);
			planarNormalDeviation(p);
		} else {
			throw new IllegalStateException("Illegal planar check type was given: " + planarCheckType
					+ "\nChoose one of: distance, angle, both");
		}
	}

	private Vector3d calculatedEigenvalues(Polygon p) {
		ArrayList<Vertex> vertices = collectVertices(p);
		Vector3d centroid = CovarianceMatrix.getCentroid(vertices);
		EigenvalueDecomposition ed = OrthogonalRegressionPlane.decompose(vertices, centroid);
		return OrthogonalRegressionPlane.getEigenvalues(ed);
	}

	private void planarNormalDeviation(Polygon p) {
		TesselatedPolygon tp = JoglTesselator.tesselatePolygon(p);
		ArrayList<Vector3d> normals = new ArrayList<>();
		for (Triangle3d t : tp.getTriangles()) {
			Vector3d normal = t.getNormal();
			normals.add(normal);
		}
		Vector3d averageNormal = calculateAverageNormal(normals);
		averageNormal.normalize();
		for (Vector3d normal : normals) {
			normal.normalize();
			double deviation = normal.dot(averageNormal);
			double radiant = Math.acos(deviation);
			if (radiant > rad) {
				CheckError err = new NonPlanarPolygonNormalsDeviation(p, radiant);
				CheckResult cr = new CheckResult(this, ResultStatus.ERROR, err);
				p.addCheckResult(cr);
				return;
			}
		}
		CheckResult cr = p.getCheckResult(this.getCheckId());
		// only change check result if missing, otherwise might override error from
		// distance check
		if (cr == null) {
			p.addCheckResult(new CheckResult(this, ResultStatus.OK, null));
		}
	}

	private Vector3d calculateAverageNormal(ArrayList<Vector3d> normals) {
		double x = 0D;
		double y = 0D;
		double z = 0D;
		for (Vector3d normal : normals) {
			x += normal.getX();
			y += normal.getY();
			z += normal.getZ();
		}
		x = x / normals.size();
		y = y / normals.size();
		z = z / normals.size();
		return new Vector3d(x, y, z);
	}

	private void planarDistance(Polygon p) {
		// store all used points in temporary list
		ArrayList<Vertex> vertices = collectVertices(p);
		Vector3d centroid = CovarianceMatrix.getCentroid(vertices);
		EigenvalueDecomposition ed = OrthogonalRegressionPlane.decompose(vertices, centroid);
		Vector3d eigenvalues = OrthogonalRegressionPlane.getEigenvalues(ed);

		if (checkEigenvalues(p, eigenvalues)) {
			// found tiny edge error, abort further checking
			return;
		}

		Plane plane = OrthogonalRegressionPlane.calculatePlane(centroid, ed, eigenvalues);
		for (Vertex v : vertices) {
			double distance = plane.getDistance(v);
			if (distance > delta) {
				CheckError err = new NonPlanarPolygonDistancePlaneError(p, distance, v, plane);
				p.addCheckResult(new CheckResult(this, ResultStatus.ERROR, err));
				return;
			}
		}
		CheckResult cr = p.getCheckResult(this.getCheckId());
		// only change check result if missing
		if (cr == null) {
			p.addCheckResult(new CheckResult(this, ResultStatus.OK, null));
		}
	}

	private ArrayList<Vertex> collectVertices(Polygon p) {
		ArrayList<Vertex> vertices = new ArrayList<>();
		// only go to n - 1 points, because last point = first point
		for (int i = 0; i < p.getExteriorRing().getVertices().size() - 1; i++) {
			Vertex v = p.getExteriorRing().getVertices().get(i);
			vertices.add(v);
		}
		for (LinearRing lr : p.getInnerRings()) {
			for (int i = 0; i < lr.getVertices().size() - 1; i++) {
				Vertex v = lr.getVertices().get(i);
				vertices.add(v);
			}
		}
		return vertices;
	}

	private boolean checkEigenvalues(Polygon p, Vector3d eigenvalues) {
		int nrOfEigenvaluesBelowTolerance = 0;
		for (double d : eigenvalues.getCoordinates()) {
			if (d <= degeneratedPolygonTolerance) {
				nrOfEigenvaluesBelowTolerance++;
			}
		}
		if (nrOfEigenvaluesBelowTolerance >= 2) {
			CheckError err = new DegeneratedPolygonError(p);
			p.addCheckResult(new CheckResult(this, ResultStatus.ERROR, err));
			return true;
		}
		return false;
	}

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

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

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

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