Drawing an ishihara (color blind test)?

I'm trying to draw a ishihara in code ( like this http://en.wikipedia.org/wiki/Ishihara_colourblindness_test ). And am having trouble with generating the random pattern of dots.

Basically I need to create random size dots that more or less fill the area, but don't overlap. I'm sure there is some clever way of doing this, but I don't know how.

My current approach is brute force. Create a dots at a random location, then check if it overlaps with those drawn previously. If it does, I skip it, and draw a new one. Repeat a 100.000 times or so. It's close to working, but it's hard to get a completely dense pattern, and there are more small dots than big ones, as they are less likely to overlap (and it's extremely slow...but that's not a big issue).

I'm thinking one of two ways should be possible:

1. Recursive function, that work a little bit like paint bucket fill tool. I've done some code like this in the past (can't find it), but it get's more complex with random size dots and no grid pattern.

2. Procedural texture style. Using worley or cell or something. I've used these in 3D software, but they may be a bit too complex for me to get my head around in code. I'm no math expert. :)

Any suggestions on how to approach this?

Doesn't matter in which language, I'm currently writing it in php and outputing svg. But BlitzMax/Blitz3D would work just as fine.

Ragnar

Don't know where my post went, but it was something like this:

You could do it like a Physics Demo. Drop random sized circles in from the top and let them all fall into place. Then color them as needed.

Hehe...though of that too. But figured that it would probably be even harder. Though, I have been working on a 2D physics system in BlitzMax, it only has some basic particle, gravity and springs so far, no collision. :)

Any reason you need to create these programatically? Can't you just create them by hand - storing coords, size and colour of each dot? Shouldn't take too long to knock up an editor to achieve this.

P.S. I'm a bit worried that I have trouble making out this one:

Is it a 2? :/

Aye.

Ah - just that it looks like it's surrounded by a load of green blobs, to me.

Graphics 800,600,0,2
ft = CreateTimer(60)

SeedRnd(MilliSecs())

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Type ball
	Field x#, y#, dx#, dy#, r, count, sumxforce#, sumyforce#
End Type
Global ballRad = 5
makeBalls()

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

pushing = 1

Repeat

	If KeyHit(57) Then
		If pushing = 1 Then
			pushing = 0
			setBalls()
		EndIf
	EndIf
	
	If pushing Then PushBalls()
	
	;WaitEvent()
	
	Cls
	If pushing Then
		DrawRects()
	Else
		DrawBalls()
	EndIf
	Flip(0)

Until KeyHit(1)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Function makeBalls()
	For a = 1 To 2000
		nb.ball = New ball
		nb\r = Rand(2,5) * 10
		nb\x = Rand(nb\r, GraphicsWidth()-nb\r)
		nb\y = Rand(nb\r, GraphicsHeight()-nb\r)
		nb\count = a
	Next
End Function

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Function PushBalls()
	
	GW = GraphicsWidth()
	GH = GraphicsHeight()
	
	For eb.ball = Each ball	
		
		For eb2.ball = Each ball
		If eb\count < eb2\count Then
			xdif = eb\x - eb2\x
			ydif = eb\y - eb2\y
			
			If RectsOverlap(eb\x-eb\r,eb\y-eb\r,2*eb\r,2*eb\r , eb2\x-eb2\r,eb2\y-eb2\r,2*eb2\r,2*eb2\r) Then
				dist# = Sqr(xdif*xdif + ydif*ydif)
			
				xf# = xdif / dist / dist
				yf# = ydif / dist / dist
				
				eb\sumxforce = eb\sumxforce + xf
				eb\sumyforce = eb\sumyforce + yf
				
				eb2\sumxforce = eb2\sumxforce - xf
				eb2\sumyforce = eb2\sumyforce - yf
			EndIf
			
		EndIf
		Next
		
		midDist# = Sqr((GW/2 - eb\x)*(GW/2 - eb\x) + (GH/2 - eb\y)*(GH/2 - eb\y))
		eb\sumxforce = eb\sumxforce + (GW/2 - eb\x) / midDist# / 100
		eb\sumYforce = eb\sumYforce + (GH/2 - eb\y) / midDist# / 100
		
	Next
	
	
	
	For eb.ball = Each ball	
		eb\dx = eb\dx + eb\sumxforce
		eb\dy = eb\dy + eb\sumyforce
		
		eb\x = eb\x + eb\dx
		eb\y = eb\y + eb\dy
		
		eb\dx = eb\dx * 0.8
		eb\dy = eb\dy * 0.8
		
		If eb\x-eb\r < 0 Then
			eb\x = eb\r
		ElseIf eb\x + eb\r > GW
			eb\x = GW - eb\r
		EndIf
		
		If eb\y - eb\r < 0 Then
			eb\y = eb\r
		ElseIf eb\y + eb\r > GH
			eb\y = GH - eb\r
		EndIf
		
		eb\sumxforce# = 0
		eb\sumyforce# = 0
		
	Next
