DEV Community

Play Button Pause Button
Daniel Dominguez
Daniel Dominguez

Posted on

Using a greedy randomized algorithm to create art

The greedy randomized adaptive search procedure (also known as GRASP) is a metaheuristic algorithm commonly applied to combinatorial optimization problems in which each iteration consists basically of two phases: construction and local search. The construction phase builds a feasible solution, whose neighborhood is investigated until a local minimum is found during the local search phase.

First, the darkest pixel is found. Then a number of random lines are drawn through that point, and the pixel values along each line are added together. The line with the darkest average is chosen, and the value of that line is subtracted from the image. Then the whole process is started over again for however many lines we are drawing.

By the nature of the algorithm, the optimal line drawing configuration is probably not achieved, but performance is far superior to the naive method of checking every line.

Discussion (0)