[Alg/php] Afbeelding vullen a la Ishihara oefeningen

[Jurgle]

Hallo medegotters,

Met de gd library die in php zit wil ik plaatjes gaan vullen met balletjes van verschillende grootte en niet op een raster maar willekeurig verdeeld over de afbeelding. Het is de bedoeling dat het er ongeveer uit gaat zien zoals de bekende 'Ishihara' tests voor kleurenblindheid:



Deze bollen lijken random neergezet te zijn en een random grootte te hebben en toch evenredig de achtergrondkleur afdekken. In mijn geval laat ik kleur buiten beschouwing. Ik wil een zwart/wit plaat.

De quick en dirty methode die ik bedacht had was een object maken en vullen met zoveel bolletjes dat als je de bollen naast elkaar zou leggen, je een 10x zo grote oppervlakte zou hebben. Daarna pak je een random bal uit die array en controleer je op deze snijpunten heeft met elke andere bol in die array en aan de hand daarvan laat je de betreffende bol staan of haal je hem weg. Dit kwam aardig in de buurt, maar liet toch nog veel lege plekken ontstaan.

Mijn vraag aan jullie is of jullie misschien ideeen hebben om dit elegant op te lossen? Of kennen jullie een methode die dit doet?

Vanzelfspreken bij voorbaat dank

PS aan een mod: of hoort dit in Software Engineering & Architecture thuis?

[ Voor 6% gewijzigd door Jurgle op 24-03-2007 23:46 . Reden: PS erbij ]

[MisterData]

Het eerste dat in me opkomt is een soort recursief verdelings-algoritme: je begint met één bol, de grote. Die verdeel je in een willekeurig aantal bollen met random grootte die de originele bol zo goed mogelijk benaderen. Dat algoritme hoeft niet zo moeilijk te zijn, als je de bol bijvoorbeeld altijd in 3 kleinere bollen verdeelt. Daarna ga je (recursief) diezelfde verdelingsfunctie weer toepassen op de zojuist gemaakte bollen en je zou een heel eind moeten komen denk ik...

[ Voor 13% gewijzigd door MisterData op 24-03-2007 23:55 ]

[mithras]

MisterData schreef op zaterdag 24 maart 2007 @ 23:54:
Het eerste dat in me opkomt is een soort recursief verdelings-algoritme: je begint met één bol, de grote. Die verdeel je in een willekeurig aantal bollen met random grootte die de originele bol zo goed mogelijk benaderen. Dat algoritme hoeft niet zo moeilijk te zijn, als je de bol bijvoorbeeld altijd in 3 kleinere bollen verdeelt. Daarna ga je (recursief) diezelfde verdelingsfunctie weer toepassen op de zojuist gemaakte bollen en je zou een heel eind moeten komen denk ik...

En dan nog wat verder geredeneerd: je specificeert een maximale grootte (boven die grootte moet de bol opgeplitst worden) en een minimale grootte (wordt die radius overschreden moet een nieuwe verdeling bedacht worden).
Wat je ook nog kan doen is een bol verdelen in $random stukjes, die tussen de 2 en de 4 of 5 ligt. Dat maakt de verdeling lastiger, maar nog wel te doen.

Om die verdeling te maken kan je denk ik het beste @random (een aantal) punten kiezen die het midden vormen van de nieuwe cirkels. De bijbehorende radius is volgens mij wel met een (eenvoudiger dan dit) algoritme uit te rekenen.

[Jurgle]

@MisterData: Volgens mij krijg je in dat geval niet een random verdeling. Je zoekt immers steeds naar een manier om de grote bol op te delen in een aantal bollen die de grote bol 'het best benaderen'. Dat moeten dus per definitie allemaal even grote bollen zijn die met regelmaat verdeeld zijn. Toch?
Ik het geval dat je 1 bol in 3 bollen opdeelt bijvoorbeeld krijg je in jouw voorbeeld volgens mij drie even grote bollen met als je lijnen tekent die hun middelpunten verbinden, een gelijkzijdige driehoek krijgt.

[megamuch]

/offtopic

moet er in die middelste ook wat te zien zijn ?

[mrFoce]

megamuch schreef op zondag 25 maart 2007 @ 00:08:
/offtopic

moet er in die middelste ook wat te zien zijn ?

Meerdere mensen op MSN en ik zitten er ook al naar te kijken. Staat niets in of wel ?

