IntersectPolygon2d.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.edge;

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

public class IntersectPolygon2d {

	private IntersectPolygon2d() {
		// only static use
	}

	public static List<Polygon2dPolygon2dInt> getIntersections(Polygon2d mcpPolygon1, Polygon2d mcpPolygon2,
			double epsilon) {
		List<Polygon2dPolygon2dInt> mpIntersections = new ArrayList<>();

		List<PolyLineSegment2d> segments = new ArrayList<>();
		calculateIntersectionSegments(mcpPolygon1, mcpPolygon2, mcpPolygon1, mcpPolygon2, segments, epsilon);
		calculateIntersectionSegments(mcpPolygon1, mcpPolygon2, mcpPolygon2, mcpPolygon1, segments, epsilon);

		List<PolyLine2d> polyLines = buildPolyLines(segments);
		
		for (PolyLine2d line : polyLines) {
			IntersectionType intType;
			if (line.getFirstSegment() == line.getLastSegment()) {
				Point2d startPnt = line.getStart().getPoint();
				Coordinate2d endCoordinate = line.getEnd();
				Point2d endPnt = endCoordinate.getPoint();

				if (startPnt.isAlmostEqual(endPnt)) {
					// point intersection ==> normal intersection
					endCoordinate.setPoint(startPnt);
					intType = IntersectionType.NORMAL_INTERSECTION;
				} else {
					// partially/fully embedded edge intersection
					int hitsPoly1 = getNumberOfCoincidentNodes(mcpPolygon1, startPnt, endPnt);
					int hitsPoly2 = getNumberOfCoincidentNodes(mcpPolygon2, startPnt, endPnt);

					if ((0 == hitsPoly1 && 2 == hitsPoly2) || (1 == hitsPoly1 && 2 == hitsPoly2)
							|| (2 == hitsPoly1 && 0 == hitsPoly2) || (2 == hitsPoly1 && 1 == hitsPoly2)
							|| (2 == hitsPoly1 && 2 == hitsPoly2)) {
						intType = IntersectionType.FULLY_EMBEDDED_EDGE;
					} else if ((1 == hitsPoly1 && 1 == hitsPoly2)) {
						intType = IntersectionType.PARTIALLY_EMBEDDED_EDGE;
					} else {
						// this shouldn't happen, something went wrong
						throw new IllegalStateException("Unable to determine intersection type for polygons ");
					}
				}
			} else {
				intType = IntersectionType.PARTIALLY_EMBEDDED_POLYGON;
				if (isFullyInPolygon(mcpPolygon2, mcpPolygon1)) {
					// is mcpPolygon2 fully in mcpPolygon1?
					intType = IntersectionType.POLYGON_1_FULLY_EMBEDDED;
					// not perfect but necessary for problems just like 'is polygon of a door in the
					// polygon if the surrounding wall'
					if (!mcpPolygon2.isPointInsidePolygon(mcpPolygon1.getMidPoint())) {
						intType = IntersectionType.FULLY_EMBEDDED_EDGE;
					}

				} else if (isFullyInPolygon(mcpPolygon1, mcpPolygon2)) {
					// is mcpPolygon1 fully in mcpPolygon2?

					intType = IntersectionType.POLYGON_2_FULLY_EMBEDDED;
					// not perfect but necessary for problems just like 'is polygon of a door in the
					// polygon if the surrounding wall'
					if (!mcpPolygon1.isPointInsidePolygon(mcpPolygon2.getMidPoint())) {
						intType = IntersectionType.FULLY_EMBEDDED_EDGE;
					}
				}
			}
			// Const cast is needed, because the intersection result calls ref on
			// the polygons. The reason is, that the intersection of loops of a PoylgonNS
			// creates temporary Polygon2d's which will be invalid after the intersections
			// are calculated and thus the intersection results holds invalid objects
			Polygon2dPolygon2dInt ppi = new Polygon2dPolygon2dInt(mcpPolygon1, mcpPolygon2, line, intType);
			mpIntersections.add(ppi);
		}
		return mpIntersections;
	}

