Mal wieder ein kleines Toleranzproblem

[JVolker]

Hallo

momentan suche ich in meinem Array nach x und y Koordinaten. Wenn welche doppelt sind oder ganz nah beieinander (vorgegebene Toleranz) so gibt mir mein Prog die Zeile aus.

 for (int a = 0 ; a < E.length;a++ ){                                          // E=Array mit X und Y Koordinaten
                for (int b = a+1 ; b < E.length;b++){ 
                if (Math.abs(E[a][0] - E[b][0]) <= toleranz){
                if (Math.abs(E[a][1] - E[b][1]) <= toleranz)
                System.out.println("zeile" +a);
                D[a] = a;
                }
                }
                }

Jetzt habe ich folgendes Problem :

je nachdem wie die Schleife über das Array läuft wird bei mir der erste wert der zutrifft genommen.
Da das jetzt aber vielleicht der höste wert war der hätte zutreffen können löscht er mir die falschen Punkte.

Beispiel1(richtig) : (Toleranz 0,2)

12.3
12.1 //wird ausgegeben
12.5 //wird ausgegeben

in dieser Reihenfolge gibt es keine probeme da der mittelwert oben steht
habe ich aber diese Reihenfolge Beispiel2(falsch)

12.1
12.3//wir ausgegeben
12.5

Wie löse ich am besten das Problem?
muss ich die angemeckerten Werte seperat abspeichern und dann evtl. den mittelwert ermitteln? oder gibt es einen einfacheren Weg?

 

[Gast2]

Was wollst du denn genau erreichen? Wenn du immer zwei Werte vergleichen willst und dabei ne Toleranz von 0.2 zulässt, dann sind 12.1 und 12.5 nunmal nicht gültig.
Oder willst du drei beliebige Werte vergleichen und Prüfen ob die Werte maximal 0.2 vom Mittelwert abweichen?

 

[JVolker]

Ich möchte 3 oder mehrere Werte und über die Toleranz rausfinden.

Ich habe ein File mit belibigen X und Y Koordinaten welche ich in ein Array einlese. Jetzt möchte ich gerne doppelte Punkte(doppelte Punkte = Punkt +/- Toleranz) markieren.

Und da taucht jetzt mein Problem auf das er mir noch die Falschen ausgibt wenn diese nicht in der richtigen Reihenfolge im Array stehen(siehe ersten Beitrag) es können auch 5 oder 10 Koordinaten betroffen sein.

Ich denke mal was anderes wie über den Mittelwert wird mir wohl nicht übrig bleiben, oder?
Und wenn ja wie soll ich die Werte zwischenspeichern?

 

[Marco13]

Hm... das Problem scheint mir nicht genau genug spezifiziert... bei einer Toleranz von 0.2, und Werten wie
0.1, 0.2, 0.3, 0.4, 0.5, 0.6
sind ALLE Werte weniger als 0.2 von einem anderen entfernt (wenn auch nicht von ALLEN anderen)... ???:L

 

[Spacerat]

Also ich würde beim Durchlaufen des Arrays nicht gerade den ersten Treffer markieren und alle weiteren löschen, ich würde erstmal alle Treffer in einem separatem Array sortiert speichern und mir davon den Mittelwert ausrechnen lassen. Diesen Mittelwert würde ich dann im neuen Array suchen und erhiehlte so ein gültiges Element des ursprünglichen Arrays. Dieses Element wird dann markiert, die anderen gelöscht.

 

[Gast2]

Statt dem Mittelwert würde ich den Median nehmen, aber ansonsten joa, genau so.
Aber vielleicht sollte der TO nochmal erklären was genau er erreichen will. Ist für mich nicht wirklich klar.

 

[JVolker]

Also Tabelle mit X Y Koordinaten wird im JTabel angezeigt

folgende Beispiel Datensatz habe ich:

X Y
2,5 1
2,7 1
2,9 1

3,5 2
3,7 2
3,9 2
3,77 2

5,5 3
5,6 3

So und von jeder Y Position soll jetzt nur noch eine Koordinate übrig bleiben. Problem ist das 2,5 nun der kleinste wert ist aber momentan würde mein Durchlauf auch eine 2,3 als unteren Wert annehmen und bei 2,9 wäre der oberste wert 3,1. Es sollte aber so sein das die Koordinate von der die Toleranz ausgeht 2,5 sein sollte.

 

[Gast2]

