[PHP] Array Groeperen

[Av-]

Hey mensen,

ik heb een array met x/y-coordinaten die stipjes projecteerd op een image.
Als de coordinaten te dicht bij elkaar liggen, vallen de stipjes over elkaar heen.

Nu wil ik deze coordinaten die dicht bijelkaar liggen groeperen in 1 array key.

Ik heb al dagen lang lopen puzzelen, maar kom er niet uit.

Dit is mijn Array

code:

Array
(
    [0] => Array
        (
            [y_coord] => 95
            [x_coord] => 87
        )

    [1] => Array
        (
            [y_coord] => 86
            [x_coord] => 43
        )

    [2] => Array
        (
            [y_coord] => 127
            [x_coord] => 59
        )

    [3] => Array
        (
            [y_coord] => 54
            [x_coord] => 51
        )

    [4] => Array
        (
            [y_coord] => 163
            [x_coord] => 129
        )

    [5] => Array
        (
            [y_coord] => 118
            [x_coord] => 102
        )

    [6] => Array
        (
            [y_coord] => 129
            [x_coord] => 55
        )

    [7] => Array
        (
            [y_coord] => 99
            [x_coord] => 43
        )

    [8] => Array
        (
            [y_coord] => 87
            [x_coord] => 54
        )

    [9] => Array
        (
            [y_coord] => 160
            [x_coord] => 149
        )

    [10] => Array
        (
            [y_coord] => 151
            [x_coord] => 145
        )

    [11] => Array
        (
            [y_coord] => 35
            [x_coord] => 14
        )

    [12] => Array
        (
            [y_coord] => 126
            [x_coord] => 90
        )

    [13] => Array
        (
            [y_coord] => 106
            [x_coord] => 75
        )

    [14] => Array
        (
            [y_coord] => 127
            [x_coord] => 59
        )

    [15] => Array
        (
            [y_coord] => 3
            [x_coord] => 104
        )

    [16] => Array
        (
            [y_coord] => 7
            [x_coord] => 99
        )

    [17] => Array
        (
            [y_coord] => 83
            [x_coord] => 79
        )

    [18] => Array
        (
            [y_coord] => 117
            [x_coord] => 85
        )

    [19] => Array
        (
            [y_coord] => 31
            [x_coord] => 102
        )

    [20] => Array
        (
            [y_coord] => 44
            [x_coord] => 3
        )

    [21] => Array
        (
            [y_coord] => 94
            [x_coord] => 79
        )

    [22] => Array
        (
            [y_coord] => 111
            [x_coord] => 93
        )

    [23] => Array
        (
            [y_coord] => 50
            [x_coord] => 67
        )

    [24] => Array
        (
            [y_coord] => 107
            [x_coord] => 97
        )

    [25] => Array
        (
            [y_coord] => 108
            [x_coord] => 59
        )

    [26] => Array
        (
            [y_coord] => 129
            [x_coord] => 132
        )

    [27] => Array
        (
            [y_coord] => 163
            [x_coord] => 106
        )

    [28] => Array
        (
            [y_coord] => 141
            [x_coord] => 106
        )

    [29] => Array
        (
            [y_coord] => 96
            [x_coord] => 59
        )

    [30] => Array
        (
            [y_coord] => 88
            [x_coord] => 121
        )

    [31] => Array
        (
            [y_coord] => 42
            [x_coord] => 35
        )

    [32] => Array
        (
            [y_coord] => 71
            [x_coord] => 43
        )

    [33] => Array
        (
            [y_coord] => 128
            [x_coord] => 65
        )

    [34] => Array
        (
            [y_coord] => 96
            [x_coord] => 81
        )

)

Bijvoorbeeld de 24e en 31e key zitten erg dicht bij elkaar, deze keys zou ik dus willlen grouperen, zodat ik een kortere array terugkrijg, waar ze zijn gegroupeerd.

Bijvoorbaad heeeeel veel dank..

Greetz

[Janoz]

Wat bedoel je met groeperen? Wil je 1 van beiden weghalen?

Laat eens een array zien van de gewenste situatie (je kunt je beperken tot een stuk of 5 punten, 35 lijkt me een beetje overdreven en onoverzichtelijk)?

[r0bert]

Gebruik een Array voor de x_coord en een array voor de y_coord. Ga dan bij iedere stip even checken van de huidige coordinaat wat er in de buurt ligt, bijv met een max van 2 pixels (?) Dan krijg je dus een mooi gebiedje met x_coor en y_coor waar overlappende in zullen vallen. Hoop dat je het idee snapt? Kun je daar wat mee?

[fleppuhstein]

Als je op het moment dat je een coordinaat tekent op je image, eerst kijkt of er geen coordinaat in de buurt is, zoja vervalt hij, zo nee dan kan je hem erbij plaatsen op de kaart.

Je zou ook eens kunnen denken aan een object array, ipv een twee dimensionale array.