	private static boolean isFullyInPolygon(Polygon2d poly, Polygon2d checkPoly) {
		List<Coordinate2d> pListCoord2d;
		boolean bPoly2FullyInPoly1 = true;
		pListCoord2d = checkPoly.getCoordinates();
		for (Coordinate2d coord : pListCoord2d) {
			bPoly2FullyInPoly1 &= poly.isPointInsidePolygon(coord.getPoint());
		}
		return bPoly2FullyInPoly1;
	}

	private static int getNumberOfCoincidentNodes(Polygon2d cpPolygon, Point2d crStartPnt, Point2d crEndPnt) {
		HalfEdge2d cCurrHe = cpPolygon.getFirstHalfEdge();
		HalfEdge2d cStartHe = cCurrHe;
		int hits = 0;

		do {
			Point2d currStart = cCurrHe.getStart().getPoint();
			if (currStart.isAlmostEqual(crStartPnt)) {
				hits++;
				if (overlapsWithCurrOrPrevHE(cCurrHe, crEndPnt)) {
					hits++;
				}
				break;
			} else if (currStart.isAlmostEqual(crEndPnt)) {
				hits++;
				if (overlapsWithCurrOrPrevHE(cCurrHe, crStartPnt)) {
					hits++;
				}
				break;
			}
			cCurrHe = cCurrHe.getNext();
		} while (cCurrHe != null && cCurrHe != cStartHe);
		return hits;
	}

	private static boolean overlapsWithCurrOrPrevHE(HalfEdge2d cpHE, Point2d crPnt) {
		return cpHE.getEnd().getPoint().isAlmostEqual(crPnt)
				|| cpHE.getPrevious().getStart().getPoint().isAlmostEqual(crPnt);
	}

	private static List<PolyLine2d> buildPolyLines(List<PolyLineSegment2d> rSegments) {
		List<PolyLine2d> orIntPolyLines = new ArrayList<>();
		if (rSegments.isEmpty()) {
			return orIntPolyLines;
		}
		checkSegmentsForDuplicatedSegments(rSegments);

		// build PolyLines
		while (!rSegments.isEmpty()) {
			Iterator<PolyLineSegment2d> currSegIt = rSegments.iterator();
			PolyLineSegment2d next = currSegIt.next();

			// cout << "rSegments.size(): " << rSegments.size() << endl;
			PolyLineSegment2d pCurrLeftSeg = next;
			PolyLineSegment2d pCurrRightSeg = next;
			currSegIt.remove();
			if (!currSegIt.hasNext()) {
				// only one line-segment
				orIntPolyLines.add(new PolyLine2d(pCurrLeftSeg));
				return orIntPolyLines;
			}
			// How the PolyLine notion is defined here:
			// leftEnd <--Segment--> <--Segment--> <--Segment--> rightEnd
			// if leftEnd == rightEnd, I have a closed PolyLine
			Point2d polyLineRightEnd = pCurrLeftSeg.getEnd().getPoint();
			Point2d polyLineLeftEnd = pCurrLeftSeg.getStart().getPoint();

			while (currSegIt.hasNext()) {
				next = currSegIt.next();
				Point2d localeRightEnd = next.getEnd().getPoint();
				Point2d localeLeftEnd = next.getStart().getPoint();

				// check if current segments fits the current PolyLine at the rightEnd
				boolean fitsRightEnd = false;
				if (polyLineRightEnd.isAlmostEqual(localeLeftEnd)) {
					fitsRightEnd = true;
				} else if (polyLineRightEnd.isAlmostEqual(localeRightEnd)) {
					next.reverse();
					fitsRightEnd = true;
				}

				if (fitsRightEnd) {
					pCurrRightSeg.setNext(next);
					next.setStart(pCurrRightSeg.getEnd());
					pCurrRightSeg = next;
					polyLineRightEnd = pCurrRightSeg.getEnd().getPoint();
				}

				// check if current segments fits the current PolyLine at the leftEnd
				boolean fitsLeftEnd = false;
				if (polyLineLeftEnd.isAlmostEqual(localeRightEnd)) {
					fitsLeftEnd = true;
				} else if (polyLineLeftEnd.isAlmostEqual(localeLeftEnd)) {
					next.reverse();
					fitsLeftEnd = true;
				}

				if (fitsLeftEnd) {
					next.setNext(pCurrLeftSeg);
					next.setEnd(pCurrLeftSeg.getStart());
					pCurrLeftSeg = next;
					polyLineLeftEnd = pCurrLeftSeg.getStart().getPoint();
				}

				// If the current PolyLineSegments fits at least one end, delete the
				// segment from the list and start over; otherwise continue
				if (fitsLeftEnd || fitsRightEnd) {
					currSegIt.remove();
					currSegIt = rSegments.iterator();
//					next = currSegIt.next();

					if (pCurrLeftSeg == pCurrRightSeg) {
						pCurrLeftSeg = pCurrLeftSeg.getNext();
						pCurrRightSeg.setNext(null);
						break;
					}
				}
			} // inner while

			if (null == pCurrLeftSeg.getNext() && pCurrLeftSeg.getStart() != pCurrLeftSeg.getEnd()) {
				// only one segment, we need at least 2 non point segments to create a
				// closed polyline
				// delete single segment
			} else {
				orIntPolyLines.add(new PolyLine2d(pCurrLeftSeg));
			}

		} // outer while

		// there might be loops in the PolyLine
		checkForDoubleUsedPoints(orIntPolyLines);

		return orIntPolyLines;
	}

