PolygonIntersectingRingsCheck.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 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.ResultStatus;
import de.hft.stuttgart.citydoctor2.check.error.PolygonIntersectingRingsError;
import de.hft.stuttgart.citydoctor2.datastructure.LinearRing;
import de.hft.stuttgart.citydoctor2.datastructure.Polygon;
import de.hft.stuttgart.citydoctor2.math.Polygon2d;
import de.hft.stuttgart.citydoctor2.math.Ring2d;
import de.hft.stuttgart.citydoctor2.math.Segment2d;
import de.hft.stuttgart.citydoctor2.math.Vector2d;
import de.hft.stuttgart.citydoctor2.utils.Pair;
import de.hft.stuttgart.citydoctor2.utils.SerializablePair;

public class PolygonIntersectingRingsCheck extends Check {
	

	private static final List<CheckId> dependencies;
	private static final List<Class<? extends Checkable>> applicableToClasses;
	
	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_R_SELF_INTERSECTION);
		deps.add(CheckId.C_GE_P_NON_PLANAR);
		deps.add(CheckId.C_GE_P_HOLE_OUTSIDE);
		deps.add(CheckId.C_GE_P_INNER_RINGS_NESTED);
		dependencies = Collections.unmodifiableList(deps);

		ArrayList<Class<? extends Checkable>> classes = new ArrayList<>();
		classes.add(Polygon.class);
		applicableToClasses = Collections.unmodifiableList(classes);
	}
	
	public PolygonIntersectingRingsCheck() {
		super(CheckId.C_GE_P_INTERSECTING_RINGS);
	}

	@Override
	public void check(Polygon p) {
		if (p.getInnerRings().isEmpty()) {
			// polygons with no internal rings are always ok
			CheckResult cr = new CheckResult(this, ResultStatus.OK, null);
			p.addCheckResult(cr);
			return;
		}
		CheckResult cr;
		SerializablePair<LinearRing, LinearRing> intersectingRings = interiorRingsIntersectWithExterior(p);
		if (intersectingRings != null) {
			CheckError err = new PolygonIntersectingRingsError(p, intersectingRings);
			cr = new CheckResult(this, ResultStatus.ERROR, err);
		} else {
			cr = new CheckResult(this, ResultStatus.OK, null);
		}
		p.addCheckResult(cr);
	}
	
	public SerializablePair<LinearRing, LinearRing> interiorRingsIntersectWithExterior(Polygon p) {
		List<Pair<LinearRing, List<Segment2d>>> ringSegments = projectTo2D(p);
		for (int i = 0; i < ringSegments.size() - 1; i++) {
			Pair<LinearRing, List<Segment2d>> ring = ringSegments.get(i);
			for (int j = i + 1; j < ringSegments.size(); j++) {
				Pair<LinearRing, List<Segment2d>> ring2 = ringSegments.get(j);
				if (doRingsIntersect(ring.getValue1(), ring2.getValue1())) {
					return new SerializablePair<>(ring.getValue0(), ring2.getValue0());
				}
			}
		}
		return null;
	}

	private List<Pair<LinearRing, List<Segment2d>>> projectTo2D(Polygon p) {
		List<Pair<LinearRing, List<Segment2d>>> ringSegments = new ArrayList<>();
		Polygon2d projectedPolygon = Polygon2d.withProjection(p);
		createSegments(ringSegments, projectedPolygon.getExterior());
		for (Ring2d interior : projectedPolygon.getInteriorRings()) {
			createSegments(ringSegments, interior);
		}
		return ringSegments;
	}

	private void createSegments(List<Pair<LinearRing, List<Segment2d>>> ringSegments, Ring2d ring) {
		List<Vector2d> vertices = ring.getVertices();
		List<Segment2d> segments = new ArrayList<>();
		for (int i = 0; i < vertices.size() - 1; i++) {
			segments.add(new Segment2d(vertices.get(i), vertices.get(i + 1)));
		}
		ringSegments.add(new Pair<>(ring.getOriginal(), segments));
	}

	private boolean doRingsIntersect(List<Segment2d> r1, List<Segment2d> r2) {
		for (Segment2d seg1 : r1) {
			for (Segment2d seg2 : r2) {
				if (seg1.intersects(seg2)) {
					return true;
				}
			}
		}
		return false;
	}

	@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 PolygonIntersectingRingsCheck();
	}
}