In diesem Wettbewerb müssen Sie ein Programm schreiben, die eine Schwarz-Weiß - Pixelbild akzeptiert und versucht , sie zu verändern, so dass die weiße Form Formen Sterne Domain , mit so wenig Änderungen wie möglich.

Zulässige Änderungen sind das Umwandeln weißer in schwarze und das Umwandeln schwarzer in weiße Pixel.

Die Ausgabe muss wieder aus demselben Bild bestehen, diesmal jedoch mit allen Änderungen und einem / der markierten Mitte. Die Pixel, die von Weiß zu Schwarz geändert wurden, müssen in Blau angezeigt werden, diejenigen, die von Schwarz zu Weiß geändert wurden, müssen in Gelb angezeigt werden, und mindestens ein zentrales Pixel muss in Rot angezeigt werden. (Die genauen Farben bestimmen Sie.) Das Programm muss das angegebene Bild sowie die Gesamtzahl der vorgenommenen Änderungen ausgeben.

Definitionen

Star Domain

Die Menge der weißen Pixel des Bildes repräsentiert eine Sterndomäne, wenn (und nur wenn) es (mindestens) ein zentrales Pixel gibt . Das mittlere Pixel ist eines der weißen Pixel, die durch eine gerade Linie mit allen anderen weißen Pixeln verbunden werden können, so dass die Linie nur weiße Pixel durchläuft. (Das mittlere Pixel ist daher nicht unbedingt eindeutig.)

Gerade zwischen zwei Pixeln

Bei zwei Pixeln (Anfang und Ende, beide in der Abbildung unten rot) besteht die gerade Linie zwischen den beiden Pixeln aus allen Pixeln, die die (mathematisch, in der Abbildung unten gelb) Linie berühren, die von der Mitte der ersten Linie ausgeht Pixel in die Mitte des letzten Pixels. Ein Pixel wird nicht berührt die Linie , wenn sie nur durch eine Ecke berührt, so dass für ein Pixel zu dem gehört Pixelzeile des (mathematischen, gelb) , um die betreffenden Pixel mit einer Nicht - Null - Länge zu überqueren hat. (Wenn es nur den Eckpunkt berührt, wird dies als Länge Null betrachtet.) Betrachten Sie die folgenden Beispiele:

Beispiel

Das erste Bild sollte ein Beispiel für eine Testfall-Eingabe darstellen, und die beiden anderen Bilder sollten zwei gültige mögliche Ausgaben für das angegebene Beispiel darstellen:

Die gelben (ehemals schwarzen) Bereiche werden auch in die Domäne "Weiß" einbezogen, während die blauen (ehemals weißen) Bereiche in den "schwarzen" Teil außerhalb der Domäne einbezogen werden und der rote Punkt jedes Mal ein mögliches zentrales Pixel darstellt.

Testfälle

Die folgenden Testfälle sind PNGs mit einer Größe von jeweils 256 x 256 Pixel.

Wertung

Bitte führen Sie Ihr Programm mit den folgenden Testfällen aus und geben Sie die Ausgabe (Bild / Anzahl der Änderungen) in Ihre Antwort ein. Ich werde für jeden Testfall eine Rangliste erstellen. Ihre Punktzahl ist die Summe aller Ranglisten-Ranglisten. Je niedriger die Punktzahl, desto besser. Es gelten Standardlücken. Es ist nicht erlaubt, dass das Programm diese Testfälle erkennt und einen speziellen Fall für sie ausführt. (Es ist nicht gestattet, die optimalen mittleren Pixel für jeden dieser Testfälle vorab zu berechnen und zu speichern.) Das Programm sollte für alle Bilder funktionieren.

Bestenliste

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 Änderungen insgesamt.

Verwendet den Durchschnitt des Bildes als Mittelpunkt. Es zeichnet dann alle möglichen Strahlen in die Mitte und verleiht der Farbe den besten Radius. Es färbt dann alle ungültigen Punkte schwarz.

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

Ergebnisse

Bild 1 - 0 Änderungen, Bild 2 - 13.698 Änderungen

Bild 3 - 24.269 Änderungen, Bild 4 - 103 Änderungen

Bild 5 - 5.344 Änderungen, Bild 6 - 4.456 Änderungen

Wenn ungültige Pixel nicht entfernt werden, werden insgesamt 42.782 Änderungen vorgenommen

Grüne Pixel sind die erste Ebene ungültiger Pixel.

Bild 1 - 0 Änderungen, Bild 2- 9.889 Änderungen

Bild 3 - 24.268 Änderungen, Bild 4 - 103 Änderungen

Bild 5 - 4.471 Änderungen, Bild 6- 4.050 Änderungen

Alle weißen Pixel in allen Bildern können mit einer Linie vom mittleren Pixel gezeichnet werden, wenn die Linie nicht an der Mitte, sondern an einer beliebigen Stelle auf dem Pixel beginnen / enden muss.

args[0] Enthält den Namen der Eingabedatei.

args[1] Enthält den Namen der Ausgabedatei.

Druckt auf die stdoutAnzahl der Änderungen.

Python - PIL - 216.228 108.363 Änderungen insgesamt

Wer? Schneiden Sie es dank @AJMansfield in zwei Hälften! Dieser Algorithmus überspringt alle Sorgen um die Berechnung von Linien und die Optimierung und was nicht. Mit einer Ausnahme werden alle Weißtöne in Schwarz geändert. Wenn es keine Weißen gibt, macht es einen Schwarzen zu einem Weißen. Es prüft, ob es mehr Weiß- oder Schwarztöne gibt, und ändert jede einzelne der anderen Arten bis auf eine. Wenn es kein Schwarz gibt, wird (0, 0) zur Mitte.

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

Ergebnisse

Bild 1 - 28688 Änderungen, Bild 2 - 24208 Änderungen

Bild 3 - 24248 Änderungen, Bild 4 - 7103 Änderungen

Bild 5 - 11097 Änderungen, Bild 6 - 13019 Änderungen

Übernimmt den Dateinamen aus raw_input und schreibt in out.png und gibt die Anzahl der Änderungen aus.