Footprint-Suchalgorithmus

Wenn die Lösungsmenge eine Vereinigung von Scheiben mit gegebenem Radius sein muss, würde ich einen gierigen Ansatz versuchen. (Ich vermute, dass das Problem unlösbar sein könnte - exponentielle Laufzeit - wenn Sie eine genaue Lösung wünschen.)

Berechnen Sie für alle Pixel (Ihre "Blöcke") die Summe der Werte auf der umgebenden Platte und nehmen Sie die mit der höchsten Summe. Markieren Sie dieses Pixel und passen Sie die Summe aller Pixel auf seiner Festplatte an, indem Sie dessen Wert ableiten, da das markierte Pixel "verbraucht" wurde. Dann scannen Sie alle Pixel, die mit ihm in Berührung kommen, durch eine Kante oder eine Ecke und markieren Sie das Pixel mit der höchsten Summe.

Fahren Sie fort, bis alle Summen negativ sind. Dann kann die Summe nicht mehr steigen.

Für eine effiziente Implementierung müssen Sie eine Liste der Randpixel behalten, d. h. die nicht markierten Pixel, die Nachbarn eines markierten Pixels sind. Nachdem Sie das Rahmenpixel mit der größten Summe ausgewählt und markiert haben, entfernen Sie es aus der Liste und berechnen die Summen für die nicht markierten Pixel auf der Festplatte neu. Sie fügen auch die unmarkierten Pixel hinzu, die sie berühren.

Auf dem Bild sind die Pixel blau und die Randpixel grün markiert. Die hervorgehobenen Pixel sind

• derjenige, der markiert wird,
• diejenigen, für die die Summe neu berechnet werden muss.

Die Rechenzeit ist proportional zum Bildbereich multipliziert mit der Fläche einer Platte (für die anfängliche Berechnung der Summen) plus der Fläche der Form mal der Fläche einer Platte (für die Aktualisierung der Summen) ), plus die Summe der Längen der aufeinanderfolgenden Perimeter der Form, während sie wächst (um die größte Summe zu finden). [Da die letztgenannten Begriffe teuer sein können - in der Größenordnung des Produkts der Fläche der Form durch ihre Umfangslänge - ist es ratsam, eine Heap Datenstruktur zu verwenden, die die Summe von die Längen zur Summe ihres Logarithmus.]

Grafischer Ansatz

Ich würde das grafisch angehen. Meine Intuition sagt mir, dass die inneren Punkte vollständig innerhalb der gegossenen Kreise mit einem minimalen Radius r von allen Footprint-Punkten in der Nähe sind. Das bedeutet, wenn Sie einen Kreis von jedem Footprint-Punkt mit dem Radius r werfen, befinden sich alle Punkte, die sich innerhalb mindestens der Hälfte aller benachbarten Kreise befinden, innerhalb Ihres Polygons. Um weniger vage zu sein, wenn Sie tief innerhalb des Polygons sind, dann haben Sie Pi*r^2 solcher überlappenden Kreise bei jedem Pixel. wenn du am Rande bist, hast du die Hälfte davon. Dies ist leicht berechenbar.

Zuerst brauche ich den Datensatz. Wie Sie nur jpg Datei zur Verfügung stellen, habe ich nicht die vales nur die Handlung. Also behandle ich dieses Problem wie ein Binärbild. Zuerst musste ich das Bild neu einfärben, um jpg Farbverzerrungen zu entfernen. Danach ist dies meine Eingabe:

Ich wähle schwarzen Hintergrund, um additive Mathe einfach auf Bild anzuwenden, und ich mag es auch mehr als weiß und lasse den Fußabdruck rot (maximal gesättigt). Jetzt der Algorithmus:

1. Temporäres Bild erstellen

   Es sollte die gleiche Größe haben und auf Schwarz (color=0) gelöscht werden. Behandle seine Pixel wie ganzzahlige Zähler überlappender Kreise.

2. Darstellerkreise

   für jedes rote Pixel in source image add +1 für jedes Pixel innerhalb des Kreises mit minimalem Radius r um dasselbe Pixel, aber in temp image . Das Ergebnis ist wie folgt (Blau sind die unteren Bits von pixelformat ):

   

   As r Ich habe r=24 verwendet, da dies der untere linke Kreisradius in Ihrem Beispiel +/- Pixel ist.

3. Nur Innenpixel auswählen

   so färben Sie das Temp-Bild ein. Alle Pixel mit color < 0.5*pi*r^2 recolor auf schwarz und der Rest auf rot . Das Ergebnis ist wie folgt:

   

4. nur Polygonumfangspunkte auswählen

   Fassen Sie einfach alle roten Pixel in der Nähe von schwarzen Pixeln in eine neutrale Farbe blau und den Rest in schwarz um. Ergebnis:

   

   Nun poliere einfach das Ergebnis. Um mit dem Eingabebild zu vergleichen, können Sie beide kombinieren (I OR sie zusammen):

   

[Hinweise]

Sie können mit dem Radius min oder der Eigenschaft treshold schweben, um ein anderes Verhalten zu erzielen. Aber ich denke, das passt ziemlich gut zu deinem Problem.

Hier ein paar C ++ Quellcode dafür:

Ich verwende meine eigene picture -Klasse für Bilder, daher sind einige Mitglieder:

• xs,ys Größe des Bildes in Pixeln
• p[y][x].dd ist pixel at (x,y) position als 32 bit integer type
• clear(color) - löscht das gesamte Bild
• resize(xs,ys) - passt das Bild an die neue Auflösung an

[Edit1] Ich habe einen kleinen Fehler im Quellcode

Ich bemerkte, dass einige Kanten zu scharf waren, also überprüfte ich den Code und ich vergaß, während des Füllens die Kreisbedingung hinzuzufügen, sodass stattdessen Quadrate gefüllt wurden. Ich habe den obigen Quellcode repariert. Ich habe nur die Zeile if ((xx*xx)+(yy*yy)<=r*r) hinzugefügt. Die Ergebnisse sind leicht verändert, also habe ich auch die Bilder mit neuen Ergebnissen aktualisiert

Ich habe mit dem Innenflächenkoeffizienten-Verhältnis gespielt und dieses:

Führt zu noch besserer Übereinstimmung für Sie. Je kleiner es ist, desto mehr kann das Polygon die äußere Grundfläche überlappen. Ergebnis: