Hilfe beim Aussortieren

[Rolf]

Hallo,

von einem umfangreichen Array werden viele Elemente entfernt.
Der Rest sieht dann z.B. wie folgt aus:

<?php  
$A = array(  
18 => '475,447',  
19 => '474,446',  
20 => '473,446',  
21 => '472,446',  
22 => '471,446',  
39 => '469,457',  
40 => '469,458',  
42 => '471,458');  
?>

Nun sollen die vereinzelten Werte eleminiert werden, so dass nur ein zusammenhängende Block übrigbleibt.
Der resultierende Block ist immer deutlich größer als alle anderen.
Bei diesem Beispiel also:

<?php  
$A = array(  
18 => '475,447',  
19 => '474,446',  
20 => '473,446',  
21 => '472,446',  
22 => '471,446');  
?>

Eine Besonderheit ist, dass ein Block auch über Anfang und Ende laufen kann,
so wie hier z.B.:

<?php  
$A = array(  
 0 => '472,459',  
 1 => '472,458',  
 2 => '473,458',  
41 => '470,458',  
42 => '471,458');  
?>

So ein Block kann 3, 4, 5, 6 oder 7 Elemente umfassen.
Mehr sind unwahrscheinlich.
Über die zur Auswahl notwendige Logik grübele ich schon den ganzen Tag.
Leider ohne Erfolg, so dass ich auf Eure Unterstützung hoffe ...

mbG Rolf

[ChrisB]

Hi,

von einem umfangreichen Array werden viele Elemente entfernt.
Der Rest sieht dann z.B. wie folgt aus:

<?php

$A = array(
18 => '475,447',
19 => '474,446',
20 => '473,446',
21 => '472,446',
22 => '471,446',
39 => '469,457',
40 => '469,458',
42 => '471,458');
?>

> Nun sollen die vereinzelten Werte eleminiert werden, so dass nur ein zusammenhängende Block übrigbleibt.  
> Der resultierende Block ist immer deutlich größer als alle anderen.  
> Bei diesem Beispiel also:  
> ~~~php

<?php  

> $A = array(  
> 18 => '475,447',  
> 19 => '474,446',  
> 20 => '473,446',  
> 21 => '472,446',  
> 22 => '471,446');  
> ?>

Mir ist nicht klar, wo da jetzt der "zusammenhaengende Block" vorliegt, bzw. was seinen Zusammenhang definiert.

Eine Besonderheit ist, dass ein Block auch über Anfang und Ende laufen kann,

Und das veranschaulicht mir auch nichts.

MfG ChrisB

[Rolf]

Hi Chris,

Mir ist nicht klar, wo da jetzt der "zusammenhaengende Block" vorliegt,
bzw. was seinen Zusammenhang definiert.

danke,
dass Du gefragt hast - mir war das klar ... ;-)

Der Zusammenhang ergibt sich aus einer fortlaufenden Indexierung.

Also im Beispiel 18-19-20-21-22 oder eben auch 41-42-0-1-2 sind die gesuchten Blöcke.
Die Values selbst sind unerheblich, wenn auch nicht unwichtig.

mbG Rolf

[ChrisB]

Hi,

Der Zusammenhang ergibt sich aus einer fortlaufenden Indexierung.

Also im Beispiel 18-19-20-21-22

OK, hier ist's klar.

oder eben auch 41-42-0-1-2 sind die gesuchten Blöcke.

Aber wie ist hier der Zusammenhang?
Du meinst, wenn man beim letzten nummerischen Index angelangt ist, und dann der (die) erste(n), wenn man wieder von vorne beginnt, 0 (, 1, 2) sind ...?

Also da faellt mir erst mal nichts besseres ein, als das ganze in einer Schleife zu durchlaufen, und zu schauen, wie lange man aufeinanderfolgende Indices vorfindet. Dabei die Laenge des laengsten (der wird ja gesucht, richtig?) bisher gefundenen zusammenhaengenden Blockes merken, sowie seinen "Startindex". Wenn nachfolgend noch ein laengerer auftritt, dann den bisherigen verwerfen, und den neuen merken ...

Der Sonderfall des "Ueberlaufs" waere dann nochmal gesondert zu beruecksichtigen.

MfG ChrisB

[ChrisB]

Hi,

Also da faellt mir erst mal nichts besseres ein, als das ganze in einer Schleife zu durchlaufen, und zu schauen, wie lange man aufeinanderfolgende Indices vorfindet. Dabei die Laenge des laengsten (der wird ja gesucht, richtig?) bisher gefundenen zusammenhaengenden Blockes merken, sowie seinen "Startindex". Wenn nachfolgend noch ein laengerer auftritt, dann den bisherigen verwerfen, und den neuen merken ...

So, hier mal ein Beispiel, basierend auf deinem ersten genannten Array, zu Testzwecken etwas erweitert:

$A = array(  
7 => 'a',  
9 => 'b',  
10 => 'c',  
11 => 'd',  
18 => '475,447',  
19 => '474,446',  
20 => '473,446',  
21 => '472,446',  
22 => '471,446',  
39 => '469,457',  
40 => '469,458',  
42 => '471,458');  
  
$actStart = $maxStart = $maxLength = 0;  
$actLength = 1;  
$prevIndex = -2; // muss fuer Vergleich kleiner als kleinster denkbarer Index (0) minus eins sein  
  
foreach($A as $index => $value) { // Schleife ueber Array-Elemente  
  if(!$actStart) { // aktuellen Startindex erstmalig auf ersten Index setzen; wichtig, wenn laengster Block direkt am Anfang des Arrays beginnt, dortiger Index aber nicht 0 ist  
    $actStart = $index;  
  }  
  if($prevIndex == $index-1) { // wenn aktueller Index direkter Nachfolger des vorherigen ist  
    $actLength++; // aktuelle Blocklaenge um eins erhoehen  
  }  
  else { // Indices sind nicht fortlaufend  
    if($actLength > $maxLength) { // neuer laengster Block gefunden  
      $maxLength = $actLength; // neue maximale Blocklaenge merken  
      $start = $actStart; // Startindex des neuen Blocks merken  
    }  
    $actLength = 1; // Laenge des neuen potentiellen Blocks initialiseren  
    $actStart = $index; // Startindex des neuen potentiellen Blocks ist aktueller Index  
  }  
  $prevIndex = $index; // Merker "vorheriger Index" fuer naechsten Durchlauf auf aktuellen Index setzen  
}  
  
echo 'longest block found beginning at index '.$start.', length '.$maxLength.' entries';

Gibt fuer das vorliegende Array aus:

longest block found beginning at index 18, length 5 entries

• ist doch das, was du in dem Fall haben wolltest, wenn ich dich jetzt nicht total missverstanden habe.

(Die Werte aus dem Array bekaeme man dann ueber eine anschliessende For-Schleife, die bei 18 beginnt und bis 18+5-1 laeuft - da liegen ja jetzt definitiv fortlaufende Indices vor, also tut's hier die simple For-Schleife.)

Der Sonderfall des "Ueberlaufs" waere dann nochmal gesondert zu beruecksichtigen.

Das hab' ich da jetzt noch nicht gemacht - your part :-)

MfG ChrisB

[Rolf]

Hallo Chris,

da das Ganze für Aussenstehende sehr verwirrend ist, hier eine reale Anwendung:

Um die nächste Koordinate des Flusses zu ermitteln, legt man, ausgehend von zwei bekannten Punkten mit dem Abstand R, einen Kreis über den Fluß. Punktweise ermittelt man die Farbwerte und erhält so die bekannten Arrayausschnitte(Bursts). Da die bekannten Punkte rot eingefärbt wurden, ist einer der beiden Bursts markiert. Der mittlere Punkt im anderen Burst, ist dann der nächste Punkt auf dem Weg des Flusslaufes.
Beispiel:

<?php  
$P = array(470,458);  // alter Mittelpunkt  
$M = array(472,452);  // aktueller Mittelpunkt  
$A = array(  
    13 => 471,458     // Burst 1  
    14 => 470,458Red  // Burst 1 - alte Koordinate  
    15 => 469,458     // Burst 1  
  
    30 => 471,446     // Burst 2  
    31 => 472,446     // Burst 2  
    32 => 473,446     // Burst 2  
    33 => 474,446     // Burst 2 - nächster Mittelpunkt  
    34 => 475,446     // Burst 2  
    35 => 475,447     // Burst 2  
)  
/* die Arraywerte als Impulsverlauf(String) */  
$R = '_____________#R#______________######_______';  
?>

Element eines Bursts sind Punkte, die ein reines Rot oder Cyan aufweisen.
Im nächsten Schritt ist der neu gefundene Punkt der Mittelpunkt des virtuellen Kreises.
Hoffe, das ist jetzt einleuchtender ...

mbG Rolf