LinearRing.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.datastructure;

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

import de.hft.stuttgart.citydoctor2.check.Check;
import de.hft.stuttgart.citydoctor2.math.ProjectionAxis;
import de.hft.stuttgart.citydoctor2.math.Ring2d;
import de.hft.stuttgart.citydoctor2.math.UnitVector3d;
import de.hft.stuttgart.citydoctor2.math.Vector2d;
import de.hft.stuttgart.citydoctor2.math.Vector3d;
import de.hft.stuttgart.citydoctor2.utils.CopyHandler;
import de.hft.stuttgart.citydoctor2.utils.Copyable;

/**
 * Represents a linear ring used in polygons. The ring contains the vertices.
 * 
 * @author Matthias Betz
 *
 */
public class LinearRing extends GmlElement {

	private static final long serialVersionUID = -2488180830514940722L;

	private LinearRingType type;
	private Polygon parent;

	private List<Vertex> vertices = new ArrayList<>();

	public enum LinearRingType {
		EXTERIOR, INTERIOR
	}

	public LinearRing(LinearRingType type) {
		this.type = type;
	}

	/**
	 * Checks whether a point is inside this ring. A point on the edge does count as
	 * inside.
	 * 
	 * @param v the point.
	 * @return true if the point is inside or on an edge, false if it is outside.
	 */
	public boolean isPointInside(Vector3d v) {
		// project to 2d ring
		ProjectionAxis axis = ProjectionAxis.of(this);
		Vector2d point = axis.project(v);
		Ring2d ring = Ring2d.of(this, axis);

		int t = -1;
		for (int i = 0; i < ring.getVertices().size() - 1; i++) {
			t = t * crossProdTest(point, ring.getVertices().get(i), ring.getVertices().get(i + 1));
			if (t == 0) {
				return true;
			}
		}
		return t >= 0;
	}

	private int crossProdTest(Vector2d a, Vector2d b, Vector2d c) {
		if (a.getY() == b.getY() && a.getY() == c.getY()) {
			if ((b.getX() <= a.getX() && a.getX() <= c.getX()) || (c.getX() <= a.getX() && a.getX() <= b.getX())) {
				return 0;
			} else {
				return 1;
			}
		}
		if (a.getY() == b.getY() && a.getX() == b.getX()) {
			return 0;
		}
		if (b.getY() > c.getY()) {
			Vector2d temp = b;
			b = c;
			c = temp;
		}
		if (a.getY() <= b.getY() || a.getY() > c.getY()) {
			return 1;
		}
		return calculateDelta(a, b, c);
	}

	private int calculateDelta(Vector2d a, Vector2d b, Vector2d c) {
		double delta = (b.getX() - a.getX()) * (c.getY() - a.getY()) - (b.getY() - a.getY()) * (c.getX() - a.getX());
		if (delta > 0) {
			return -1;
		} else if (delta < 0) {
			return 1;
		} else {
			return 0;
		}
	}

	/**
	 * Calculates the normal vector of the ring. Method by Newell. If the Newell
	 * method would return a (0, 0, 0) vector a cross product is formed from the
	 * first 3 vertices. If there are no 3 vertices available (1, 0, 0) is returned.
	 * 
	 * @return the normal as a normalized vector
	 */
	public UnitVector3d calculateNormalNormalized() {
		return calculateNormal().normalize();
	}

	/**
	 * Calculates the normal vector of the ring. Method by Newell. If the Newell
	 * method would return a (0, 0, 0) vector a cross product is formed from the
	 * first 3 vertices. If there are no 3 vertices available (1, 0, 0) is returned.
	 * 
	 * @return the normal vector
	 */
	public Vector3d calculateNormal() {
		double[] coords = new double[3];
		for (int i = 0; i < vertices.size() - 1; i++) {
			Vertex current = vertices.get(i + 0);
			Vertex next = vertices.get(i + 1);
			coords[0] += (current.getZ() + next.getZ()) * (current.getY() - next.getY());
			coords[1] += (current.getX() + next.getX()) * (current.getZ() - next.getZ());
			coords[2] += (current.getY() + next.getY()) * (current.getX() - next.getX());
		}

		if (coords[0] == 0 && coords[1] == 0 && coords[2] == 0) {
			// no valid normal vector found
			if (vertices.size() < 3) {
				// no three points, return x-axis
				return UnitVector3d.X_AXIS;
			}

			Vertex v1 = vertices.get(0);
			Vertex v2 = vertices.get(1);
			Vertex v3 = vertices.get(2);
			return calculateNormalWithCross(v1, v2, v3);
		}
		return new Vector3d(coords);
	}

