Neste concurso, você precisa escrever um programa que aceite uma imagem em pixel preto e branco e tente alterá-la, de forma que a forma branca forme o domínio em estrela , com o mínimo de alterações possível.

As alterações permitidas estão transformando pixels brancos em pretos e pixels pretos em brancos.

A saída deve consistir novamente na mesma imagem, mas desta vez com todas as alterações e com o centro marcado. Os pixels que foram alterados de branco para preto devem ser exibidos em azul, os que foram alterados de preto para branco devem ser exibidos em amarelo e pelo menos um pixel central deve ser exibido em vermelho. (As cores exatas são com você.) O programa deve exibir a imagem especificada, bem como o número total de alterações que foram feitas.

Definições

Star Domain

O conjunto de pixels brancos da imagem representa um domínio em estrela se (e somente se) houver (pelo menos) um pixel central . O pixel central é um dos pixels brancos que podem ser conectados por uma linha reta a todos os outros pixels brancos, de modo que a linha atravesse apenas pixels brancos. (O pixel central não é necessariamente único.)

Linha reta entre dois pixels

Dado dois pixels (início e fim, ambos vermelhos na ilustração abaixo), a linha reta entre os dois pixels consiste em todos os pixels, que tocam na linha (matemática, amarela na ilustração abaixo) que leva do centro da primeira pixel para o centro do último pixel. Um pixel não está tocando a linha se apenas o tocar em um canto; portanto, para que ele pertença à linha de pixel, a linha (matemática, amarela) deve cruzar o pixel em questão com um comprimento diferente de zero. (Se apenas tocar o ponto de canto, isso será considerado como comprimento zero). Considere os seguintes exemplos:

Exemplo

A primeira imagem deve representar um exemplo de entrada de teste 'e as duas outras imagens representam duas saídas possíveis válidas para o exemplo dado:

As áreas amarelas (anteriormente pretas) contam também para o domínio 'branco', enquanto as áreas azuis (anteriormente brancas) contam para a parte 'preta' fora do domínio e o ponto vermelho a cada vez representa um possível pixel central.

Casos de teste

Os seguintes casos de teste são pngs, cada um com um tamanho de 256 x 256 pixels.

Pontuação

Execute seu programa com os seguintes casos de teste e inclua a saída (imagem / número de alterações) em sua resposta. Farei uma tabela de classificação para cada caso de teste. Sua pontuação será a soma de cada classificação na tabela de classificação - quanto menor a pontuação, melhor. Aplicam-se brechas padrão. Não é permitido fazer o programa reconhecer esses casos de teste e executar um caso especial para eles. (Não é permitido pré-calcular e salvar os pixels centrais ideais para cada um desses casos de teste.) O programa deve funcionar para qualquer imagem.

Entre os melhores

Name        | Score | 1     - rk | 2     - rk | 3     - rk | 4     - rk | 5     - rk | 5     - rk | Total Changes
------------+-------+------------+------------+------------+------------+------------+------------+--------------
Maltysen    |    11 | 28688 -  2 | 24208 -  2 | 24248 -  1 |  7103 -  2 | 11097 -  2 | 13019 -  2 | 108363
TheBestOne  |     7 | 0     -  1 | 13698 -  1 | 24269 -  2 |   103 -  1 |  5344 -  1 |  4456 -  1 |  47867  

Java 8, 47.867 mudanças no total.

Usa a média da imagem como ponto central. Em seguida, atrai todos os raios possíveis para o centro e fornece o melhor raio para a cor. Em seguida, pinta todos os pontos inválidos em preto.

import javax.imageio.ImageIO;
import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.ArrayList;
import java.util.List;

public class MakeItStarry {

    private static final int RGB_RED = Color.RED.getRGB();
    static int[][] originalImage;

    static final int WHITE = 0;
    static final int BLACK = 1;
    static final int RGB_WHITE = Color.WHITE.getRGB();
    static final int RGB_BLACK = Color.BLACK.getRGB();
    static final int RGB_BLUE = Color.BLUE.getRGB();
    static final int RGB_YELLOW = Color.YELLOW.getRGB();

    public static void main(String[] args) throws Exception{
        originalImage = convert(ImageIO.read(new File(args[0])));
        Point center = findCenter(originalImage);
        int[][] nextImage = starry(originalImage, center);
        BufferedImage result = difference(originalImage, nextImage);
        result.setRGB(center.x, center.y, RGB_RED);
        String fileType;
        String fileName;
        if (args[1].split("\\.").length > 1){
            fileType = args[1].split("\\.")[1];
            fileName = args[1];
        } else {
            fileType = "PNG";
            fileName = args[1] + ".PNG";
        }
        ImageIO.write(result, fileType, new File(fileName));
        System.out.println(cost);
    }

    static int cost;