	private static void checkForDoubleUsedPoints(List<PolyLine2d> orIntPolyLines) {
		for (int i = 0; i < orIntPolyLines.size(); i++) {
			PolyLine2d currPolyLine = orIntPolyLines.get(i);
			List<PolyLineSegment2d> segs = currPolyLine.getSegments();
			if (2 == segs.size()) {
				PolyLine2d newPolyLine = new PolyLine2d(segs.get(0).getStart(), segs.get(0).getEnd());
				orIntPolyLines.add(newPolyLine);
				continue;
			}
			List<Coordinate2d> coords = currPolyLine.getCoordinates();
			for (Coordinate2d cIt1 : coords) {
				Point2d currPoint = cIt1.getPoint();
				for (Coordinate2d cIt2 : coords) {
					Point2d checkPoint = cIt2.getPoint();
					// only check for geometrically equal points; this is needed,
					// we have a closed PolyLine (start and end point referring to
					// the same Coordinate2d)
					if (cIt1 != cIt2 && currPoint.isAlmostEqual(checkPoint))// edited by JvF on 15/02/2013
					{
						// we found a loop in the polyLine
						// ==> cut it out, and sew the endings together

						PolyLine2d right = currPolyLine.split(cIt1);
						PolyLine2d rightRight = right.split(cIt2);

						PolyLineSegment2d startRight = right.getFirstSegment();
						PolyLineSegment2d endRight = right.getLastSegment();

						// the ending coordinates need to be switched, because the erase
						// method of std::list deletes the range [first, last), thus the
						// ending coordinate of the original polyline would be removed
						// instead of the ending of the loop
						currPolyLine.getLastSegment().setEnd(endRight.getEnd());

						// sewing the endings of the loop
						endRight.setEnd(startRight.getStart());
						endRight.setNext(null);
						// insert the new PolyLine; it will be checked for double nodes later
						orIntPolyLines.add(right);

						// sew the orignal polyline together, where the loop was cut out
						currPolyLine.append(rightRight);

						// erase the coordinates from the loop out of the list; these
						// coordinates are checked later
						coords.remove(cIt1);
						coords.remove(cIt2);
					}
				}
			}
		}

	}