[ Voor 19% gewijzigd door fleppuhstein op 05-09-2007 16:50 ]

[Johnny]

Ten eerste, volgens mij liggen 107x97 en 42x35 helemaal niet dicht bij elkaar, als je de dingen gaat groeperen krijg je niet minder data, alleen zijn je gegevens op een andere manier gestorteerd.

De enige manier om dit te doen is door voor item de hele array doorlopen en kijken of de waardes binnen een bepaald bereik liggen, en als dat zo is het item er uit gooien, dan krijg je een kortere array.

[Cartman!]

Wat heb je al geprobeerd dan? Hoe verwacht je dat het er uit komt te zien als het klaar is?
Er wordt verwacht hier dat je duidelijk verteld wat je probeert en waar je niet uitkomt ipv: dit wil ik en het werkt niet.

edit: eerst reactie posten, dan naar de wc...

[ Voor 10% gewijzigd door Cartman! op 05-09-2007 16:57 ]

[Av-]

Sorry, ik bedoelde key 34, 21 (ipv 24 en 31)

De logica die hier boven wordt geopperd snap ik ook. Wat ik zelf had geprobeerd is de array door te loopen en deze te vergelijken met een tweede array die zichzelf opbouwt aan de hand van of de key in de range valt, het is moeilijk uit te leggen, maar zowiezo vond de server dat niet echt leuk, omdat het toch wel een heel aantal loops vereist.

We gaan kijken of we iets met de bovenstaande suggesties kunnen. Extra suggesties altijd welkom

tnx

[MrOizo2005]

code:

    function array_sort($array, $key)
    {
       foreach ($array as $i => $k) {
            $sort_values[$i] = $array[$i][$key];
       }
       asort ($sort_values);
       reset ($sort_values);
       while (list ($arr_key, $arr_val) = each ($sort_values)) {
              $sorted_arr[] = $array[$arr_key];
       }
       return $sorted_arr;
    }   
    
    $bla = array_sort($array,'x_coord');

Nu sorteert hij ASC op de x_coord


edit: doh denk niet dat dit helemaal de TS zijn bedoeling is. naja snel lezen onder werk tijd is geen goed plan....

[ Voor 12% gewijzigd door MrOizo2005 op 05-09-2007 17:04 ]

[Av-]

Toch bedankt, je hebt me wel op een ander idee gebracht.

[ATS]

Ja, de eerste stap is sorteren. Daarna loop je de array door en kijk je of
|x(n) - x(n+1)| < delta. Als dat het geval is dan kijk of dat ook geldt voor |y(n) - y(n+1)| < delta. Delta kies je afhankelijk van wat je "dicht bij elkaar" vindt. Als beide gelden, dan pas je ze aan (voeg je ze samen met een gemiddelde waarde ofzo?)

Als je dit soort dingen veel vaak moet doen, of op grote datasets, dan zijn er trouwens veel efficiëntere datastructuren dan wat je nu hebt.

[Verwijderd]

Ik neem aan dat die array uit een database komt.
Kun je zoiets ook niet meteen met een query of 2 uit een database halen?

[Janoz]

Let er trouwens wel op dat je vreemde resultaten kunt krijgen afhankelijk van de volgorde van de punten. Wanneer de punten op een lijn liggen en per twee liggen ze wel te dicht bij elkaar volgens je criterium, dan kan zo de hele lijn worden gereduceerd tot 1 punt (mits de lijn in een richting doorwandeld wordt). Ik neem niet aan dat dat de bedoeling is.

[Voutloos]

Tja, dan moet je elke keer met de nieuw gefilterde array vergelijken. Punt 1 keur je goed, punt 2 ligt te dichtbij en komt er niet in, punt 3 ligt bijvoorbeeld voldoende ver van punt 1 en mag er wel in.

[Janoz]

Het telkens opnieuw gebruiken van de gefilterde array zorgt juist voor dit probleem. Even een voorbeeld in 1D:
punten: 2, 4, 6, 8

Alles met buren dichter dan 3 komen samen.

Met eerste punt bewaren levert dit:
2, 6
Met laatste punt bewaren levert dit
8
Met gemiddelde bewaren levert dit
3,7

Nu hebben we de volgende punten: 8, 2, 6 ,4

Met eerste punt bewaren levert dit:
8, 2, 6
Met laatste punt bewaren levert dit
8, 2, 4
Met gemiddelde bewaren levert dit
8, 2, 5

Zelfde punten, zelfde keuzes, maar andere volgorde geeft ander resultaat.

[Verwijderd]

even brainen, ik weet overigens niet hoe je het in php neer zou moeten zetten, maar dat kunnen anderen wellicht wel.:

