MovedRing.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.math;

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

import de.hft.stuttgart.citydoctor2.datastructure.LinearRing;
import de.hft.stuttgart.citydoctor2.datastructure.Vertex;

/**
 * A ring moved by an offset. Used to avoid numerical inaccuracies
 * 
 * @author Matthias Betz
 *
 */
public class MovedRing {

	private List<Vector3d> vertices;
	private LinearRing original;

	public static MovedRing ofRing(LinearRing ring, Vector3d movedBy) {
		MovedRing indRing = new MovedRing();
		indRing.original = ring;
		for (Vertex v : ring.getVertices()) {
			Vector3d movedV = new Vector3d(v.getX() - movedBy.getX(), v.getY() - movedBy.getY(),
					v.getZ() - movedBy.getZ());
			indRing.addVertex(movedV);
		}
		return indRing;
	}

	public LinearRing getOriginal() {
		return original;
	}

	public MovedRing() {
		vertices = new ArrayList<>();
	}

	public void addVertex(Vector3d v) {
		vertices.add(v);
	}

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

	/**
	 * 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
		List<Vector2d> projectedRing = new ArrayList<>();
		Vector2d point;
		Vector3d normal = calculateNormal();

		double x = Math.abs(normal.getX());
		double y = Math.abs(normal.getY());
		double z = Math.abs(normal.getZ());
		
		if (x >= y && x >= z) {
			for (Vector3d vert : vertices) {
				Vector2d projCoords = new Vector2d(vert.getY(), vert.getZ());
				projectedRing.add(projCoords);
			}
			point = new Vector2d(v.getY(), v.getZ());
		} else if (y >= x && y >= z) {
			for (Vector3d vert : vertices) {
				Vector2d projCoords = new Vector2d(vert.getX(), vert.getZ());
				projectedRing.add(projCoords);
			}
			point = new Vector2d(v.getX(), v.getZ());
		} else {
			for (Vector3d vert : vertices) {
				Vector2d projCoords = new Vector2d(vert.getX(), vert.getY());
				projectedRing.add(projCoords);
			}
			point = new Vector2d(v.getX(), v.getY());
		}

		int t = -1;
		for (int i = 0; i < projectedRing.size() - 1; i++) {
			t = t * crossProdTest(point, projectedRing.get(i), projectedRing.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 Vector3d calculateNormal() {
		double[] coords = new double[3];
		for (int i = 0; i < vertices.size() - 1; i++) {
			Vector3d current = vertices.get(i + 0);
			Vector3d 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 new Vector3d(1, 0, 0);
			}

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

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