From Daan
Jump to: navigation, search
(→‎PolygonConstellation)
(→‎Paintings)
 
(69 intermediate revisions by the same user not shown)
Line 1: Line 1:
  
−
This page is dedicated to the EVOSTAR'18 submission "Paintings, Polygons and Plant Propagation".
+
This page is dedicated to the EVOSTAR'19 publication "Paintings, Polygons and Plant Propagation".
  
  
Line 11: Line 11:
 
!Mona Lisa  
 
!Mona Lisa  
 
!Mondriaan
 
!Mondriaan
 +
!Klimt
 
!Bach
 
!Bach
 
|-  
 
|-  
−
|valign="top" |[[Image:180x240MonaLisa.png|frame|link=Protein Pow(d)er|Mona Lisa (1503) by Leonardo da Vinci]]
+
|valign="top" |[[Image:180x240MonaLisa.png|frame|Mona Lisa (1503) by Leonardo da Vinci.]]
−
|valign="top" |[[Image:180x240Mondriaan.png|frame|link=Amstelhaege|Composition with Red, Yellow and Blue (1930) by Piet Mondriaan.]]
+
|valign="top" |[[Image:180x240Mondriaan.png|frame|Composition with Red, Yellow and Blue (1930) by Piet Mondriaan.]]
−
|valign="top" |[[Image:180x240Klimt.png|frame|link=Chips & Circuits| Pipipipipi.]]
+
|valign="top" |[[Image:180x240Klimt.png|frame|The Kiss (1908) by Gustav Klimt.]]
−
|valign="top" |[[Image:180x240Bach.png|frame|link=Chips & Circuits| Portrait of Johann Sebastian Bach (1746) by Elias Gottlieb Haussman.]]
+
|valign="top" |[[Image:180x240Bach.png|frame|Portrait of Johann Sebastian Bach (1746) by Elias Gottlieb Haussman.]]
 
|}
 
|}
 
</Center>
 
</Center>
Line 26: Line 27:
 
!Starry Night  
 
!Starry Night  
 
|-  
 
|-  
−
|valign="top" |[[Image:240x180Dali.png|frame|link=Protein Pow(d)er|The Persistance of Memory (1931) by Salvador Dali]]
+
|valign="top" |[[Image:240x180StarryNight.png|frame|The Starry Night (1889) by Vincent Van Gogh.]]
−
|valign="top" |[[Image:240x180JacksonPollock.png|frame|link=Protein Pow(d)er|Convergence} (1952) by Jackson Pollock.]]
+
|valign="top" |[[Image:240x180JacksonPollock.png|frame|Convergence (1952) by Jackson Pollock.]]
−
|valign="top" |[[Image:240x180StarryNight.png|frame|link=Protein Pow(d)er|The Starry Night (1889) by Vincent Van Gogh.]]
+
|valign="top" |[[Image:240x180Dali.png|frame|The Persistence of Memory (1931) by Salvador Dali.]]
 
|}
 
|}
 
</Center>
 
</Center>
 +
 +
 +
 +
Painting provenance (recovered 31-9-2018):
 +
 +
 +