Von jedem Y Wert soll genau nur ein X Wert übrig bleiben? Dann bilde doch von allen zusammengehörigen X Werten den Mittelwert oder Median. Wofür brauchst du da ne Toleranz?

 

[JVolker]

Weil die Daten nicht ganz so einfach sind wie in meinen Beispiel. In wirklichkeit liegen die Werte nicht auf unterschiedlichen Y Koordinaten.

Es soll ein Programm werden womit ich eine Platte CNC-Bohren könnte. Damit aber die Maschine nicht auf 2,5 / 2,7 / 2,9 jeweils ein Loch bohrt möchte ich gerne das von den 3St. nur noch eine übrig bleibt.

 

[Gast2]

Ok, du willst also Punkte (x/y) die näher als Toleranz z zusammenliegen zu einem Punkt zusammenfassen. Was soll beispielsweise passieren wenn du ne Wertereihe hast wie von Marco13 beschrieben?

Was soll mit Punkten passieren die in nem Viereck liegen: 0,0 - 0,1 - 1,0 - 1,1 bei Toleranz 1, soll der neue Punkt dann 0.5,0.5 sein?

 

[JVolker]

Im ersten Moment ja. habe das nur mit der Wertereihe noch nicht so 100%ig verstanden.
Was passiert denn wenn der Punkt auf 0,9/0,9 liegt und der andere auf 1,1/1,1 dann sollten diese ja zusammengefasst werden.

Die Wertereihe habe ich so verstanden das ich meine Koordinaten einem Gewissen Raster unterlege oder bin ich da falsch

 

[Gast2]

Ja, deine Werte sind ja offensichtlich keine einfachen Werte sondern Punkte in einem 2D System. Und da stellt sich die Frage wie solche Werte wie oben beschrieben zusammengefasst werden sollen. Kann sowas überhaupt vorkommen? Oder liegen die Punkte immer in nem bestimmten Muster?

Gib doch bitte mal nen Beispiel an mit nen paar Punkten und wie das ganze dann zusammengefasst ausschauen soll.

 

[JVolker]

So habe mal schnell was gestrickt also wenn ich exakt gleiche Punktehabe oder nur 2 Punkte funzt es ja auch aber ab 3 Punkten habe ich Probleme.

Hier mal mein vorher nachher Beispiel :

siehe Anhang

 

[Gast2]

Das Beispiel machts für micht nicht unbedingt klarer WIE genau das zusammenlegen funktionieren soll.

Du hast da beispielsweise die Punkte 2.05/3.01 und 2.08/3. Warum wird daraus 2.05/3.1 und nicht 2.08/3, oder vielleicht doch die Mitte der beiden Punkte 2.065/3.005 ?

Wenn du daraus nen Algorithmus bauen willst dann musst du den Computer schon sagen können was er wann zu tun hat.

EDIT:
Da bleiben jetzt meiner Meinung nach genau 2 Fragen zu klären:
1. Woran wird festgemacht welche Werte in einer "Gruppe" sind? In deinem Beispiel hast du die ja schön eingefärbt.
2. Wie kommst du dann von der beliebigen Anzahl an Punkte aus einer Gruppe auf genau den einen der übrig bleibt?

 

[JVolker]

Da hast du recht das mit den Punkten war jetzt von mir reine Willkür. Ich denke ein ittelwert würde am besten sein. Sorry war etwas doof von mir.

Ich denke auch das das größte Problem ist wie ich die Gruppen rausfinde.

 

[Spacerat]

@EikeB: Der Median ist nicht unbedingt jener Wert, welcher dem Mittelwert am nächsten kommt. In einem sortierten Array mit 10 Elementen können die ersten 4 weit unter dem Mittelwert liegen und die restlichen geringfügig bis weit darüber. Der Median wäre dann Element 5. Element 3 oder 4 aber könnten dem Mittelwert durchaus besser entsprechen.
Bei zwei Koordinaten müsste man die die Auswahl der in Frage kommenden Elemente bereits Schachteln, maw. für die beschriebene Auswahl oben nur die Elemente wählen, welche auch auf der zweiten Koordinate eine gewisse Toleranz nicht überschreiten.

 

[Gast2]

Und wenn du folgende Punkte hast:

1, 2, 3, 1000

Dann passt der Median wesentlich besser als der Mittelwert
Es kommt sicherlich auf die Werte an welcher Wert am sinnvollsten ist. Wenn man keine Ausreißer hat ist man mit dem Mittelwert wohl besser dran.