1. je sorteert op X-coordinaat en subsortering op Y
2. je loopt door de array en kijkt of de volgende waarde binnen de array in de 'dichtbij'-range valt.
3. Als dat het geval is, kijk je ook of de Y-coordinaat in de 'dichtbij'-range valt.
4. Dit doe je totdat je een waarde vindt die niet meer 'dichtbij' is.
5. Dan kopieer je het deel van de orginele array dat in de 'dichtbij'-range viel, als een enkele node naar een nieuwe array (array 2)
6. De volgende waarde in de array (die net niet meer in de 'dichtbij'-range viel) neem je als beginpunt voor een nieuwe check. (stap 2 tot 6 dus steeds herhalen)

Voorbeeld:
1,1
1,2
1,3
2,1
2,2
2,3

Dus als de 'dichtbij'-range een waarde van 1 heeft krijg je het volgende:
1,1 kijken naar volgende 1,2 (true, true)
1,2 kijken naar volgende 1,3 (true, false) -> nieuwe array maken met 1,1 en 1,2 als waarden.

dan krijg je dus weer stap 2
1,3 kijken naar 2,1 (true, false) -> nieuwe array maken met 1,3 als waarde(n)

volgende punt
2,1 kijken naar 2,2 (true, true)
2,1 kijken naar 2,3 (true, false) -> nieuwe array met waarde 2,1 en 2,2

volgende punt
2,3 (einde reeks) -> nieuwe array met 2,3 als waarde

HMMMM.... en dan lijkt het dus fout te gaan, want (1,3) en (2,3) liggen onderelkaar en ook (1,1), (1,2), (2,1) en (2,2) liggen bijelkaar.

Maar dat geeft niet! De 2e array ga je nogmaals doorlopen om dit samen te voegen.
Je moet dan eerst alle 'samengestelde' waardes met elkaar vergelijken

1,1 en 1,2 vergelijken met de volgende 1,3
1,1 -> 1,3 = (true/false)
1,2 -> 1,3 = (true/true)
bij 1 false hoort 1,3 gewoon niet bij die array

de check vervolgt zich:

dan vergelijken we het eerste waarde paar nogmaals met het 3e waarde paar:
1,1 -> 2,1 (true/true)
1,1 -> 2,2 (true/true)
1,2 -> 2,1 (true/true)
1,2 -> 2,2) (true/true)

Alles op true! Dus deze 4 coordinaten horen bijelkaar! (en dat klopt)

Dan vergelijken we het eerste paar weer met het de laatste waarde uit de 2e array
1,1 -> 2,3 (true, false)
1,2 -> 2,3 (true, true)
weer een false melding, dus 2,3 hoort er weer niet bij

dan ga je de volgende waarde vergelijken.
1,3 - > 1,1 (true, false)
1,3 -> 1,2 (true, true)
een false melding, dus niet grouperen

1,3 -> 2,1 (true, false)
1,3 -> 2,2 (true, true)
(vanwege 1 false worden deze dus niet samengevoegd)

1,3 vergelijken met 2,3 -> true, true
true -> Dus die worden dan wel samengevoegd!

En dan uiteindelijk heb je dus (1,1) (1,2) (2,1) (2,2) bij elkaar en (1,3 en 2,3) bijelkaar, zonder dat ze elkaar overlappen

[ Voor 4% gewijzigd door Verwijderd op 07-09-2007 13:57 ]

[Janoz]

Waarom zouden 1,2 en 1,3 niet bij elkaar horen? De afstand tussen 1,2 en 1,3 is immers net zo groot asl die tussen 1,2 en 1,1.

[Verwijderd]

op die manier komt ieder coordinaat maar 1 keer voor.

Anders krijg je alsnog 6 punten die dicht bij elkaar liggen, en die allemaal elkaars coordinaten bevatten.

[Verwijderd]

Heb je dit probleem inmiddels al kunnen oplossen?
Afgezien van de abstractheid, denk ik dat omixium wel een goede oplossing heeft gevonden (mits dat in code te vangen is)

Ik ben wel benieuwd naar een stukje 'werkende code' voor dit probleem.

[KopjeThee]

Een k-means clustering zou ook kunnen. Een paar iteraties zal misschien al een aardig resultaat geven.

1 Je kiest een k punten uit je dataset (de "means")
2 Je kent alle punten uit je dataset toe aan de "means" (op basis van de kleinste afstand)
3 Je verschuift elk van de k "means" naar het midden van alle punten die aan die mean waren toegekend.
4 ga naar 2

Als je dit een paar keer hebt gedaan, dan laat je alleen de means zien. K-means is een eenvoudig clustering algoritme. Misschien kan je ook wat varieren.

[Verwijderd]

@kopjethee
de k-means clustering klinkt interessant en ziet er veelbelovend uit, maar hoe vang je dat in een stukje php-code?

[ Voor 8% gewijzigd door Verwijderd op 09-09-2007 16:08 ]

[KopjeThee]

Verwijderd schreef op zondag 09 september 2007 @ 16:05:
@kopjethee
de k-means clustering klinkt interessant en ziet er veelbelovend uit, maar hoe vang je dat in een stukje php-code?

Onderaan die wikipedia link staat een verwijzing naar een php implementatie.