	private static void checkSegmentsForDuplicatedSegments(List<PolyLineSegment2d> rSegments) {
		// code edit JvF: old 'Code doesnt work correctly new one does// should TODO:
		// test it with other examples (where a point segment with multiplicity 2 is
		// given)
		// segment suchen, dass kein punkt ist
		// dann immer von vorne starten und punkte / segmente suchen die geometrische
		// mit dem aktuellen segment übereinstimmen
		// löschen falls das der fall ist
		// edited by Jvf on 19/2/2013
		// start--------------------------------------------------------------------------------------

		double eps = 0.00001;

		List<PolyLineSegment2d> lines = new ArrayList<>();
		List<PolyLineSegment2d> points = new ArrayList<>();
		// separate segments in lines and points
		for (PolyLineSegment2d seg : rSegments) {
			boolean segIsPoint = seg.getLength() < eps;
			if (segIsPoint) {
				points.add(seg);
			} else {
				lines.add(seg);
			}
		}

		// eliminate points that are connected to lines
		for (PolyLineSegment2d line : lines) {
			Iterator<PolyLineSegment2d> pointsit = points.iterator();
			Point2d startSegPnt = line.getStart().getPoint();
			Point2d endSegPnt = line.getEnd().getPoint();
			while (pointsit.hasNext()) {
				PolyLineSegment2d pointSegment = pointsit.next();
				Point2d pnt = pointSegment.getStart().getPoint();
				boolean isConnectedToSegment = (pnt.isAlmostEqual(startSegPnt, eps)
						|| pnt.isAlmostEqual(endSegPnt, eps));
				if (isConnectedToSegment) {
					pointsit.remove();
				}
			}
		}

		// eliminate geometric equal lines
		for (int i = 0; i < lines.size() - 1; i++) {
			PolyLineSegment2d line1 = lines.get(i);
			List<PolyLineSegment2d> remainingSegments = new ArrayList<>();
			// the first segment cannot be duplicated
			for (int j = 0; j < i + 1; j++) {
				remainingSegments.add(lines.get(j));
			}
			for (int j = i + 1; j < lines.size(); j++) {
				PolyLineSegment2d line2 = lines.get(j);
				boolean isGeometricallyEqual = line1.isGeometricallyEqual(line2, eps);
				if (!isGeometricallyEqual) {
					remainingSegments.add(line2);
				}
			}
			// only the non duplicate segments are contained here
			lines = remainingSegments;
		}
		rSegments.clear();
		rSegments.addAll(lines);
		rSegments.addAll(points);
		

//		Iterator<PolyLineSegment2d> currSegIt = rSegments.iterator();
//		PolyLineSegment2d currSegItNext = currSegIt.next();
//		while (currSegIt.hasNext()) {
//			Iterator<PolyLineSegment2d> toCheckIt = rSegments.iterator();
//			PolyLineSegment2d toCheckItNext = toCheckIt.next();
//
//			Point2d startSegPnt = currSegItNext.getStart().getPoint();
//			Point2d endSegPnt = currSegItNext.getEnd().getPoint();
//
//			while (toCheckIt.hasNext()) {
//				Point2d pnt = toCheckItNext.getStart().getPoint();
//				boolean isNotTheSameIterator = (currSegItNext != toCheckItNext);
//				boolean currSegIsPoint = toCheckItNext.getLength() < eps;
//				boolean isConnectedToSegment = (pnt.isAlmostEqual(startSegPnt, eps)
//						|| pnt.isAlmostEqual(endSegPnt, eps));
//				boolean isGeometricallyEqual = currSegItNext.isGeometricallyEqual(toCheckItNext, eps);
//
//				// check if the current segment is obsolete
//				if (isNotTheSameIterator && ((currSegIsPoint && isConnectedToSegment) || isGeometricallyEqual)) {
//					toCheckIt.remove();
//					toCheckItNext = toCheckIt.next();
//				} else {
//					toCheckItNext = toCheckIt.next();
//				} // else
//			} // inner while
//			currSegItNext = currSegIt.next();
//		} // outer while

	}