@TO:
Ich würde beim finden der Gruppen ungefähr so vorgehen:
- Nimm einen beliebigen Punkt aus der Menge V der noch verfügbaren Punkten.
- Von da aus alle Punkte ausfindig machen die über Kanten der Länge x (deine Toleranz) erreichbar sind. Alle gefundenen Punkte aus V entfernen und damit neue Gruppe bilden.
(Probleme gibts da dann nur falls du solche Sachen hättest: 0, 0.2, 0.4, 0.6, 0.8, 1. Dann würden alle 6 Werte in die Gruppe fallen. Falls sowas bei dir vorkommt müsste man sich was schlaueres ausdenken.)
- Solange V noch Elemente hat, mach bei erstens weiter.
- Danach von jeder Gruppe den Mittelpunkt (Schwerpunkt?) bestimmen.

So in etwa zumindest

 

[Spacerat]

Und wenn du folgende Punkte hast:

1, 2, 3, 1000

Dann passt der Median wesentlich besser als der Mittelwert

Pack zu der Zahlenreihe noch die 4, dann wäre der Median (mittleres Element) 3, obwohl die 4 inzwischen besser passt (Mittelwert 202). Je mehr Elemente du abseits vom Ausreisser (1000) hinzufügst (z.B. alle Zahlen von 1 bis 50 und die 1000), desto mehr entfernst du dich mit dem Median vom Mittelwert. Bei der von mir oben beschiebenen Auswahl erhält man einen Index auf jenes Element, welches dem Mittelwert am nächsten kommt. Dieses Element muss nicht unbedingt der Mittelwert sein. Bei [c]1, 2, 3, 4, 1000[/c] bekäme man z.B. 4 statt 3. Ich schau mal, ob ich das auf die Schnelle zusammen bekomme.

 

[andiv]

Folgender "Algorithmus" funktioniert für den 1D-Fall ganz gut. Ein Wert wird der Gruppe zugeordnet wenn sein Abstand zum Mittelwert der Gruppe kleiner als die Toleranz ist. Das funktioniert dann auch bei 0.1 0.2 0.3 0.4... noch ganz gut.

Wenn man das ganze aber auf 2D erweitern will wird's glaub ich deutlich komplizierter. Man kann dann ja nicht mehr sortieren. Man müsste also schauen ob der Punkt weniger als Toleranz vom Mittelpunkt einer Gruppe wegliegt und dann dieser Gruppe hinzufügen. Andernfalls entsteht mit diesem Punkt eine neue Gruppe. Spannend wirds dann wenn man zwei Gruppen zusammenfassen muss weil ihre Mittelpunkte zu nah beieinander liegen.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class Test {
 
	private static final int NUMBER_OF_VALUES = 10;
	private static final float TOLERANCE = 0.1f;
	
	private static void printList(List<Float> values) {
		for(float value : values) {
			System.out.printf("%.2f ", value);
		}
		System.out.println();
	}
	
	private static float calcAverage(List<Float> values) {
		float sum = 0f;
		for(float v : values) {
			sum += v;
		}
		return sum / values.size();
	}
	
    public static void main(String... args) {  	
    	List<Float> values = new ArrayList<Float>();
    	
    	// Zufällige Werte generieren
    	Random random = new Random();
    	for(int i = 0; i < NUMBER_OF_VALUES; i++) {
    		values.add(random.nextFloat());
    	}
    	printList(values);
    	
    	// Feste Werte verwenden
//    	values.add(0f);
//    	values.add(0.1f);
//    	values.add(0.2f);
//    	values.add(0.3f);
//    	values.add(0.4f);
//    	values.add(0.5f);
//    	values.add(0.6f);
//    	values.add(0.7f);
//    	values.add(0.8f);
//    	values.add(0.9f);
    	
    	// Werte aufsteigend sortieren
    	Collections.sort(values);
    	printList(values);
    	
    	List<Float> result = new ArrayList<Float>();
    	
    	// Werte in Gruppen zusammenfassen
    	List<Float> group = new ArrayList<Float>();
    	for(float value : values) {
    		if(!group.isEmpty() && Math.abs(value - calcAverage(group)) > TOLERANCE) {
    			// Mittelwert der Gruppe bilden
    			result.add(calcAverage(group));
    			group.clear();
    		}
    		group.add(value);
    	}
		// Mittelwert der letzten Gruppe bilden
		result.add(calcAverage(group));
    	
    	printList(result);
    }
}

 

