Regionen erkennen aus einer Matrix

[Peter666]

@Medium: Ja mich auch

Der HK Algorithmus sollte wie folgt aussehen:

Code:

var labels: array of integer = nil;
  n_labels: integer = 0; (* length of the labels array *)

(*  uf_find returns the canonical label for the equivalence class containing x *)

function uf_find(x: integer): integer;
var y, z: integer;
begin
  y := x;
  while (labels[y] <> y) do
    y := labels[y];

  while (labels[x] <> x) do
  begin
    z := labels[x];
    labels[x] := y;
    x := z;
  end;
  result := y;
end;

(*  uf_union joins two equivalence classes and returns the canonical label of the resulting class. *)

function uf_union(x, y: integer): Integer;
begin
  result := uf_find(y);
  labels[uf_find(x)] := result;
end;


(*  uf_make_set creates a new equivalence class and returns its label *)

function uf_make_set: integer;
begin
  inc(labels[0]);
  labels[labels[0]] := labels[0];
  result := labels[0];
end;

(*  uf_intitialize sets up the data structures needed by the union-find implementation. *)

procedure uf_initialize(max_labels: integer);
begin
  n_labels := max_labels;
  SetLength(labels, n_labels);
  labels[0] := 0;
end;

(*  uf_done frees the memory used by the union-find data structures *)

procedure uf_done;
begin
  n_labels := 0;
  setlength(labels, 0);
  labels := nil;
end;

(* End Union-Find implementation *)

function max(const a, b: integer): integer;
begin
  if a > b then result := a else result := b;
end;

function min(const a, b: integer): integer;
begin
  if a > b then result := b else result := a;
end;

type
  TMatrix = array of array of integer;

(* Label the clusters in "matrix".  Return the total number of clusters found. *)

function hoshen_kopelman(matrix: TMatrix; m, n: integer): integer;
var i, j: integer;
  up, left: integer;
  new_labels: array of integer;
  x: integer;
begin
  uf_initialize(m * n div 2);

  (* scan the matrix *)

  for i := 0 to m - 1 do
    for j := 0 to n - 1 do
      if (matrix[i][j] <> 0) then // if occupied ...
      begin
        if i = 0 then up := 0 else up := matrix[i - 1][j]; //  look up
        if j = 0 then left := 0 else left := matrix[i][j - 1]; //  look left

        case up + left of //switch (!!up + !!left) {
          0: matrix[i][j] := uf_make_set(); // a new cluster
          1: matrix[i][j] := max(up, left); // part of an existing cluster
                                            // whichever is nonzero is labelled
          2: matrix[i][j] := uf_union(up, left); // this site binds two clusters
        end;
      end;

  (* apply the relabeling to the matrix *)

  (* This is a little bit sneaky.. we create a mapping from the canonical labels
     determined by union/find into a new set of canonical labels, which are
     guaranteed to be sequential. *)

  Setlength(new_labels, n_labels); // allocate array, initialized to zero

  for i := 0 to m - 1 do
    for j := 0 to n - 1 do
      if (matrix[i][j] <> 0) then
      begin
        x := uf_find(matrix[i][j]);
        if (new_labels[x] = 0) then
        begin
          inc(new_labels[0]);
          new_labels[x] := new_labels[0];
        end;
        matrix[i][j] := new_labels[x];
      end;

  result := new_labels[0];

  setlength(new_labels, 0);
  uf_done();
end;

Was mir nen bisschen unbekannt vorkommt ist dieses Konstrukt:
switch (!!up + !!left)