BACH: Wikipedia, Public Domain (https://en.wikipedia.org/wiki/Johann_Sebastian_Bach)
 +
 +
DALI: Wikiart, Fair Use (https://www.wikiart.org/en/salvador-dali/the-persistence-of-memory-1931)
 +
 +
MONA LISA: https://www.wikiart.org/en/leonardo-da-vinci/mona-lisa
 +
 +
MONDRIAAN: https://www.wikiart.org/en/piet-mondrian/composition-with-red-blue-and-yellow-1930
 +
 +
POLLOCK: https://www.wikiart.org/en/jackson-pollock/convergence-1952
 +
 +
STARRY NIGHT: https://www.wikiart.org/en/vincent-van-gogh/the-starry-night-1889
 +
 +
KLIMT:  https://www.wikiart.org/en/gustav-klimt/the-kiss-1908
 +
 +
 +
Get [http://heuristieken.nl/resources/PaauwVandenBerg_paintings.zip all the painting bitmaps] in one zip file.
  
 
==PolygonConstellation==
 
==PolygonConstellation==
−
!Mona Lisa
 
−
!Mondriaan
 
−
!Bach
 
−
|-
 
  
−
[bestPolygonConstellations]
+
These are the constellations from our last figure:
 +
 
 +
 
  
 
<Center>
 
<Center>
−
{| class="wikitable"
+
{|class="wikitable"| align="center" | style=" align="center"; text-align: center; margin-left: 1em; margin-bottom: 1em; font-size: 100%;"
 
|-
 
|-
−
|valign="top" colspan="3" |[[Image:180x240MonaLisa.png|frame|link=Protein Pow(d)er|Mona Lisa (1503) by Leonardo da Vinci]]
+
| colspan="3" |[[Image:180x240MonaLisaPoly.png|frame|Mona Lisa (1503) by Leonardo da Vinci. (Done with Simulated Annealing)]]
−
|valign="top" colspan="3" |[[Image:180x240Mondriaan.png|frame|link=Amstelhaege|Composition with Red, Yellow and Blue (1930) by Piet Mondriaan.]]
+
| colspan="3" |[[Image:180x240MondriaanPoly.png|frame|Composition with Red, Yellow and Blue (1930) by Piet Mondriaan. (Done with Hillclimber)]]
−
|valign="top" colspan="3" |[[Image:180x240Klimt.png|frame|link=Chips & Circuits| Pipipipipi.]]
+
| colspan="3" |[[Image:180x240KlimtPoly.png|frame|The Kiss (1908) by Gustav Klimt. (Done with Plant Propagation)]]
−
|valign="top" colspan="3" |[[Image:180x240Bach.png|frame|link=Chips & Circuits| Portrait of Johann Sebastian Bach (1746) by Elias Gottlieb Haussman.]]
+
| colspan="3" |[[Image:180x240BachPoly.png|frame|Portrait of Johann Sebastian Bach (1746) by Elias Gottlieb Haussman. (Done with Hillclimber)]]
 +
|}
 +
</Center>
 +
 
 +
<Center>
 +
{|class="wikitable"| align="center" | style=" align="center"; text-align: center; margin-left: 1em; margin-bottom: 1em; font-size: 100%;"
 
|-
 
|-
−
|valign="top" colspan="4" |[[Image:240x180Dali.png|frame|link=Protein Pow(d)er|The Persistance of Memory (1931) by Salvador Dali]]
+
| colspan="4" |[[Image:240x180StarryNightPoly.png|frame|The Starry Night (1889) by Vincent Van Gogh. (Done with Plant Propagation)]]
−
|valign="top" colspan="4" |[[Image:240x180JacksonPollock.png|frame|link=Protein Pow(d)er|Convergence} (1952) by Jackson Pollock.]]
+
| colspan="4" |[[Image:240x180JacksonPollockPoly.png|frame|Convergence (1952) by Jackson Pollock. (Simulated Annealing)]]
−
|valign="top" colspan="4" |[[Image:240x180StarryNight.png|frame|link=Protein Pow(d)er|The Starry Night (1889) by Vincent Van Gogh.]]
+
| colspan="4" |[[Image:240x180DaliPoly.png|frame|The Persistence of Memory (1931) by Salvador Dali. (Done with Hillclimber)]]
 
|}
 
|}
 
</Center>
 
</Center>
 +
 +
==New Paintings==
 +
 +
<Center>
 +
{| align="center" | style=" align="center"; text-align: center; margin-left: 1em; margin-bottom: 1em; font-size: 100%;"
 +
!Salvator
 +
!Lady Ermine
 +
|-
 +
|valign="top" |[[Image:180x240SalvatorMundi.png|frame|Salvator Mundi (1503) by Leonardo da Vinci.]]
 +
|valign="top" |[[Image:180x240LadyErmine.png|frame|Lady with an Ermine (1490) by Leonardo da Vinci.]]
 +
|}
 +
</Center>
 +
 +
==Resources & Media==
 +
 +
A [https://www.youtube.com/watch?v=u91gRGY8ElQ movie clip] of the algorithm at work.
 +
 +
 +
* [graph typicalruns][graph best end results][link to data records] ... available on request.
 +
 +
* Here's our [http://heuristieken.nl/resources/PaintingsFromPolygons.zip source code].
  
  
 +
==Errata==
  
−
[graph typicalruns]
+
* In equation (7), the factor (1−fi) should be just (fi). The typo is just in the paper, not in the source code, and therefore doesn't affect the results (see organisms.py, line 138).
  
 +
* In equation (9), the factor 9v/4 is incorrect; the experiments were done with 13v/5. The factor 1/nmax from the same formula was never in the experiment (see organisms.py, line 143). It is most likely a uncorrected textual remnant from an earlier probe. In general, we have been looking for a good way to transfer the PPA-algorithm to this problem, and many adaptations are possible.
  
−
[graph best end results]
 
  
 +
==Misc==
  
−
[link to source code]
+
* A simplified version of the problem was proven to be [http://heuristieken.nl/resources/(2020)VandenBerg-SimplifiedPaintingsfromPolygonsisNPHard.pdf NP-hard] in 2020.
  
  
−
[link to data records]
+
* We got simulated annealing to work in a [http://heuristieken.nl/resources/(2020)Dahmanietal-PFPSimulatedAnnealing.pdf paper] published at ICCC'20.

Latest revision as of 11:49, 7 June 2021

This page is dedicated to the EVOSTAR'19 publication "Paintings, Polygons and Plant Propagation".


Paintings

These are the target bitmaps used in our experimental runs.

Mona Lisa Mondriaan Klimt Bach
Mona Lisa (1503) by Leonardo da Vinci.
Composition with Red, Yellow and Blue (1930) by Piet Mondriaan.
The Kiss (1908) by Gustav Klimt.
Portrait of Johann Sebastian Bach (1746) by Elias Gottlieb Haussman.
Dali Jackson Pollock Starry Night
The Starry Night (1889) by Vincent Van Gogh.
Convergence (1952) by Jackson Pollock.
The Persistence of Memory (1931) by Salvador Dali.


Painting provenance (recovered 31-9-2018):


BACH: Wikipedia, Public Domain (https://en.wikipedia.org/wiki/Johann_Sebastian_Bach)

DALI: Wikiart, Fair Use (https://www.wikiart.org/en/salvador-dali/the-persistence-of-memory-1931)

MONA LISA: https://www.wikiart.org/en/leonardo-da-vinci/mona-lisa

MONDRIAAN: https://www.wikiart.org/en/piet-mondrian/composition-with-red-blue-and-yellow-1930

POLLOCK: https://www.wikiart.org/en/jackson-pollock/convergence-1952

STARRY NIGHT: https://www.wikiart.org/en/vincent-van-gogh/the-starry-night-1889

KLIMT: https://www.wikiart.org/en/gustav-klimt/the-kiss-1908


Get all the painting bitmaps in one zip file.

PolygonConstellation

These are the constellations from our last figure:


Mona Lisa (1503) by Leonardo da Vinci. (Done with Simulated Annealing)
Composition with Red, Yellow and Blue (1930) by Piet Mondriaan. (Done with Hillclimber)
The Kiss (1908) by Gustav Klimt. (Done with Plant Propagation)
Portrait of Johann Sebastian Bach (1746) by Elias Gottlieb Haussman. (Done with Hillclimber)
The Starry Night (1889) by Vincent Van Gogh. (Done with Plant Propagation)
Convergence (1952) by Jackson Pollock. (Simulated Annealing)
The Persistence of Memory (1931) by Salvador Dali. (Done with Hillclimber)

New Paintings

Salvator Lady Ermine
Salvator Mundi (1503) by Leonardo da Vinci.
Lady with an Ermine (1490) by Leonardo da Vinci.

Resources & Media

A movie clip of the algorithm at work.


  • [graph typicalruns][graph best end results][link to data records] ... available on request.


Errata

  • In equation (7), the factor (1−fi) should be just (fi). The typo is just in the paper, not in the source code, and therefore doesn't affect the results (see organisms.py, line 138).
  • In equation (9), the factor 9v/4 is incorrect; the experiments were done with 13v/5. The factor 1/nmax from the same formula was never in the experiment (see organisms.py, line 143). It is most likely a uncorrected textual remnant from an earlier probe. In general, we have been looking for a good way to transfer the PPA-algorithm to this problem, and many adaptations are possible.


Misc

  • A simplified version of the problem was proven to be NP-hard in 2020.


  • We got simulated annealing to work in a paper published at ICCC'20.
Retrieved from "http://heuristieken.nl/wiki/index.php?title=Paintings_from_Polygons&oldid=2859"