import ij.IJ;
import ij.ImagePlus; // for ImagePlus
import ij.gui.GenericDialog;
import ij.gui.Overlay;
import ij.gui.PolygonRoi;
import ij.gui.Roi;
import ij.plugin.filter.PlugInFilter; // for PlugInFilter
import ij.process.ByteProcessor;
import ij.process.ImageProcessor; // for ImageProcessor

import java.awt.Color;
import java.awt.Point;
import java.awt.Polygon;

public class darkest_Spot implements PlugInFilter {

    int blockSize = 15;

    public int setup(String arg, ImagePlus imp) {
        return PlugInFilter.DOES_RGB + PlugInFilter.NO_UNDO
                + PlugInFilter.NO_CHANGES;
    }

    public void run(ImageProcessor ip) {
        if (!ip.isGrayscale()) {
            ip = new Color_2_Gray().color2Gray(ip);
        }
        blockSize = Dialog.getBlocksizeFromDialog();
        long startTime, stopTime, diffTime;
        startTime = System.currentTimeMillis();
        Point corner = getDarkestSpot(ip, blockSize,0);
        stopTime = System.currentTimeMillis();
        diffTime = stopTime - startTime;
        IJ.log("time: " + diffTime + " ms");
        ImagePlus erg = createOverlayBlock(ip, "Poly",
                getPoly(corner, blockSize));
        erg.show();
    }

    private Polygon getPoly(Point corner, int blockSize) {
        Polygon myPoly = new Polygon();
        myPoly.addPoint(corner.x, corner.y);
        myPoly.addPoint(corner.x - blockSize, corner.y);
        myPoly.addPoint(corner.x - blockSize, corner.y - blockSize);
        myPoly.addPoint(corner.x, corner.y - blockSize);
        myPoly.addPoint(corner.x, corner.y);
        return myPoly;
    }
    /**
     * returns bottom right Corner of darkest Spot in Pic
     * @param ip_gray
     * @param blockSize
     * @return
     */
    public Point getDarkestSpot(ImageProcessor ip_gray, int blockSize,int pixelcutoff) {
        long[][] asb = createAsb(ip_gray);
        Point darkestSpot = new Point(0, 0);
        long darkestValue = Long.MAX_VALUE;
        long value = 0;

        for (int cols = blockSize + pixelcutoff; cols < ip_gray.getWidth() - pixelcutoff; cols++) {
            for (int rows = blockSize + pixelcutoff; rows < ip_gray.getHeight()-pixelcutoff; rows++) {
                value = (asb[rows][cols] - asb[rows][cols - blockSize]
                        - asb[rows - blockSize][cols] + asb[rows - blockSize][cols
                        - blockSize]);
                if (darkestValue > value) {
                    darkestSpot.setLocation(cols, rows);
                    darkestValue = value;
                }
            }
        }

        System.out.println(darkestSpot.x + ": " + darkestSpot.y);
        return darkestSpot;
    }

    private long[][] createAsb(ImageProcessor ip) {
        int cols = ip.getWidth();
        int rows = ip.getHeight();

        long[][] asb = new long[rows][cols];

        byte[] pic = (byte[]) ip.getPixels();
        long sum_row = 0;

        // First Row
        for (int i = 0; i < cols; i++) {
            sum_row = sum_row + (pic[i] & 0xff);
            asb[0][i] = sum_row;
        }

        // Rest
        for (int i = 1; i < (rows); i++) {
            sum_row = 0;
            for (int j = 0; j < cols; j++) {
                sum_row = sum_row + (pic[(i * cols + j)] & 0xff);
                asb[i][j] = sum_row + asb[i - 1][j];
            }
        }
        return asb;
    }

    public ImagePlus createOverlayBlock(ImageProcessor ip, String title,
            Polygon poly) {
        Roi myRoi = new PolygonRoi(poly, Roi.POLYLINE);
        myRoi.setStrokeColor(Color.RED);
        myRoi.setStrokeWidth(1);

        Overlay myOverlay = new Overlay(myRoi);
        ImagePlus impOverlay = new ImagePlus(title, ip);
        impOverlay.setOverlay(myOverlay);
        return impOverlay;
    }

}