import java.awt.Shape;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;


/**
 * Compute the visual center of a shape using MapBox algorithm
 *
 */
public class MapBox {

	public static Point2D getVisualCenter(Shape shape) {
		return getVisualCenter(shape, 1d);
	}

	public static Point2D getVisualCenter(Shape shape, double precision) {

	    final Point2D[] polygon = toPolygon(shape);

	    // find the bounding box of the outer ring
		final Rectangle2D  bounds = shape.getBounds2D();
	    final double minX = bounds.getMinX();
	    final double minY = bounds.getMinY();
	    final double maxX = bounds.getMaxX();
	    final double maxY = bounds.getMaxY();

	    final double width = bounds.getWidth();
	    final double height = bounds.getHeight();
	    final double cellSize = Math.min(width, height);
	    double h = cellSize / 2;

	    List<Cell> cellQueue = new ArrayList<>();

	    // cover polygon with initial cells
	    for (double x = minX; x < maxX; x += cellSize) {
	        for (double y = minY; y < maxY; y += cellSize) {
	            cellQueue.add(new Cell(x + h, y + h, h, polygon));
	        }
	    }
	    Collections.sort(cellQueue,CELL_MAX);

	    // take centroid as the first best guess
	    Cell bestCell = getCentroidCell(polygon);

	    // special case for rectangular polygons
	    Cell bboxCell = new Cell(minX + width / 2, minY + height / 2, 0, polygon);
	    if (bboxCell.d > bestCell.d) bestCell = bboxCell;
 
	    while (!cellQueue.isEmpty()) {
	        // pick the most promising cell from the queue
	        Cell cell = cellQueue.remove(cellQueue.size()-1);

	        // update the best cell if we found a better one
	        if (cell.d > bestCell.d) {
	            bestCell = cell;
	        }

	        // do not drill down further if there's no chance of a better solution
	        if (cell.max - bestCell.d <= precision) continue;

	        // split the cell into four cells
	        h = cell.h / 2;
	        cellQueue.add(new Cell(cell.x - h, cell.y - h, h, polygon));
	        cellQueue.add(new Cell(cell.x + h, cell.y - h, h, polygon));
	        cellQueue.add(new Cell(cell.x - h, cell.y + h, h, polygon));
	        cellQueue.add(new Cell(cell.x + h, cell.y + h, h, polygon)); 
	        Collections.sort(cellQueue,CELL_MAX);
	    } 

	    return new Point2D.Double(bestCell.x, bestCell.y);
	}

	// signed distance from point to polygon outline (negative if point is outside)
	private static double pointToPolygonDist(double x, double y, Point2D[] polygon) {
		boolean inside = false;
		double minDistSq = Double.POSITIVE_INFINITY;

		for (int i = 0, len = polygon.length, j = len - 1; i < len; j = i++) {

			Point2D a = polygon[i];
			Point2D b = polygon[j];
	
			if ((a.getY() > y != b.getY() > y) && (x < (b.getX() - a.getX()) * (y - a.getY()) / (b.getY() - a.getY()) + a.getX()))
				inside = !inside;
	
			minDistSq = Math.min(minDistSq, getSegDistSq(x, y, a, b));
		}
	
		return (inside ? 1 : -1) * Math.sqrt(minDistSq);
	}

	// get polygon centroid
	private static Cell getCentroidCell(Point2D[] points) {
		double area = 0;
		double x = 0;
		double y = 0;

		for (int i = 0, len = points.length, j = len - 1; i < len; j = i++) {
			Point2D a = points[i];
			Point2D b = points[j];
			double f = a.getX() * b.getY() - b.getX() * a.getY();
			x += (a.getX() + b.getX()) * f;
			y += (a.getY() + b.getY()) * f;
			area += f * 3;
		}
		return new Cell(x / area, y / area, 0, points);
	}

	// get squared distance from a point to a segment
	private static double getSegDistSq(double px, double py, Point2D a, Point2D b) {

		double x = a.getX();
		double y = a.getY();
		double dx = b.getX() - x;
		double dy = b.getY() - y;

		if (dx != 0 || dy != 0) {

			double t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy);

			if (t > 1) {
				x = b.getX();
				y = b.getY();

			} else if (t > 0) {
				x += dx * t;
				y += dy * t;
			}
		}

		dx = px - x;
		dy = py - y;

		return dx * dx + dy * dy;
	}

	private static Point2D[] toPolygon(Shape shape) {
		final PathIterator pi = shape.getPathIterator(null, 0.1d);
		double coords[] = new double[6]; 
		final List<Point2D> pointList = new ArrayList<>();
		while (!pi.isDone()) {
			int s = pi.currentSegment(coords);
			switch (s) {
			case PathIterator.SEG_MOVETO:
				// Ignore
				break;

			case PathIterator.SEG_LINETO:
				pointList.add(new Point2D.Double(coords[0], coords[1]));
				break;

			case PathIterator.SEG_CLOSE:
				// Ignore
				break;

			case PathIterator.SEG_QUADTO:
				throw new AssertionError("SEG_QUADTO in flattening path iterator");
			case PathIterator.SEG_CUBICTO:
				throw new AssertionError("SEG_CUBICTO in flattening path iterator");
			}
			pi.next();
		}

		return pointList.toArray(new Point2D[pointList.size()]);
	}

	private static Comparator<Cell> CELL_MAX = new Comparator<MapBox.Cell>() {
		public int compare(Cell o1, Cell o2) {
			return (int) (o2.max - o1.max);
		};
	};
	private static final double SQRT2 = Math.sqrt(2);
	private static class Cell {

		private final double x;
		private final double y;
		private final double h;
		private final double d;
		private final double max;

		public Cell(double x, double y, double h, Point2D[] polygon) {
			this.x = x; // cell center x
			this.y = y; // cell center y
			this.h = h; // half the cell size
			this.d = pointToPolygonDist(x, y, polygon); // distance from cell center to polygon
			this.max = this.d + this.h * SQRT2; // max distance to polygon within a cell
		} 
		
	}

}