	public double getArea() {
		int n = vertices.size();
		if (n < 3)
			return 0.0; // a degenerated polygon

		// prepare an vertex array with n+2 vertices:
		// V[0] ... V[n-1] - the n different vertices
		// V[n]=V[0]
		// V[n+1]=V[1]
		Vertex[] vertexArray = new Vertex[n + 2];
		for (int i = 0; i < n; i++) {
			vertexArray[i] = vertices.get(i);
		}
		vertexArray[n] = vertices.get(0);
		vertexArray[n + 1] = vertices.get(1);
		double area = 0;

		// make sure the normal has been calculated
		Vector3d normal = calculateNormal();
		// select largest abs coordinate to ignore for projection
		double ax = Math.abs(normal.getX()); // abs x-coord
		double ay = Math.abs(normal.getY()); // abs y-coord
		double az = Math.abs(normal.getZ()); // abs z-coord

		// coord to ignore: 1=x, 2=y, 3=z
		int coord = 3; // ignore z-coord
		if (ax > ay) {
			if (ax > az) {
				coord = 1; // ignore x-coord
			}
		} else if (ay > az) {
			coord = 2; // ignore y-coord
		}

		// compute area of the 2D projection
		for (int i = 1, j = 2, k = 0; i <= vertexArray.length - 2; i++, j++, k++) {
			switch (coord) {
			case 1:
				area += (vertexArray[i].getY() * (vertexArray[j].getZ() - vertexArray[k].getZ()));
				break;
			case 2:
				area += (vertexArray[i].getX() * (vertexArray[j].getZ() - vertexArray[k].getZ()));
				break;
			case 3:
				area += (vertexArray[i].getX() * (vertexArray[j].getY() - vertexArray[k].getY()));
				break;
			default:
				throw new IllegalStateException();
			}
		}

		// scale to get area before projection
		double an = Math.sqrt(ax * ax + ay * ay + az * az); // length of normal vector

		switch (coord) {
		case 1:
			area *= (an / (2 * ax));
			break;
		case 2:
			area *= (an / (2 * ay));
			break;
		case 3:
			area *= (an / (2 * az));
			break;
		default:
			throw new IllegalStateException();
		}

		return Math.abs(area);
	}

	private UnitVector3d calculateNormalWithCross(Vertex v1, Vertex v2, Vertex v3) {
		Vector3d dir1 = v2.minus(v1);
		Vector3d dir2 = v3.minus(v1);
		Vector3d cross = dir1.cross(dir2);
		return cross.normalize();
	}

	@Override
	public void accept(Check c) {
		super.accept(c);
		if (c.canExecute(this)) {
			c.check(this);
		}
	}

	@Override
	public void clearAllContainedCheckResults() {
		super.clearCheckResults();
	}

	public void setParent(Polygon polygon) {
		parent = polygon;
	}

	public Polygon getParent() {
		return parent;
	}

	public LinearRingType getType() {
		return type;
	}

	public List<Vertex> getVertices() {
		return vertices;
	}

	public void addVertex(Vertex v) {
		vertices.add(v);
		if (parent == null) {
			return;
		}
		if (parent.isLinkedTo()) {
			v.addAdjacentRing(this, parent.getLinkedFromPolygon().getParent());
		}
		v.addAdjacentRing(this, parent.getParent());
	}

	public void addVertex(int i, Vertex v) {
		vertices.add(i, v);
		if (parent.isLinkedTo()) {
			v.addAdjacentRing(this, parent.getLinkedFromPolygon().getParent());
		}
		v.addAdjacentRing(this, parent.getParent());
	}

	public void setVertex(int i, Vertex v) {
		vertices.set(i, v);
		if (parent.isLinkedTo()) {
			v.addAdjacentRing(this, parent.getLinkedFromPolygon().getParent());
		}
		v.addAdjacentRing(this, parent.getParent());
	}

	@Override
	public String toString() {
		return "LinearRing [type=" + type + ", gmlId=" + getGmlId() + "]";
	}

	void anonymize() {
		setGmlId(GmlId.generateId());
	}

	public boolean isRingConnectedViaPoint(LinearRing other) {
		for (Vertex v : vertices) {
			if (other.getVertices().contains(v)) {
				return true;
			}
		}
		return false;
	}

	public boolean hasPointAsCorner(Vertex v) {
		return vertices.contains(v);
	}

	public void setType(LinearRingType type) {
		this.type = type;
	}

	public void addAllVertices(List<Vertex> extRing) {
		vertices.addAll(extRing);
	}

	@Override
	public void prepareForChecking() {
		parent.getParent().prepareForChecking();
	}

	@Override
	public void clearMetaInformation() {
		parent.getParent().clearMetaInformation();
	}

	@Override
	public void fillValues(Copyable original, CopyHandler handler) {
		super.fillValues(original, handler);
		LinearRing originalRing = (LinearRing) original;
		type = originalRing.type;
		parent = handler.getCopyInstance(originalRing.parent);
		for (Vertex v : originalRing.vertices) {
			vertices.add(handler.getCopyInstance(v));
		}
	}

	@Override
	public void collectInstances(CopyHandler handler) {
		for (Vertex v : vertices) {
			handler.addInstance(v);
		}
		handler.addInstance(parent);
	}

	@Override
	public Copyable createCopyInstance() {
		return new LinearRing(type);
	}
}