End Function

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Function setBalls()

	For eb.ball = Each ball	
		
		minDist = -1
		
		For eb2.ball = Each ball
		If eb <> eb2 Then
			xdif = eb\x - eb2\x
			ydif = eb\y - eb2\y
			dist# = Sqr(xdif*xdif + ydif*ydif)
			
			If minDist = -1 Or dist < minDist
				minDist = dist
			EndIf
			
		EndIf
		Next
		
		eb\r = minDist/2
		
	Next

End Function

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Function DrawRects()
	For eb.ball = Each ball	
		Rect eb\x-eb\r/2/2, eb\y-eb\r/2/2, 2*eb\r/2/2, 2*eb\r/2/2
		;Oval eb\x-eb\r, eb\y-eb\r, 2*eb\r, 2*eb\r, 0
	Next
End Function

Function DrawBalls()
	For eb.ball = Each ball
		Oval eb\x-eb\r, eb\y-eb\r, 2*eb\r, 2*eb\r, 0
	Next
End Function

Here's a rough idea in BlitzPlus code to generate some positions and sizes. It's rough.

Run this for a few dozen loops and then hit the Space Bar.

What do you all think?

Graphics 800,600,0,2
ft = CreateTimer(60)

SeedRnd(MilliSecs())

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Type ball
	Field x#, y#, r
End Type

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Global failsInARow = 0
Global maxFails = 50

Repeat

	If failsInARow < maxFails Then
		If addBall() Then
			failsInARow = 0
		Else
			failsInARow = failsInARow + 1
		EndIf
	EndIf
	
	;WaitEvent()
	
	Cls
	DrawBalls()
	Flip(0)

Until KeyHit(1)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Function addBall()
	
	GW = GraphicsWidth()
	GH = GraphicsHeight()
	newR = Rand(5, 20)
	
	For a = 1 To 1000
		newx = Rand(newR, GW-newR)
		newy = Rand(newR, GH-newR)
		
		isgood = 1
		
		For eb.ball = Each ball
			dx = (eb\x-newx)
			dy = (eb\y-newy)
			If dx*dx + dy*dy < (eb\r + newR)*(eb\r + newR) Then
				isgood = 0
				Exit
			EndIf
		Next
		
		If isgood = 1 Then
			nb.ball = New ball
			nb\x = newx
			nb\y = newy
			nb\r = newR
			Exit
		EndIf
	Next
	
	Return isGood
	
End Function

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Function DrawBalls()
	If failsInARow < maxFails Then
	;	For eb.ball = Each ball
	;		Rect eb\x-eb\r, eb\y-eb\r, 2*eb\r, 2*eb\r, 0
	;	Next
		Text 0,0,failsInARow
	Else
		For eb.ball = Each ball
			Oval eb\x-eb\r, eb\y-eb\r, 2*eb\r, 2*eb\r, 0
		Next
	EndIf
End Function

And here's one which packs much tighter like those images but takes longer (much) to complete. Adjust the starting ball sizes to get things to converge faster. I commented out the drawing code before complete to make things go faster. This overall method might be preferred.

Rck: Thanks for the example. I converted the second one to BlitzMax as I don't have BlitzPlus, and added space to stop it. :-)

Graphics 800,600,0,2
ft = CreateTimer(60)

SeedRnd(MilliSecs())

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Type ball
	Field x#, y#, r
End Type

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Global failsInARow = 0
Global maxFails = 50
Global ballList:TList = CreateList()


Repeat

	If failsInARow < maxFails Then
		If addBall() Then
			failsInARow = 0
		Else
			failsInARow = failsInARow + 1
		EndIf
	EndIf
	
	If KeyHit(KEY_SPACE) Then
		failsInARow = 51
		EndIf
	'WaitEvent()
	
	Cls
	DrawBalls()
	Flip(0)

