Logik: Grenz-/Frontlinie zeichnen

[nroz]

Hallo Leute,

kennt ihr einen Algorithmus mit dem ich eine Frontlinie bzw. Grenze berechnen kann?
Gegeben sind mehrere Punkte und jeder Punkt gehört zu einer Fraktion.
Zwischen diesen Punkten soll eine Grenze gezogen werden.

Beispielbild:
Schwarze Linie - die zu berechnende Grenze
blaue/rote Punkte - die gegebenen Punkte

Ich selber komme überhaupt nicht mehr weiter und jetzt hoffe ich auf ein Stichwort oder Lösungsansatz.

Vielen Dank

 

[Quaxli]

Grundsätzlich fällt mir da der Begriff der Interpolation ein. Aber Du könntest mal ein bißchen außen rum erzählen (Hintergrund zu dem Problem) evtl. fällt ja dem einen oder anderen dann noch eine Lösung ein.

 

[Marco13]

Interpolation? Ich hätte da jetzt eher das Wort "Clustering" eingeworfen...
http://en.wikipedia.org/wiki/Data_clustering

Grundsätzlich ist die Linie, die du suchst, in deinem Beispiel aber falsch eingezeichnet :wink: Du könntest jeweils die einander nächstgelegenen roten und blauen Punkte mit einer Strecke verbinden. Dann kannst du Geraden einzeichnen, die jeweils durch die Mitte der Strecken verlaufen und senkrecht darauf stehen. Diese Geraden schneiden sich dann an eniigen Stellen, und wie Abschnitte zwischen den Schnittpunkten dürften zusammengenommen deine Grenzlinie ergeben.

Zusammengefaßt: Schau dir auch mal http://en.wikipedia.org/wiki/Voronoi_diagram an :wink:

 

[Marco13]

Als Nachtrag: Der Kreis, den du um den einzelenen Blauen Punkt gezeichnet hast, wäre dann kein Kreis. Stattdessen wäre es ein Polygon. Innerhalb dieses Polygons lägen dann alle Punkte, die NÄHER am blauen Punkt liegen als an irgendeinem roten Punkt. (Das ist schon fast die Definition eines Voronoi-Diagramms)

 

[nroz]

Das Voroni-Diagramm sieht auf den ersten Blick sehr gut aus.
Ich werd mich mal einlesen aber schonmal vielen Dank!