[ Voor 5% gewijzigd door mrFoce op 25-03-2007 00:10 ]

[Jurgle]

offtopic:
Jij begint ook aan jezelf te twijfelen? Ik deed dat ook, daarom gebruik ik deze plaat. Ik zie ook niks op de middelste iig

[Puch-Maxi]

Oh gelukkig, ik dacht dat het aan mij lag .me ziet op de middelste ook niets.

[Jurgle]

En we zijn weer on-topic

[mithras]

Jurgle schreef op zondag 25 maart 2007 @ 00:18:
En we zijn weer on-topic

Maar wat vind je van mij post? Ik zit even te kijken: op zich is de methode wel ok, maar krijg je uiteindelijk hetzelfde effect dat er nog wat gaten kunnen ontstaan in de eerste zetten van die recursiviteit. Maar het opdelen in een willekeurig aantal nieuwe cirkels met een willekeurig middelpunt in de grote cirkel geeft al een heel groot aantal mogelijkheden

Hoe je dus gaat voorkomen dat je grote lege plekken krijgt is lastiger te controleren. Ik weet niet of het mogelijk is, maar het mooiste zou zijn dat je ook de lege plekken (naast de cirkels) bij houdt, en de oppervlakte van een zo'n deel kan bepalen. Maar vogel dat maar eens uit

[ Voor 22% gewijzigd door mithras op 25-03-2007 00:31 ]

[Blorgg]

Owjee, de gruwelijke herinneringen aan dat geklier met Flash waarin je verschillende objecten interactie met elkaar moet laten hebben komen weer boven :B

Vanuit een array willekeurig bolletjes zetten zal nooit echt lekker gaan werken omdat de methode gewoon niet juist is voor dit doeleinde. Wat je wil is beginnen met 1 bolletje, en er dan 1 zo strak mogelijk tegenaan plaatsen, en dan weer 1 erbij enzovoort, todat je cirkel vol zit.

Er zijn genoeg Flash tutorials te vinden over hoe je bijvoorbeeld een bak kunt vullen met een aantal cirkels die je van boven erin kiept en die dan een beetje stuiteren en uiteindelijk tegen- en op elkaar blijven liggen. Sleutelwoord is collision detection. Kijk gewoon daar het algoritme van af. En of je dan een bak vult of een cirkel, dat maakt opzich weinig verschil.

Is misschien niet de snelste methode wat rekentijd aangaat, maar het geeft je wel een resultaat zoals in die plaatjes. De middelste is trouwens een 3

[ Voor 13% gewijzigd door Blorgg op 25-03-2007 00:59 ]

[Verwijderd]

De middelste is trouwens een 3

Jij bent echt kleurenblind

[Verwijderd]

De middelste is een 6.

Maar ook ik zie deze niet in een andere kleur.

[Jurgle]

@mithras: Ik ben die van jou nu aan het simuleren.
@Overigen: die middelste is niks, google maar even voor bewijs. Hou het on-topic plz.

[Marcj]

Is het niet makkelijker om met de grootste bolletjes te beginnen en deze zo goed mogelijk (maar random) de cirkel te laten opvullen en daar met steeds kleiner wordende bolletjes de gaten opvullen?

[compufreak88]

Jurgle schreef op zondag 25 maart 2007 @ 01:29:
@mithras: Ik ben die van jou nu aan het simuleren.
@Overigen: die middelste is niks, google maar even voor bewijs. Hou het on-topic plz.

Volgens mij was het zo dat mensen die bepaalde kleuren hetzelfde zien, er juist wel een getal in zagen.

[MisterData]

Jurgle schreef op zondag 25 maart 2007 @ 00:06:
@MisterData: Volgens mij krijg je in dat geval niet een random verdeling. Je zoekt immers steeds naar een manier om de grote bol op te delen in een aantal bollen die de grote bol 'het best benaderen'. Dat moeten dus per definitie allemaal even grote bollen zijn die met regelmaat verdeeld zijn. Toch?
Ik het geval dat je 1 bol in 3 bollen opdeelt bijvoorbeeld krijg je in jouw voorbeeld volgens mij drie even grote bollen met als je lijnen tekent die hun middelpunten verbinden, een gelijkzijdige driehoek krijgt.

Ze hoeven hem niet 100% te benaderen he! Dus dan mogen de bollen in grootte verschillen. Daarnaast kun je ook het aantal bollen waar je in splitst random maken

[Daos]