    private static BufferedImage difference(int[][] image1, int[][] image2) {
        cost = 0;
        int height = image1[0].length;
        int width = image1.length;
        BufferedImage result = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
        for (int x = 0; x < width; x++){
            for (int y = 0; y < width; y++){
                if (image1[x][y] == image2[x][y]){
                    if (image1[x][y] == WHITE){
                        result.setRGB(x, y, RGB_WHITE);
                    } else {
                        result.setRGB(x, y, RGB_BLACK);
                    }
                } else {
                    cost++;
                    if (image1[x][y] == WHITE){
                        result.setRGB(x, y, RGB_BLUE);
                    } else {
                        result.setRGB(x, y, RGB_YELLOW);
                    }
                }
            }
        }
        return result;
    }

    private static int[][] starry(int[][] image, Point center) {
        int width = image.length;
        int height = image[0].length;
        int[][] result = new int[width][height];
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                result[x][y] = BLACK;
            }
        }
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++) {
                Point endPoint = new Point(x, y, image);
                List<Point> line = Point.lineTo(center, endPoint, image);
                List<Point> newLine = starRay(line);
                newLine.stream().filter(point -> result[point.x][point.y] == BLACK).forEach(point -> {
                    result[point.x][point.y] = point.color;
                });
            }
        }
        int distance = 0;
        while (distance < height || distance < width){//This removes pixels that can't see the center.
            for (int x = Math.max(center.x - distance,0); x < center.x + distance && x < width; x++){
                for (int y = Math.max(center.y - distance, 0); y < center.y + distance && y < height; y++){
                    Point point = new Point(x, y, result);
                    if (Point.distance(center, point) != distance){
                        continue;
                    }
                    if (point.color == WHITE){
                        List<Point> line = Point.lineTo(center, point, result);
                        for (Point p : line){
                            if (p.color == BLACK){
                                point.color = BLACK;
                                break;
                            }
                        }
                        result[point.x][point.y] = point.color;
                    }
                }
            }//All white pixels can technically see the center but only if looking from the edge.
            distance++;
        }
        return result;
    }

    private static List<Point> starRay(List<Point> line) {
        int numOfWhites = 0;
        int farthestGoodPoint = 0;
        int blackCost = 0;
        int whiteCost = 0;
        for (int i = 0; i < line.size(); i++){
            if (line.get(i).color == WHITE){
                numOfWhites++;
                whiteCost++;
                if (numOfWhites + whiteCost > blackCost){
                    blackCost = 0;
                    whiteCost = 0;
                    farthestGoodPoint = i;
                }
            } else {
                blackCost++;
                numOfWhites = 0;
            }
        }
        List<Point> result = new ArrayList<>();
        for (int i = 0; i < line.size(); i++){
            Point p = line.get(i);
            if (i <= farthestGoodPoint){
                result.add(new Point(p.x, p.y, WHITE));
            } else {
                result.add(new Point(p.x, p.y, BLACK));
            }
        }
        return result;
    }

    private static Point findCenter(int[][] image) {
        double totalx = 0;
        double totaly = 0;
        int counter = 0;
        int width = image.length;
        int height = image[0].length;
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                if (image[x][y] == WHITE){
                    totalx += x;
                    totaly += y;
                    counter++;
                }
            }
        }
        return new Point((int)(totalx/counter), (int)(totaly/counter), image);
    }

    private static int[][] convert(BufferedImage image) {
        int width = image.getWidth();
        int height  = image.getHeight();
        int[][] result = new int[width][height];
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                if (image.getRGB(x, y) == RGB_WHITE){
                    result[x][y] = WHITE;
                } else {
                    result[x][y] = BLACK;
                }
            }
        }
        return result;
    }


    private static class Point {

        public int color;
        public int y;
        public int x;

        public Point(int x, int y, int[][] image) {
            this.x = x;
            this.y = y;
            this.color = image[x][y];
        }

        public Point(int x, int y, int color) {
            this.x = x;
            this.y = y;
            this.color = color;
        }

        public static List<Point> lineTo(Point point1, Point point2, int[][] image) {
            List<Point> result = new ArrayList<>();
            boolean reversed = false;
            if (point1.x > point2.x){
                Point buffer = point1;
                point1 = point2;
                point2 = buffer;
                reversed = !reversed;
            }
            int rise = point1.y - point2.y;
            int run = point1.x - point2.x;
            if (run == 0){
                if (point1.y > point2.y){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                int x = point1.x;
                for (int y = point1.y; y <= point2.y; y++){
                    result.add(new Point(x, y, image));
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
            if (rise == 0){
                if (point1.x > point2.x){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                int y = point1.y;
                for (int x = point1.x; x <= point2.x; x++){
                    result.add(new Point(x, y, image));
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
            int gcd = gcd(rise, run);
            rise /= gcd;
            run /= gcd;
            double slope = (rise + 0.0) / run;
            if (Math.abs(rise) >= Math.abs(run)){
                if (point1.y > point2.y){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                double x = point1.x;
                for (double y = point1.y + .5; y <= point2.y; y++){
                    int px = (int) Math.round(x);
                    if (Math.abs(Math.abs(px - x) - .5) < Math.abs(1.0 / (rise * 4))){
                        x += 1/slope;
                        continue;
                    }
                    result.add(new Point(px, (int) Math.round(y - .5), image));
                    result.add(new Point(px, (int) Math.round(y + .5), image));
                    x += 1/slope;
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            } else {
                if (point1.x > point2.x){
                    Point buffer = point1;
                    point1 = point2;
                    point2 = buffer;
                    reversed = !reversed;
                }
                double y = point1.y;
                for (double x = point1.x + .5; x <= point2.x; x++){
                    int py = (int) Math.round(y);
                    if (Math.abs(Math.abs(py - y) - .5) < Math.abs(1.0 / (run * 4))) {
                        y += slope;
                        continue;
                    }
                    result.add(new Point((int) Math.round(x - .5), py, image));
                    result.add(new Point((int) Math.round(x + .5), py, image));
                    y += slope;
                }
                if (reversed){
                    return reversed(result);
                }
                return result;
            }
        }

        private static List<Point> reversed(List<Point> points) {
            List<Point> result = new ArrayList<>();
            for (int i = points.size() - 1; i >= 0; i--){
                result.add(points.get(i));
            }
            return result;
        }

        private static int gcd(int num1, int num2) {
            if (num1 < 0 && num2 < 0){
                return -gcd(-num1, -num2);
            }
            if (num1 < 0){
                return gcd(-num1, num2);
            }
            if (num2 < 0){
                return gcd(num1, -num2);
            }
            if (num2 > num1){
                return gcd(num2, num1);
            }
            if (num2 == 0){
                return num1;
            }
            return gcd(num2, num1 % num2);
        }

        @Override
        public String toString(){
            return x + " " + y;
        }

        public static int distance(Point point1, Point point2) {
            return Math.abs(point1.x - point2.x) + Math.abs(point1.y - point2.y);
        }
    }
}

Resultados

Imagem 1 - 0 alterações, Imagem 2 - 13.698 alterações

Imagem 3 - 24.269 alterações, Imagem 4 - 103 alterações

Imagem 5 - 5.344 alterações, Imagem 6 - 4.456 alterações

Sem pixels inválidos removidos, 42.782 alterações no total

Pixels verdes são a primeira camada de pixels inválidos.

Imagem 1 - 0 alterações, Imagem 2- 9.889 alterações

Imagem 3 - 24.268 alterações, Imagem 4 - 103 alterações

Imagem 5 - 4.471 alterações, Imagem 6- 4.050 alterações

Todos os pixels brancos em todas as imagens podem ter uma linha desenhada para eles a partir do pixel central, se a linha não precisar se originar / terminar nos centros, mas em qualquer lugar do pixel.

args[0] contém o nome do arquivo de entrada.

args[1] contém o nome do arquivo de saída.

Imprime para o stdoutnúmero de alterações.

Python - PIL - 216.228 108.363 alterações no total

Whoo! Corte ao meio graças a @AJMansfield! Esse algoritmo ignora toda a preocupação com o cálculo de linhas e otimização e o que não. Apenas muda todos os brancos para preto, exceto um. Se não houver brancos, torna um preto um branco. Ele verifica se há mais brancos ou pretos e altera cada um do outro tipo, exceto um. Se não houver preto, ele faz (0, 0) o centro.

import Image
from itertools import product

img = Image.open(raw_input())
img = img.convert("RGB")

pixdata = img.load()
changed=0

m=False
count=0
for x, y in product(xrange(img.size[1]), xrange(img.size[0])):
    if pixdata[x, y]==(0, 0, 0):
        count+=1

colors=[(0, 0, 0), (255, 255, 0)] if img.size[0]*img.size[1]-count>count else [(255, 255, 255), (0, 0, 255)]
m=False
for x, y in product(xrange(img.size[1]), xrange(img.size[0])):
    if pixdata[x, y] == colors[0]:
        if m:
            pixdata[x, y] = colors[1]
        else:
            pixdata[x, y] = (255, 0, 0)
            m=True
        changed+=1

if not m:
    pixdata[0, 0]==(255, 0, 0)
    changed+=1
if colors[0]==(255, 255, 255):
    changed-=1

print changed
img.save("out.png", "PNG")

Resultados

Imagem 1 - 28688 alterações, Imagem 2 - 24208 alterações

Imagem 3 - 24248 alterações, Imagem 4 - 7103 alterações

Imagem 5 - 11097 alterações, Imagem 6 - 13019 alterações

Pega o nome do arquivo de raw_input e grava em out.png e imprime o número de alterações.