Rekursion: Überlappung vermeiden (Processing)

[receivingwisdom]

Hallo allerseits,

im beiliegendem PDF ist die Aufgabenstellung formuliert. Ich komme leider auf keine effiziente Idee wie ich die Überlappung vermeide. Die einzige Methode auf die ich gekommen bin, wäre es für jedes einzelne Viereck, welches ein Viereck zwei Rekursionsstufen vorher überlappt, gesondert eine Bedingung zu schreiben. Die Aufgabe auf diese Art und Weise zu lösen würde ja aber hunderte Bedingungen erfordern. Bin sehr dankbar für jede Hilfe.

final float SQUARE_LENGTH = 300;
int maxRecursionDepth = 6;
int currentRecursionDepth = 0;
float offsetX;
float offsetY;


void setup() {
  size(720, 720);
  offsetX = width/2 - SQUARE_LENGTH/2; // 210
  offsetY = height/2 - SQUARE_LENGTH/2;
}


void draw() {
  background(255);
  recursiveSquare(offsetX, offsetY, SQUARE_LENGTH, 0);

  fill(0);
  textSize(25);
  text("Current recursion depth: " + currentRecursionDepth, 10, 25);
  fill(255);
}


void recursiveSquare(float x, float y, float l, int depth) {
  if (depth == currentRecursionDepth) {

    // Gibt Farbe für Vierecke der letzten Rekursionsstufe
    if (depth == 0) {
      fill (150, 200, 0);
    } else if (depth == 1) {
      fill (0, 100, 200);
    } else if (depth == 2) {
      fill (200, 200, 0);
    } else if (depth == 3) {
      fill (200, 0, 200);
    } else if (depth == 4) {
      fill (0, 200, 200);
    } else if (depth == 5) {
      fill (50);
    } else if (depth == 6) {
      fill (200, 100, 0);
    }


    drawSquare(x, y, l);

    fill (255);
  } else if (currentRecursionDepth <= maxRecursionDepth) {

    float x1 = x - l/4;
    float y1 = y - l/4;

    float x2 = x + 3 * l/4;
    float y2 = y + 3 * l/4;


    // Geben Farben für Vierecke aller Rekursionsstufen bis auf letzte Rekursionsstufe.
    if (depth == 0) {
      fill (150, 200, 0);
    }

    if (depth == 1) {
      fill(0, 100, 200);
    }

    if (depth == 2) {
      fill (200, 200, 0);
    }

    if (depth == 3) {
      fill (200, 0, 200);
    }

    if (depth == 4) {
      fill (0, 200, 200);
    }

    if (depth == 5) {
      fill (50);
    }

    drawSquare(x, y, l);
    fill (255);


    recursiveSquare(x1, y1, l/2, depth + 1);
    recursiveSquare(x2, y1, l/2, depth + 1);
    recursiveSquare(x1, y2, l/2, depth + 1);
    recursiveSquare(x2, y2, l/2, depth + 1);
         

    }
  }


  void drawSquare(float x, float y, float l) {
    rect(x, y, l, l);
  }


void mouseClicked() {
  if (mouseButton == LEFT && currentRecursionDepth < maxRecursionDepth) {
    currentRecursionDepth++;
  } else if (mouseButton == RIGHT && currentRecursionDepth > 0) {
    currentRecursionDepth--;
  }
}

 

[mihe7]

Die Aufgabe auf diese Art und Weise zu lösen würde ja aber hunderte Bedingungen erfordern.

Warum? Wenn Du Dir das Bild ansiehst, ist doch ein Muster erkennbar: das Quadrat, das ich in eine Ecke platziere, zeichnet in der gegenüberliegenden Ecke selbst kein Quadrat.

Platziere ich ein blaues Quadrat in die obere linke Ecke des roten Quadrats, findet man kein grünes Quadrat in der unteren rechten Ecke des blauen Quadrats. Platziere ich ein blaues Quadrat in die obere rechte Ecke des roten Quadrats, findet man kein grünes Quadrat in der unteren linken Ecke des blauen Quadrats usw.

Das gelbe Quadrat, das ganz oben links zu sehen ist, würde kein Quadrat unten rechts enthalten.

 

[KonradN]

Um die Gedanken nur etwas zu vertiefen: Es muss also bekannt sein, in welche Richtung man gegangen ist. Wenn man also nach oben rechts gegangen ist, dann muss man im folgenden nur oben rechts, oben links und unten rechts die folge-Quadrate malen.

Diese Information kann man entweder mitgeben (Dann hast Du ein weiteren Parameter) oder man kann es aus den x/y Werten ableiten so man den Startpunkt und das Vorgehen kennt. Ich würde den zusätzlichen Parameter bevorzugen, da schlicht einfacher und schneller. Aber das Berechnen kann auch schon sehr interessant sein

Du kannst also einfach bei den 4 Aufrufen vorab prüfen, ob es gemalt werden soll. Es gibt 4 Richtungen und bei dreien muss gemalt werden - daher ist es einfacher, das negative zu formulieren, also wenn aktuell nicht unten rechts gemacht wird, dann male das neue Quadrat oben links.

Und statt der vielen if: Da ist ein switch deutlich besser denke ich mal.
Und wenn ich das auf die Schnelle richtig gesehen habe, dann hast Du da doppelten Code. Du malst ja immer das Rechteck (unabhängig von der äußeren if Bedingung) und nur der rekursive Aufruf erfolgt, wenn eine bestimmte Bedingung erfüllt ist.
Und die Bedingung ist etwas dubios - Du hast da zwei Rekursionstiefen. Die maximale Rekursionstiefe ist doch eigentlich nur das maximum, das der User einstellen kann. Das ist aber hier doch egal. Das ist ein UI Thema. Es gibt eine eingestellte Rekursionstiefe (current) und die solltest Du in dem Algorithmus einfach nutzen.

Wenn man da sichergehen will, dass da kein Unsinn kommt, dann prüfst man maximal, dass da wirklich kein falscher Wert ist, d.h. etwas wie
if (currentRecursionDepth < 0 || currentRecursionDepth > maxRecursionDepth) throw new IllegalStateException("currentRecursionDepth has invalid value!");

Das einfach mal von meiner Seite als Input.