Until KeyHit(KEY_ESCAPE)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Function addBall()
	
	GW = GraphicsWidth()
	GH = GraphicsHeight()
	newR = Rand(5, 20)
	
	For a = 1 To 1000
		newx = Rand(newR, GW-newR)
		newy = Rand(newR, GH-newR)
		
		isgood = 1
		
		For eb:ball = EachIn ballList
			dx = (eb.x-newx)
			dy = (eb.y-newy)
			If dx*dx + dy*dy < (eb.r + newR)*(eb.r + newR) Then
				isgood = 0
				Exit
			EndIf
		Next
		
		If isgood = 1 Then
			nb:ball = New ball
			nb.x = newx
			nb.y = newy
			nb.r = newR
			ballList.AddLast(nb)
			Exit
		EndIf
	Next
	
	Return isGood
	
End Function

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

Function DrawBalls()
	If failsInARow < maxFails Then
		For eb:ball = EachIn ballList
			DrawRect eb.x-eb.r, eb.y-eb.r, 2*eb.r, 2*eb.r
		Next
		DrawText 0,0,failsInARow
	Else
		For eb:ball = EachIn ballList
			DrawOval eb.x-eb.r, eb.y-eb.r, 2*eb.r, 2*eb.r
		Next
	EndIf
End Function

It's close to what I want, though a bit brute force like my current method. Will look into it further.

I've got a solution I think is going to work, but it requires a bit of trigonometry.

If I have a triangle, and have the position of corners A and B, and have the length of all three sides. How do I find the postion of corner C?

I probably knew the answer to that in high-school, but that was a long time ago. :-)

Do you know the angle of any of the sides? I think you can do it by knowing the length of all the sides, but then again I'm failing math right now. :(

Ah now I remember, the Sine Theory thingy: http://www.teacherschoice.com.au/Maths_Library/Trigonometry/solve_trig_SSS.htm

SOH
CAH
TOA

Sin(theta)=Opp/Hyp
Cos(theta)=Adj/Hyp
Tan(theta)=Opp/Adj

But SOH CAH TOA only works with right triangles doesn't it?

Yeah, right angles. You are correct.

Use law of cosines to solve for some internal angles and then you can project point C off of A or B (because you know angles and length) ; use po's link a few posts above


and for BP -> BM code conversion remem

BP:

Text x,y,t$

BM:

DrawText(t$,x,y)

I think Rck's code above was looking pretty good, but here is another method I thought of.

1. Create a bunch of random points. Since these are just points, the chance of collisions should be relatively low, but you can check this easily.

2. Now go back through each of the points, and expand it to a larger radius circle. Do this in small steps.

3. Check if the new size collides with something. If it does, then stop expanding, or back up to the previous size. Continue this until no more points can be expanded.

I don't know how well it would work in code, but it seems to be working in my head.

Pull up the code for the 'bubbles' screensaver from most graphical linux distributions. It solves the same problem. Whether it does so in an elegant way, I'm not sure.

Me again. Now I'm close to a working solution. This needs a basic web server and php, plus a browser that supports svg to work. :)

I've figured the angles of all the corners, and the lengths of all sides. But I still need help with figuring out the position of that last corner of the triangle.

Here is a quick explaination of what the code does.
- It's a loop for the x axis, with a loop for the y axis.
- It creates circles in a verticalrow.
- Checks all circles to the left of it, and offsets it horizontaly, to be to the right of that (box collission).

This almost works, but there are cracks in the pattern.

What I want to do, is create a triangle between the ball on the left (A), the ball above (B) and the new ball (C). I know the coordinates of A and B, the length of all the sides, and the angle of all corners. All that is missing is to project a vector from A or B, out to C, I know the angle and the length, so it shouldn't be a problem...right!

Anyone know how to?

Here is the code I have so far...

<?php
class ishihara {
  private $balls = array();
  private $rmin;
  private $rmax;
  private $padding;

  private $w;
  private $h;

  public function __construct($w,$h,$rmin,$rmax) {
    $this->w = $w;
    $this->h = $h;
    $this->rmin = $rmin;
    $this->rmax = $rmax;
    $this->padding = 1;
  }