	private static void calculateIntersectionSegments(Polygon2d mcpPolygon1, Polygon2d mcpPolygon2,
			Polygon2d cpFirstPolygon, Polygon2d cpIntersectWithFirstPolygon, List<PolyLineSegment2d> segments,
			double eps) {
		List<HalfEdge2d> polyHEs = cpFirstPolygon.getHalfEdges();

		for (HalfEdge2d he : polyHEs) {
			if (he.getPartner() != null && he.getPartner().getPolygon() == cpIntersectWithFirstPolygon) {
				// both polygons sharing this edge, no need to intersect it
				// NOTE: it's assumed, that the polygons aren't self intersecting
				continue;
			}

			GmBoundedStraight2d straight = he.getStraight();
			List<Interval> intList = IntersectPolygonAndStraight2d.intersect(cpIntersectWithFirstPolygon, straight,
					eps);
			List<PolyLineSegment2d> newSegs = createSegments(mcpPolygon1, mcpPolygon2, eps, intList, straight);
			newSegs.addAll(segments);
			segments.clear();
			segments.addAll(newSegs);
		}
	}

	private static List<PolyLineSegment2d> createSegments(Polygon2d mcpPolygon1, Polygon2d mcpPolygon2, double eps,
			List<Interval> crIntersectionIntervals, GmBoundedStraight2d crHalfEdgeStraight) {
		/*
		 * An intersection interval consists of two parameter values (t_a, t_e)
		 * referring to the intersecting straight (g(t_i) = p + t_i*v). This straight is
		 * created from a HalfEdge2d. It is possible that the calculated intersection
		 * extend the restricted domain of the underlying HalfEdge2d. Normally you need
		 * to check, if the values of the interval are inside the interval [0,1], but
		 * the direction vector of the straight is normalized during the creation of the
		 * straight, thats why an additional treatment is neccessary.
		 */
		List<PolyLineSegment2d> orSegments = new ArrayList<>();

		double len = crHalfEdgeStraight.getLength();
		Interval validInterval = new Interval(0, len);
		for (Interval interval : crIntersectionIntervals) {
			Interval overlap = validInterval.overlap(interval);

			if (!overlap.isValid()) {
				continue;
			}
			Point2d pntStart = crHalfEdgeStraight.evaluate(overlap.getStart());

			// check if point interval is a coordinate of both polygons
			if (overlap.getLength() < Global.getHighAccuracyTolerance() * 100
					&& bothPolygonsSharingThisPointAsCoordinate(mcpPolygon1, mcpPolygon2, pntStart, eps)) {
				continue;
			}

			Coordinate2d pStart = new Coordinate2d(pntStart);
			Point2d pntEnd = crHalfEdgeStraight.evaluate(overlap.getEnd());
			Coordinate2d pEnd = new Coordinate2d(pntEnd);
			orSegments.add(new PolyLineSegment2d(pStart, pEnd));
		}
		return orSegments;
	}

	private static boolean bothPolygonsSharingThisPointAsCoordinate(Polygon2d mcpPolygon1, Polygon2d mcpPolygon2,
			Point2d crIntPnt, double eps) {
		List<Coordinate2d> coords = mcpPolygon1.getCoordinates();
		Coordinate2d tmp = null;
		for (Coordinate2d it : coords) {
			if (crIntPnt.isAlmostEqual(it.getPoint(), eps)) {
				tmp = it;
				break;
			}
		}

		if (tmp != null) {
			// check if mcpPolygon2 contains the same coordiante2d
			coords = mcpPolygon2.getCoordinates();
			for (Coordinate2d it : coords) {
				if (it == tmp) {
					return true;
				}
			}
		}
		return false;
	}

}