W tym konkursie musisz napisać program, który akceptuje czarno-biały obraz w pikselach i próbuje go zmienić, tak aby tworzył się biały kształt domenę gwiazdy , z jak najmniejszą liczbą zmian.

Dozwolone zmiany polegają na zamianie białych pikseli na czarne i zamianie czarnych pikseli na białe.

Wyjście musi ponownie składać się z tego samego obrazu, ale tym razem ze wszystkimi zmianami i oznaczonym środkiem /. Piksele, które zostały zmienione z białego na czarny, muszą być wyświetlane na niebiesko, te, które zostały zmienione z czarnego na biały, muszą być wyświetlane na żółto, a co najmniej jeden środkowy piksel musi być wyświetlony na czerwono. (Dokładne kolory zależą od Ciebie.) Program musi podać określony obraz, a także całkowitą liczbę wprowadzonych zmian.

Definicje

Domena gwiezdna

Zestaw białych pikseli obrazu reprezentuje domenę gwiazd, jeśli (i tylko wtedy) istnieje (przynajmniej) jeden środkowy piksel . Centrum pikseli jest jedną z białych pikseli, które mogą być conneced przez prostą do wszystkich innych białych pikseli tak, że linia przechodzi tylko białe piksele. (Dlatego środkowy piksel niekoniecznie jest unikalny).

Prosta linia między dwoma pikselami

Biorąc pod uwagę dwa piksele (początek i koniec, oba czerwone na ilustracji poniżej), linia prosta między dwoma pikselami składa się ze wszystkich pikseli, które dotykają linii (matematyczna, żółta na ilustracji poniżej), która prowadzi od środka pierwszego piksel do środka ostatniego piksela. Piksel nie dotyka linii, jeśli dotyka go tylko rogiem, więc aby piksel należał do linii piksela, linia (matematyczna, żółta) musi przecinać dany piksel o niezerowej długości. (Jeśli dotknie tylko punktu narożnego, uznaje się to za długość zero). Rozważ następujące przykłady:

Przykład

Pierwszy obraz powinien reprezentować przykładowe „wejście” testu, a dwa pozostałe obrazy przedstawiają dwa prawidłowe możliwe wyniki dla podanego przykładu:

Żółte obszary (wcześniej czarne) również liczą się do domeny „białej”, podczas gdy niebieskie obszary (wcześniej białe) liczą się do „czarnej” części poza domeną, a czerwona kropka za każdym razem reprezentuje jeden możliwy piksel środkowy.

Przypadki testowe

Następujące przypadki testowe to png o rozmiarze 256 x 256 pikseli.

Punktacja

Uruchom swój program z następującymi przypadkami testowymi i dołącz wynik (obraz / liczbę zmian) do swojej odpowiedzi. Zrobię tabelę wyników dla każdego przypadku testowego. Twój wynik będzie sumą każdego rankingu w tabeli liderów - im niższy wynik, tym lepiej. Obowiązują standardowe luki. Niedozwolone jest, aby program rozpoznał te przypadki testowe i uruchomił dla nich specjalne przypadki. (Niedozwolone jest wstępne obliczanie i zapisywanie optymalnych pikseli środkowych dla każdego z tych przypadków testowych.) Program powinien działać dla wszystkich obrazów.

Tabela liderów

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 zmian ogółem.

Wykorzystuje średnią obrazu jako punkt środkowy. Następnie przyciąga wszystkie możliwe promienie do środka i daje najlepszy promień koloru. Następnie koloruje wszystkie nieprawidłowe punkty na czarno.

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);
        }
    }
}

Wyniki

Zdjęcie 1 - 0 zmian, Zdjęcie 2 - 13 698 zmian

Zdjęcie 3 - 24 269 zmian, Zdjęcie 4 - 103 zmian

Zdjęcie 5 - 5 344 zmiany, Zdjęcie 6 - 4 456 zmian

Bez usuniętych nieprawidłowych pikseli, 42 782 zmian łącznie

Zielone piksele to pierwsza warstwa nieprawidłowych pikseli.

Zdjęcie 1 - 0 zmian, zdjęcie 2 - 9 889 zmian

Zdjęcie 3 - 24 268 zmian, Zdjęcie 4 - 103 zmian

Zdjęcie 5 - 4 471 zmian, Zdjęcie 6- 4 050 zmian

Wszystkie białe piksele na wszystkich zdjęciach mogą mieć linię rysowaną do nich od środkowego piksela, jeśli linia nie musi zaczynać się / kończyć w środkach, ale raczej w dowolnym miejscu piksela.

args[0] zawiera nazwę pliku wejściowego.

args[1] zawiera nazwę pliku wyjściowego.

Drukuje według stdoutliczby zmian.

Python - PIL - 216.228 228 363 zmian ogółem

Whoo! Przetnij go na pół dzięki @AJMansfield! Algorytm ten pomija wszystkie obawy związane z obliczaniem linii i optymalizacją. Po prostu zmienia wszystkie białe kolory na czarne oprócz jednego. Jeśli nie ma białych, sprawia, że ​​jeden jest biały i biały. Sprawdza, czy jest więcej białych lub czarnych i zmienia każdy inny z wyjątkiem jednego. Jeśli nie ma czerni, oznacza to (0, 0) środek.

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")

Wyniki

Zdjęcie 1 - 28688 zmian, Zdjęcie 2 - 24208 zmian

Zdjęcie 3 - 24248 zmian, Zdjęcie 4 - 7103 zmian

Zdjęcie 5 - 11097 zmian, Zdjęcie 6 - 13019 zmian

Pobiera nazwę pliku z raw_input i zapisuje do pliku out.png i wyświetla liczbę zmian.