[JVolker]

Danke für die ganzen Antworten. Werde mir jetzt mal die nacht um die Ohren schlagen und ein paar Möglichkeiten ausprobieren.

 

[Spacerat]

import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;


public class Toleranz
{
	private static final double X_TOL = 0.2;
	private static final double Y_TOL = X_TOL;

	private static final Comparator<Point2D.Double> X_COMPARATOR = new Comparator<Point2D.Double>()
	{
		@Override
		public int compare(Point2D.Double o1, Point2D.Double o2)
		{
			return (o1.x < o2.x)? -1 : (o1.x > o2.x)? 1 : 0;
		}
	};

	public static void main(String[] args)
	{
		List<Point2D.Double> points = new ArrayList<Point2D.Double>();
		points.add(new Point2D.Double(2.05, 3.01));
		points.add(new Point2D.Double(2.08, 3.00));
		points.add(new Point2D.Double(1.79, 4.50));
		points.add(new Point2D.Double(1.33, 2.77));
		points.add(new Point2D.Double(5.76, 3.40));
		points.add(new Point2D.Double(6.00, 3.50));
		points.add(new Point2D.Double(5.88, 3.50));
		points.add(new Point2D.Double(1.10, 2.77));
		points.add(new Point2D.Double(3.60, 5.80));
		points.add(new Point2D.Double(4.45, 6.11));
		points.add(new Point2D.Double(4.48, 6.10));
		points.add(new Point2D.Double(4.20, 6.00));
		points.add(new Point2D.Double(3.73, 5.87));
		points.add(new Point2D.Double(8.16, 6.50));
		points.add(new Point2D.Double(8.40, 6.60));
		points.add(new Point2D.Double(8.28, 6.60));
		points.add(new Point2D.Double(3.50, 5.87));

		SortedSet<Point2D.Double> sortedPoints = new TreeSet<Point2D.Double>(X_COMPARATOR);
		sortedPoints.addAll(points);

		Map<MidVal, Set<Point2D.Double>> groups = new IdentityHashMap<MidVal, Set<Point2D.Double>>();

		Point2D.Double pt1 = sortedPoints.first();
		sortedPoints.remove(pt1);
		addNewGroup(groups, pt1);

		while(!sortedPoints.isEmpty()) {
			pt1 = sortedPoints.first();
			sortedPoints.remove(pt1);
			boolean brk = false;
			for(MidVal mv : groups.keySet()) {
				if(Math.max(mv.y, pt1.y) - Math.min(mv.y, pt1.y) < Y_TOL && Math.max(mv.x, pt1.x) - Math.min(mv.x, pt1.x) < X_TOL) {
					addToGroup(groups, mv, pt1);
					brk = true;
					break;
				}
			}
			if(!brk) {
				addNewGroup(groups, pt1);
			}
		}
	}

	private static void addToGroup(Map<MidVal, Set<Point2D.Double>> groups, MidVal mv, Point2D.Double pt1)
	{
		Set<Point2D.Double> group = groups.get(mv);
		group.add(pt1);
		mv.x = 0.0;
		mv.y = 0.0;
		for(Point2D.Double pt : group) {
			mv.x += pt.x;
			mv.y += pt.y;
		}
		mv.x /= group.size();
		mv.y /= group.size();
	}

	private static void addNewGroup(Map<MidVal, Set<Point2D.Double>> groups, Point2D.Double pt1)
	{
		MidVal mv = new MidVal();
		TreeSet<Point2D.Double> newGroup = new TreeSet<Point2D.Double>(X_COMPARATOR);
		newGroup.add(pt1);
		mv.x = pt1.x;
		mv.y = pt1.y;
		groups.put(mv, newGroup);
	}

	private static final class MidVal
	{
		private double x, y;

		@Override
		public String toString()
		{
			return "Toleranz.MidVal[" + x + ", " + y + "]";
		}
	}
}

Apropos Nacht um die Ohren schlagen... jetzt hab' ich mich drauf festgebissen... Naja...
1. Der Code ist möglicherweise nicht der sauberste aber immerhin...
2. Damit komme ich mit den Punkten aus der Tabelle allerdings auf 9 Gruppen statt auf 8.
3. die Toleranz-MidVal kann man jetzt entweder so lassen, ein Element anhand des X-Mittels oder eines anhand des Y-Mittels wählen oder ein neues Element aus beiden Mittelwerten einer Gruppe erstellen.