Use in another project?

[Webreaper]

Hi there,

Love this project. I'm thinking about building something similar into my application (https://github.com/webreaper/Damselfly) to allow people to create a single composite JPEG etc from a selected set of images. If I were to copy your algo, would you mind?

Even better, do you have a .Net version of your library that I can use? 😄

[mendrik]

go ahead and copy, that's what OS is for :)
I used chatgpt to translate it to Elixir for https://albums.digital. It was pretty straightforward. Will probably work also for any other language.

[mendrik]

Btw. nice project you have there. So I thought if it's any help, here is the elixir code, too, if you want to throw rather that at the some AI, it's a bit more straight forward as Elixir has no generators and other gizmos (alas it's a bit simplified as I limit image count to less than 8 there):

defmodule ImageLayout do
  defmodule Dimension do
    use Ecto.Schema
    import Ecto.Changeset

    @type t :: %__MODULE__{
            width: pos_integer(),
            height: pos_integer()
          }

    @primary_key false
    embedded_schema do
      field :width, :float
      field :height, :float
    end

    def changeset(dimension, attrs) do
      cast(dimension, attrs, [:width, :height])
    end
  end

  defmodule Position do
    use Ecto.Schema
    import Ecto.Changeset

    @type t :: %__MODULE__{
            x: float,
            y: float
          }

    @primary_key false
    embedded_schema do
      field :x, :float
      field :y, :float
    end

    def changeset(position, attrs) do
      cast(position, attrs, [:x, :y])
    end
  end

  defmodule Picture do
    alias ImageLayout.Dimension

    @type t :: %__MODULE__{
            dimension: Dimension.t(),
            aspect_ratio: float,
            photo_id: non_neg_integer()
          }
    defstruct [:dimension, :aspect_ratio, :photo_id]
  end

  defmodule PositionedPicture do
    use Ecto.Schema
    import Ecto.Changeset
    alias ImageLayout.Dimension
    alias ImageLayout.Position

    @type t :: %__MODULE__{
            photo_id: non_neg_integer(),
            dimension: Dimension.t(),
            position: Position.t()
          }

    @primary_key false
    embedded_schema do
      embeds_one :position, Position, on_replace: :update
      embeds_one :dimension, Dimension, on_replace: :update
      belongs_to :photo, Album.Photo
    end

    def changeset(positioned_picture, attrs) do
      positioned_picture
      |> cast(attrs, [:photo_id])
      |> cast_embed(:position, with: &Position.changeset/2)
      |> cast_embed(:dimension, with: &Dimension.changeset/2)
    end
  end

  defmodule Solution do
    use Ecto.Schema
    import Ecto.Changeset
    alias ImageLayout.PositionedPicture
    alias ImageLayout.Dimension

    @page_aspect Application.compile_env!(:album, :page_aspect)

    require Logger

    @type t :: %__MODULE__{
            score: float,
            size_homogeneity: float,
            dimension: Dimension.t(),
            pictures: [PositionedPicture.t()]
          }

    @primary_key false
    embedded_schema do
      embeds_many :pictures, PositionedPicture, on_replace: :delete
      field :score, :float
      field :size_homogeneity, :float
      embeds_one :dimension, Dimension, on_replace: :update
    end

    def changeset(solution, attrs) do
      solution
      |> cast(attrs, [:score, :size_homogeneity])
      |> cast_embed(:pictures, with: &PositionedPicture.changeset/2)
      |> cast_embed(:dimension, with: &Dimension.changeset/2)
    end

    defp aspect_ratio(nil), do: 1.0

    defp aspect_ratio(solution),
      do: solution.dimension.width / solution.dimension.height / @page_aspect

    def style(solution) do
      aspect_ratio = aspect_ratio(solution)

      case aspect_ratio < 1 do
        true -> "width: #{trunc(aspect_ratio * 100)}%; height: 100%;"
        false -> "width: 100%; height: #{trunc(100 / aspect_ratio)}%;"
      end
    end
  end

  defmodule Composition do
    alias ImageLayout.Composition
    alias ImageLayout.Picture

    @type t :: %__MODULE__{
            horizontal: boolean(),
            first: Picture.t() | Composition.t(),
            second: Picture.t() | Composition.t(),
            aspect_ratio: number()
          }
    defstruct [:horizontal, :first, :second, :aspect_ratio]

    def new(horizontal, first, second) when horizontal == true do
      aspect_ratio = first.aspect_ratio + second.aspect_ratio

      %ImageLayout.Composition{
        horizontal: true,
        first: first,
        second: second,
        aspect_ratio: aspect_ratio
      }
    end

    def new(horizontal, first, second) when horizontal == false do
      aspect_ratio =
        first.aspect_ratio * second.aspect_ratio /
          (first.aspect_ratio + second.aspect_ratio)

      %ImageLayout.Composition{
        horizontal: false,
        first: first,
        second: second,
        aspect_ratio: aspect_ratio
      }
    end
  end

  defmodule Utils do
    def traverse(%Picture{}), do: []

    def traverse(%Composition{} = node) do
      [node | traverse(node.first) ++ traverse(node.second)]
    end

    @spec size_variation([Dimension.t()]) :: number()
    def size_variation(rects) do
      areas = Enum.map(rects, fn rect -> rect.width * rect.height end)
      min_area = Enum.min(areas)
      max_area = Enum.max(areas)

      min_area / max_area
    end

    @spec flip_count(Composition.t(), non_neg_integer()) :: non_neg_integer()
    def flip_count(root, pictures) do
      flip_count =
        traverse(root)
        |> Enum.reduce(0, fn node, acc ->
          if node.horizontal, do: acc + 1, else: acc
        end)

      half = (pictures - 1) / 2.0

      if half == 0, do: 0, else: max(1 - abs(half - flip_count) / half, 0)
    end
  end

  defmodule Positioning do
    import Utils
    alias ImageLayout.Composition
    alias ImageLayout.Picture
    alias ImageLayout.PositionedPicture

    @spec position_pictures(Position.t(), Dimension.t(), Picture.t() | Composition.t()) :: [
            PositionedPicture.t()
          ]
    @spec position_pictures(Position.t(), Dimension.t(), Composition.t()) :: [
            PositionedPicture.t()
          ]

    def position_pictures(position, dimension, %Picture{} = rect) do
      [%PositionedPicture{position: position, dimension: dimension, photo_id: rect.photo_id}]
    end

    def position_pictures(position, dimension, %Composition{horizontal: true} = rect) do
      length_horizontal = dimension.height * rect.first.aspect_ratio
      position_horizontal = %Position{position | x: position.x + length_horizontal}
      dimension_horizontal = %Dimension{dimension | width: length_horizontal}
      remaining_width = dimension.width - length_horizontal
      dimension2_horizontal = %Dimension{dimension | width: remaining_width}

      position_pictures(position, dimension_horizontal, rect.first) ++
        position_pictures(position_horizontal, dimension2_horizontal, rect.second)
    end

    def position_pictures(position, dimension, %Composition{horizontal: false} = rect) do
      length_vertical = dimension.width / rect.first.aspect_ratio
      position_vertical = %Position{position | y: position.y + length_vertical}
      dimension_vertical = %Dimension{dimension | height: length_vertical}
      remaining_height = dimension.height - length_vertical
      dimension2_vertical = %Dimension{dimension | height: remaining_height}

      position_pictures(position, dimension_vertical, rect.first) ++
        position_pictures(position_vertical, dimension2_vertical, rect.second)
    end
  end

  defmodule TreeComposition do
    alias ImageLayout.Composition

    @spec generate_tree_compositions([Picture.t()]) :: [Composition.t()]

    def generate_tree_compositions(pictures) when length(pictures) == 1 do
      [hd(pictures)]
    end

    def generate_tree_compositions(pictures) do
      1..(length(pictures) - 1)
      |> Enum.flat_map(fn i ->
        left_subtrees = generate_tree_compositions(Enum.slice(pictures, 0, i))
        right_subtrees = generate_tree_compositions(Enum.slice(pictures, i, length(pictures) - i))

        for left <- left_subtrees, right <- right_subtrees, horizontal <- [true, false] do
          Composition.new(horizontal, left, right)
        end
      end)
    end
  end

  defmodule SolutionGeneration do
    require Logger
    import Utils, only: [size_variation: 1, flip_count: 2]
    import TreeComposition, only: [generate_tree_compositions: 1]
    import Positioning, only: [position_pictures: 3]
    alias ImageLayout.Picture
    alias ImageLayout.Solution
    alias ImageLayout.Dimension

    @score_subset 10

    @spec find_solution!([Picture.t()], Dimension.t()) :: Solution.t()
    @spec find_best_solution([Solution.t()]) :: Solution.t() | nil
    @spec resize_dimension(Dimension.t(), number()) :: Dimension.t()
    @spec size_solution(Dimension.t(), number(), Composition.t()) :: Solution.t()

    @spec find_solution!([ImageLayout.Picture.t()], ImageLayout.Dimension.t()) ::
            ImageLayout.Solution.t()
    def find_solution!(pictures, target_dimension) do
      ar_target = target_dimension.width / target_dimension.height
      compositions = generate_tree_compositions(pictures)

      Logger.info("processing #{length(compositions)} compositions...")

      picture_count = length(pictures)

      result =
        Enum.reduce(compositions, [], fn root, acc ->
          distance = abs(root.aspect_ratio - ar_target)
          score = 1 / (1 + distance)
          flips = flip_count(root, picture_count)

          if picture_count >= 6 && flips <= 0.5 do
            acc
          else
            actual_dimensions = resize_dimension(target_dimension, root.aspect_ratio)
            solution = size_solution(actual_dimensions, score, root)
            [solution | acc]
          end
        end)

      case find_best_solution(result) do
        nil -> raise "No solution found"
        solution -> solution
      end
    end

    defp find_best_solution(solutions) do
      solutions
      |> Enum.sort_by(&(&1.score * &1.score * &1.size_homogeneity))
      |> Enum.take(-@score_subset)
      |> Enum.sort_by(& &1.score)
      |> List.last()
    end

    defp size_solution(dimension, score, composition) do
      pictures = position_pictures(%Position{x: 0, y: 0}, dimension, composition)
      size_homogeneity = size_variation(Enum.map(pictures, fn p -> p.dimension end))

      %Solution{
        dimension: dimension,
        score: score,
        size_homogeneity: size_homogeneity,
        pictures: pictures
      }
    end

    defp resize_dimension(dimension, aspect_ratio) do
      new_width = dimension.height * aspect_ratio

      if new_width <= dimension.width do
        %Dimension{dimension | width: new_width}
      else
        new_height = dimension.width / aspect_ratio
        %Dimension{dimension | height: new_height}
      end
    end
  end
end

[Webreaper]

Thanks, I'll take a look at converting. I think TS is so close to C# that translating it will probably be trivial.

I'll let you know how I get on!