/*
 * Copyright (C) 2010 Christian Gawron
 * 
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License version 2 as
 *  published by the Free Software Foundation.
 * 
 *  This program 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 General Public License for more details.
 * 
 * 
 * Author: Christian Gawron
 * Create date: Jan 1, 2010
 */
package uk.me.parabola.mkgmap.reader.osm;

import java.util.List;
import java.util.Map;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.log.Logger;

/** Decompose a polygon (with holes) into simple components */
public class PolygonDecomposer 
{
    private static final Logger log = Logger.getLogger(PolygonDecomposer.class);

    /**
     * Decompose the given polygon and place the resulting shapes in the outputs list.
     * @param shape The original shape (with holes).
     * @param outputs The output list consisting of polygons without holes.
     */
    public static List<Way> decompose(Way outer, List<? extends Way> inners) 
    {
	/*
	 * Idea: 
	 * 
	 * while there is outer way with an inner way do
	 *   choose an inner way
	 *   find the closest points of approach between inner and outer (Pi and Po)
	 *   connect a segment of the outer ring at Po to a segment at Pi to create a quadrilateral shape, add it to the result
	 *   merge the rest of the hole into the outer way (this removes the hole)
	 *   remove the inner way from the list
	 *
	 * This basic approach has to be refined somewhat:
	 * - The quadrilateral could in principle contain or even intersect some of the remaining holes. 
	 */

	log.info(String.format("polygon decomposer: %d inner ways", inners.size()));

	
	List<Way> result = new java.util.ArrayList<Way>();

	Map<Way, Way> isInMap = new java.util.HashMap<Way, Way>();
	List<Way> outers = new java.util.ArrayList<Way>();
	if (!outer.isClockwise()) {
	    log.warn("outer way not clockwise, reversing it");
	    outer.reverse();
	}
	outers.add(outer);
	result.add(outer);

	for (Way inner : inners) {
	    if (inner.isClockwise()) {
		log.warn("inner way not counter-clockwise, reversing it");
		inner.reverse();
	    }
	    isInMap.put(inner, outer);
	}

	while (inners.size() > 0) {
	    Way inner = inners.remove(0);
	    log.info("processing inner way " + inner);

	    int[] insert = findCpa(outer.getPoints(), inner.getPoints());
	    
	    int o0 = insert[0];
	    int o1 = o0 > 0 ? o0-1 : outer.getPoints().size()-1;
	    int i0 = insert[1];
	    int i1 = i0 < inner.getPoints().size()-1 ? i0+1 : 0;

	    Way quadrilateral = new Way(inner.getId());
	    // TODO: check for intersections!!
	    List<Coord> outList = outer.getPoints();
	    List<Coord> inList = inner.getPoints();
	    quadrilateral.addPoint(outList.get(o0));
	    quadrilateral.addPoint(inList.get(i0));
	    quadrilateral.addPoint(inList.get(i1));
	    quadrilateral.addPoint(outList.get(o1));
	    quadrilateral.addPoint(outList.get(o0));

	    result.add(quadrilateral);
	    outers.add(quadrilateral);
	    // TODO: check if the quadrilateral contains some of the inner ways!

	    int index = o1 + 1;
	    for (int i=i1; i < inList.size(); i++) {
		outList.add(index++, inList.get(i));
	    }
	    for (int i=0; i < i0; i++) {
		outList.add(index++, inList.get(i));
	    }
	}
	
	return result;
    }

    /**
     * find the Closest Point of Approach between two coordinate-lists This will
     * probably be moved to a Utils class
     * 
     * @param l1
     *            First list of points.
     * @param l2
     *            Second list of points.
     * @return The first element is the index in l1, the second in l2 which are
     *         the closest together.
     */
    private static int[] findCpa(List<Coord> l1, List<Coord> l2) {
	double oldDistance = Double.MAX_VALUE;
	Coord found1 = null;
	Coord found2 = null;
	
	for (Coord c1 : l1) {
	    for (Coord c2 : l2) {
		double newDistance = c1.distanceInDegreesSquared(c2);
		if (newDistance < oldDistance) {
		    oldDistance = newDistance;
		    found1 = c1;
		    found2 = c2;
		}
	    }
	}
	
	return new int[] { l1.indexOf(found1), l2.indexOf(found2) };
    }
}