offtopic:
De middelste is wat kleurenblinden zien als ze naar links kijken.

Kan je niet met een grid werken?

Als je met een grid werkt (bv 10 bij 10 pixels), dan gaat het zowiezo een heel stuk sneller. Je hebt minder punten waar cirkels kunnen liggen en je hoeft minder punten te vergelijken om te kijken of cirkels overlappen. Hoe de afdruk van de cirkels op het grid is, kan je van tevoren al bepalen (bv met een scriptje die php uitpoept). Een cirkel van 20 bij 20 neemt vier gridblokjes in beslag. Bij grotere cirkels kunnen wat blokjes in de hoeken eraf.

Om het allemaal wat mooier te laten lijken, kan je ook eerst een aantal grote cirkels random op je grid zetten om vervolgens via een vaste route lege plekken op te vullen met cirkels met willekeurige grootte.

[MrBucket]

Is het jullie trouwens al opgevallen dat de drie afbeeldingen allemaal dezelfde configuratie van bolletjes hebben, en dat alleen de kleur van de bolletjes per plaatje verschilt?

Dit betekent dat je tijdens het genereren van de positie van de bolletjes geen rekening hoeft te houden met wat je wilt afbeelden; pas als je een goede vulling van bolletjes hebt gevonden ga je de kleur van de bolletjes bepalen om er bijv. een cijfer in te verstoppen.
--edit
Net nog even met een tekenprogramma gecontroleerd, maar de configuratie van de bolletjes zijn niet helemaal hetzelfde. Helaas

Het lijkt erop dat de grootste bolletjes allemaal even ver van elkaar afliggen, dus deze zullen denk ik als eerste geplaatst worden. De rest van de cirkel wordt dan (op een of andere manier...) gevuld met de kleinere bolletjes.

[ Voor 9% gewijzigd door MrBucket op 25-03-2007 15:10 ]

[Blorgg]

Als je met een grid zou werken, dan krijg je geen willekeurig opgevult geheel. En je zal dan waarschijnlijk het geheel ook niet zo goed kunnen opvullen zoals op het voorbeeld. De reden dat het voorbeeld zo goed is gevuld lijkt mij te komen doordat ze die bolletjes redelijk willekeurig tegen elkaar hebben gelegd.

Vergelijk het met een bak knikkers waarvan je de bodem met een laag van 1 knikker hoog wilt gaan bedekken. Als je de knikkers er los in zou gaan leggen op een grid dan krijg je vrij veel gaten. Maar als je de verschillende knikkers erin legt en een beedje rond schud dan vult het geheel zich netjes op.

[H!GHGuY]

Ben ik de enige die aan voronoi en delauney denkt?

Het is niet exact wat je nodig hebt, maar je kan er misschien wel wat dingen uit halen die nuttig zijn.

[Daos]

QuickBasic (voorloper van VB) voorbeeldje met een grid. Het plaatsen gebeurt nu random. Dat kan misschien wat sneller. Het analyseren zou bovendien van te voren kunnen gebeuren met het resultaat hardcoded.

Visual Basic:

DECLARE FUNCTION ChooseColor% ()
DECLARE FUNCTION IsPlacable% (GridX%, GridY%, Circ%)
DECLARE SUB PlaceCircle (GridX%, GridY%, Circ%)
DECLARE FUNCTION IsPainted% (GridX%, GridY%)
DECLARE SUB PaintCircle (GridX%, GridY%, Circ%)
DECLARE SUB AnalyseCircles ()
DEFINT A-Z

SCREEN 12

CONST FALSE = 0
CONST TRUE = NOT FALSE

CONST CircleCount = 10

CONST GridSize = 10

CONST MaxX = 639
CONST MaxY = 479

CONST MaxGridX = (MaxX + 1) \ GridSize - 1
CONST MaxGridY = (MaxY + 1) \ GridSize - 1

DIM SHARED CircleData(CircleCount, CircleCount * 2, CircleCount * 2)
DIM SHARED CircleOffset(CircleCount)

DIM SHARED GridData(MaxGridX, MaxGridY)

RANDOMIZE TIMER


AnalyseCircles
                      
FOR i# = 1 TO 100000
    GridX = INT(RND * (MaxGridX + 1))
    GridY = INT(RND * (MaxGridY + 1))
    Circ = INT(RND * CircleCount) + 1

    IF IsPlacable(GridX, GridY, Circ) THEN
        PlaceCircle GridX, GridY, Circ
    END IF
