# Abstand von Punkten



## Jariel (25. Nov 2010)

Hallo, ich hab folgendes Problem:

Ich hab eine Fläche die ich anmalen muss. Vorgegeben hab ich ein zweidimensionales Array mit einigen Punkten inkl. ihrer Farbe. Nun muss der Rest der Fläche auch ausgemalen werden, und die Punkte sollen jeweils die selbe Farbe annehmen wie der nächstgelegene Punkt im Array.

Der Array gestaltet sich wie folgt:

blub[1][] ist der erste Punkt, blub[2][] der 2te, blub[3][] der 3te, etc.

blub_[0] ist dann die x-Koordinate des i-ten Punktes, blub[1] die y-Koordinate und blub[2] die Farbe


Der Abstand 2er Punkte (x1,y1); (x2,y2) wird mittels dem euklidischen Abstand ermittelt,
 also Distanz := Wurzel((x1 - x2)^2 + (y1 - y2)^2).

Das ganze grafische Zeugs hab ich schon, mir geht es nur um die Ermittlung des nächstgelegenen Array-Punktes. Die Fläche die ausgemalen werden soll ist 500 Punkte breit und 500 hoch. Meine ersten kärglichen Überlegungen, aber weiter komm ich nicht :
(die Malmethode schaut so aus: drawPoint(frame, x-Koordinate, y-Koordinate, Farbe) )



		Java:In die Zwischenablage kopieren


// eine Variable für die Distanz:
double dist = Math.sqrt((x1 - blub[i][0]) * (x1 - blub[i][0]) + (y1 - blub[i][1]) * (y1 - blub[i][1]) ); 
//hab mal die Array Punkte hingemalen:
for (int i=0; i<blub.length; ++i) {
		drawPoint(frame,blub[i][0], blub[i][1], blub[i][2]);
		}


Kann mir jemand einen Tipp oder Pseudocode geben wie man nun für jeden Punkt (x <= 500; y <= 500) den nächstgelegenen Punkt vom Array blub findet?_


----------



## Marco13 (25. Nov 2010)

Vorneweg: Mach' dir eine Klasse "ColoredPoint" oder so - oder überleg' dir, wie du das ganze effizient auf einem BufferedImage machen kannst.

Pseudocode: 

```
List<Point> presentPoints = ...
Point closest = null;
double minDistance = +infinity;
for (each point p)
{
    for (each presentPoint q)
    {
        if (p.distance(q) < minDistance)
        {
            minDistance = p.distance(q);
            closest = q;
        }
    }
    // Closest point for p is q
}
```

Klingt als wolltest du auf ziemlich umständliche Weise ein Voronoi diagram - Wikipedia, the free encyclopedia malen...


----------



## XHelp (25. Nov 2010)

Falls mich die Uhrzeit nicht täuscht, muss man in der Schleife für jeden Punkt 
	
	
	
	





```
p
```
 immer wieder 
	
	
	
	





```
minDistance
```
 auf +infinity setzen.


----------



## Jariel (26. Nov 2010)

Danke habs hinbekommen. Eine Frage noch, wie setzt man einen Wert auf unendlich in Java? Ich hab ihn jetzt einfach extra hoch gesetzt und es funktioniert auch, nur wäre unendlich wohl besser.


----------



## XHelp (26. Nov 2010)

Naja, Enendlich muss es nicht unbedingt sein, 
	
	
	
	





```
Double.MAX_VALUE
```
 reicht aus. Aber es gibt auch 
	
	
	
	





```
Double.POSITIVE_INFINITY
```


----------