  public function positionBalls() {
    // Horizontal loop
    $lastLine = array();
    $thisLine = array();
    $x = 0;
    while ($x<$this->w) {
      // Vertical loop
      $y = 0;
      $lastRadius = 0;
      while ($y<$this->h) {
	$radius = rand($this->rmin,$this->rmax);
	$y = $y+$radius+$lastRadius+$this->padding;

	$toTheRight = array();
	foreach ($lastLine as $lineBall) {
	  $top = $y-$radius;
	  $bottom = $y+$radius;
	  $linetop = $lineBall->y - $lineBall->r;
	  $linebottom = $lineBall->y + $lineBall->r;
	  if (($top <= $linebottom) && ($bottom >= $linetop)) {
	    array_push($toTheRight,$lineBall);
	  }
	}
	$maxx = 0;
	foreach ($toTheRight as $rightBall) {
	  // Find angle a and angle b.
	  $a = $rightBall->r + $radius + $this->padding;
	  $b = $rightBall->r + $lastRadius + $this->padding;
	  $c = $lastRadius + $radius + $this->padding;
	  $weight = 180/($a+$b+$c);
	  $a_angle = $a*$weight;
	  $b_angle = $b*$weight;
	  $c_angle = $c*$weight;
	  //echo 'A '.$a_angle.' B '.$b_angle.' C '.$c_angle.' TOTAL '.($a_angle+$b_angle+$c_angle).'<br>';

	  // HELP!  Project vector at $a_angle, relative to a to b plane, $c distance.
	  
	  
	  // This is the code that's used in this loop. It only checks with a squara.
	  if ($rightBall->x+$rightBall->r+$radius+$this->padding > $maxx) {
	    $maxx = $rightBall->x+$rightBall->r+$radius+$this->padding;
	  }
	  $lastRadius = $radius;
	}
	
	$x = $maxx+$this->padding;
	$ball = new ball($x,$y,$radius);
	array_push($thisLine, $ball);
	array_push($this->balls, $ball);
      }
      $lastLine = $thisLine;
      $thisLine = array();
    }
  }

  
  public function draw() {
    header('Content-type: image/svg+xml');
    echo '<?xml version="1.0" standalone="no"?>';
    echo '<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">';
    echo '<svg width="'.$this->w.'" height="'.$this->h.'" version="1.1" xmlns="http://www.w3.org/2000/svg">';
    foreach ($this->balls as $ball) {
      $ball->draw();
    }
    echo '</svg>';
  }
}

class ball {
  public $x;
  public $y;
  public $r;
  public $rgb;

  public function __construct($x,$y,$r) {
    $this->x = $x;
    $this->y = $y;
    $this->r = $r;
    $this->rgb = 'rgb('.$x.',128,'.$y.')';
  }

  public function draw() {
        echo '<circle cx="'.$this->x.'" cy="'.$this->y.'" r="'.$this->r.'" fill="'.$this->rgb.'" />';
    //echo '<rect x="'.$this->x.'" y="'.$this->y.'" width="'.($this->r*2).'" height="'.($this->r*2).'" fill="'.$this->rgb.'" />';

  }
}


$ishihara = new ishihara(500,500,2,8);
$ishihara->positionBalls();
$ishihara->draw();
?>

p.s. The colors are just random for now.

Is this the sort of thing you want to do?

Graphics 640,480,0,2

aX=320
aY=240
Len=100
angle=45

Repeat
Cls
bx=MouseX()
by=MouseY()
Len=Len+MouseZSpeed()
dx=ax-bx
dy=ay-by

angle=(angle+MouseDown(2)-MouseDown(1))
If angle>180 Then angle=angle-360
If angle<-180 Then angle=angle+360

Color 255,0,0 : Text 0,0,"Length: "+Len+",  Angle: "+angle
Color 255,255,255
Line ax,ay,bx,by
theta#=ATan2(-dy,-dx)
vx=ax+Len*Cos(angle+theta)
vy=ay+Len*Sin(angle+theta)
Color 255,0,0 : Line ax,ay,vx,vy
Color 0,255,0 : Line bx,by,vx,vy
Flip
Until KeyDown(1)

My vector maths is not up to much BTW so I imagine there will be a simpler way to do this.

This packing of various sized circles makes an interesting problem.

Why do the Ishihara tests use such circles rather than a grid of uniformly sized dots?

I'd love to do this, but since i'm colourblind I'll never know if its actually working or not XD

OK, just do the circle packing code and we'll do the rest. :P

I found this:
http://scien.stanford.edu/class/psych221/projects/06/dingting/appendix.htm

Click the ColorCheck.zip link. It contains Java program and source used for a research project to generate Ishiharas. I'm still trying to understand the code though, it has 6 nested loops. :-/

Will finish this tonight, or tomorrow....so will have to figure it out one way or another. Worst case, I'll use what I have now, and fill in the cracks manually in InkScape. :)