NEXT

SUB AnalyseCircles
    CLS
    FOR Circ = 1 TO CircleCount
        'Get Circle Data
        PaintCircle 0, 0, Circ
        FOR GridY = 0 TO 2 * CircleCount - 1
            FOR GridX = 0 TO 2 * CircleCount - 1
                CircleData(Circ, GridX, GridY) = IsPainted(GridX, GridY)
            NEXT
        NEXT
        CLS

        'Get Circle Offset
        PaintingSeen = FALSE
        FOR GridX = 0 TO 2 * CircleCount - 1
            IF NOT PaintingSeen AND CircleData(Circ, GridX, 0) THEN
                PaintingSeen = TRUE
                CircleOffset(Circ) = GridX
            END IF
        NEXT
    NEXT
END SUB

FUNCTION ChooseColor
    ChooseColor = INT(RND * 2) * 8 + 2  'Green
END FUNCTION

FUNCTION IsPainted (GridX, GridY)
    x = GridX * GridSize
    y = GridY * GridSize
       
    IsPainted = FALSE
    FOR i = x TO x + GridSize - 1
        FOR j = y TO y + GridSize - 1
            IF POINT(i, j) THEN IsPainted = TRUE
        NEXT
    NEXT
END FUNCTION

FUNCTION IsPlacable (GridX, GridY, Circ)
    GridX1 = GridX - CircleOffset(Circ)
    GridY1 = GridY

    GridX2 = 2 * Circ + GridX1 - 1
    GridY2 = 2 * Circ + GridY1 - 1

    IF GridX1 < 0 OR GridY1 < 0 THEN
        IsPlacable = FALSE
    ELSEIF GridX2 > MaxGridX OR GridY2 > MaxGridY THEN
        IsPlacable = FALSE
    ELSE
        IsPlacable = TRUE
        FOR GX = GridX1 TO GridX2
            FOR GY = GridY1 TO GridY2
                IF CircleData(Circ, GX - GridX1, GY - GridY1) AND GridData(GX, GY) THEN
                    IsPlacable = FALSE
                END IF
            NEXT
        NEXT
    END IF
END FUNCTION

SUB PaintCircle (GridX, GridY, Circ)
    r = Circ * GridSize - 1
    c = ChooseColor
    x = GridX * GridSize + r
    y = GridY * GridSize + r

    CIRCLE (x, y), r, c
    PAINT (x, y), c
END SUB

SUB PlaceCircle (GridX, GridY, Circ)
    GridX1 = GridX - CircleOffset(Circ)
    GridY1 = GridY

    GridX2 = 2 * Circ + GridX1 - 1
    GridY2 = 2 * Circ + GridY1 - 1

    FOR GX = GridX1 TO GridX2
        FOR GY = GridY1 TO GridY2
            IF CircleData(Circ, GX - GridX1, GY - GridY1) THEN
                GridData(GX, GY) = TRUE
            END IF
        NEXT
    NEXT

    PaintCircle GridX1, GridY1, Circ
END SUB

Ik kwam QuickBasic vandaag weer tegen. Dit leek me wel even leuk om te proberen...

[edit]
Plaatje

[ Voor 1% gewijzigd door Daos op 25-03-2007 18:58 . Reden: Plaatje toegevoegd ]

[Blackbird-ce]

Misschien een benadering vanaf de andere kant? Genereer eerst een bol gemaakt van allemaal kleine bollen (1 px groot, bij wijze van spreken). Dat moet aardig te doen zijn lijkt me.
Vervolgens ga je at random bollen die naast elkaar liggen mergen.

[MrBucket]

Blackbird-ce schreef op zondag 25 maart 2007 @ 21:50:
Misschien een benadering vanaf de andere kant? Genereer eerst een bol gemaakt van allemaal kleine bollen (1 px groot, bij wijze van spreken). Dat moet aardig te doen zijn lijkt me.
Vervolgens ga je at random bollen die naast elkaar liggen mergen.

Dat gaat in sommige (veel?) gevallen niet goed.

Stel dat je vier bollen hebt in de volgende configuratie:

code:

.  1
.2   3
.  4

Stel dat bol 2 of 3 al gemerged is. Op het moment dat je bol 1 en 4 wil mergen, zal de nieuwe bol overlap hebben met bol 2 en 3. Deze merge is dan niet toegestaan.

Met deze aanpakk zullen er dus heel veel kleine bollen overblijven.