Abstand von Punkten

[Jariel]

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) )

// 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]

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]

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

p

immer wieder

minDistance

auf +infinity setzen.

 

[Jariel]

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]

Naja, Enendlich muss es nicht unbedingt sein,

Double.MAX_VALUE

reicht aus. Aber es gibt auch

Double.POSITIVE_INFINITY