Datentypen TreeMap nach Color sortiert (kd-Baum)

[glörf]

Ich benötige eine Datenstruktur/Datentyp mit dem/der sich folgendes realisieren lässt

gegeben ist als Input ein zweidimensionales Array das die Farben eines Bildes enthält und die x/y-Koordinanten als Index hat.

Color[][] bildArray

dieses soll konvertiert werden in eine Struktur, die jedem im Bild vorhanden Color-Wert (RGB) die Menge Punkte mit den Koordinaten x und y zweist, die genau diese Farbe besitzen. Die RGBs sollen dann natürlich noch einmal als Schlüssel vorkommen.

etwa so
(25,7,114) : {Point(7/5)}
(255,255,0) : {Point(2,99), Point(7,34)}
…

die Struktur soll wahlweise nach dem Wert von R, G oder B aus Color sortiert sein.

ich habe es mit

TreeMap<HashSet<Point>>

probiert, und für Color Comparable implementiert, aber da bekomme ich jedoch Probleme beim Einfügen der Punkte in die nach R,G oder B sortierte Struktur. Ich glaube das Problem liegt darin, dass TreeMap keine doppelten Schlüssel zulässt die auftreten wenn man nach R,G oder B “comparet”, aber in ihrer Gesamtheit eindeutig sind.


Anmerkung: das ganze sollen Knoten in einem kd-Baum werden, mit R,G und B als Schlüssel, x und y als Knotenwerte.


Bin für jede Hilfe dankbar

 

[bERt0r]

class MyColor implements Compareable
{
private int R,G,B;
//get,set, Konstruktor, compareto
}

TreeMap<MyColor,Vector<Point>> ?

 

[nillehammer]

Also eine Datenstruktur, bei der man beliebig das Sortierkriterium zwischendrin ändern kann, kenne ich nicht. Ich würde darum empfehlen mit drei TreeMaps zu arbeiten, eine in der nach R, eine in der nach G und eine in der nach B sortiert ist.

Da Comparable<Color> natürlich nur ein Kriterium berücksichtigen kann, kommt es nicht in Frage. Implementiere also nicht Comparable. Sondern implementiere drei mal Comparator<Color> (eben einmal einen für R, einen für G und einen für B) und nutze jeweils eine Instanz dieser Implementierung bei dem Erstellen der drei TreeMaps.

 

[bERt0r]

import java.awt.Point;
import java.util.Random;
import java.util.TreeMap;
import java.util.Vector;


public class ColorMapTest {
	
	class MyColor implements Comparable<MyColor>
	{
		private int r,g,b;

		@Override
		public int compareTo(MyColor c) 
		{
			int red=c.getR();
			int blue=c.getB();
			int green=c.getG();
			
			if(r==red)
			{
				if(g==c.getG())
				{
					if(b==blue)
					{
						return 0;
					}
					else
					{
						if(b>blue)
						{
							return 1;
						}
						else
						{
							return -1;
						}
					}
				}
				else
				{
					if(g>green)
					{
						return 1;
					}
					else
					{
						return -1;
					}
				}
			}
			else
			{
				if(r>red)
				{
					return 1;
				}
				else
				{
					return -1;
				}
			}
		
		}

		public MyColor(int r, int g, int b) {
			super();
			this.r = r;
			this.g = g;
			this.b = b;
		}

		public int getR() {
			return r;
		}

		public void setR(int r) {
			this.r = r;
		}

		public int getG() {
			return g;
		}

		public void setG(int g) {
			this.g = g;
		}

		public int getB() {
			return b;
		}

		public void setB(int b) {
			this.b = b;
		}
		
		public String toString()
		{
			return "\nMyColor["+r+","+g+","+b+"]";
		}
		
	}

	ColorMapTest()
	{
		TreeMap<MyColor,Vector<Point>> map=new TreeMap<MyColor,Vector<Point>>();
		Random r=new Random();
		for (int i=0;i<100;i++)
		{
			int red=r.nextInt(5);
			int green=r.nextInt(5);
			int blue=r.nextInt(5);
			MyColor col=new MyColor(red,green,blue);
			Vector<Point> points;
			if(map.containsKey(col))
			{
				points=map.get(col);
			}
			else
			{
				points=new Vector<Point>();
			}
			int x=r.nextInt(100);
			int y=r.nextInt(100);
			points.add(new Point(x,y));
			map.put(col, points);
		}
		System.out.println(map);
		
	}
	public static void main(String [] args)
	{
		new ColorMapTest();
	}
}

 

[glörf]

import java.awt.Point;
import java.util.Random;
import java.util.TreeMap;
import java.util.Vector;


public class ColorMapTest {
	
	class MyColor implements Comparable<MyColor>
	{
		private int r,g,b;

		@Override
		public int compareTo(MyColor c) 
		{
			int red=c.getR();
			int blue=c.getB();
			int green=c.getG();
			
			if(r==red)
			{
				if(g==c.getG())
				{
					if(b==blue)
					{
						return 0;
					}
					else
					{
						if(b>blue)
						{
							return 1;
						}
						else
						{
							return -1;
						}
					}
				}
				else
				{
					if(g>green)
					{
						return 1;
					}
					else
					{
						return -1;
					}
				}
			}
			else
			{
				if(r>red)
				{
					return 1;
				}
				else
				{
					return -1;
				}
			}
		
		}

		public MyColor(int r, int g, int b) {
			super();
			this.r = r;
			this.g = g;
			this.b = b;
		}

		public int getR() {
			return r;
		}

		public void setR(int r) {
			this.r = r;
		}

		public int getG() {
			return g;
		}

		public void setG(int g) {
			this.g = g;
		}

		public int getB() {
			return b;
		}

		public void setB(int b) {
			this.b = b;
		}
		
		public String toString()
		{
			return "\nMyColor["+r+","+g+","+b+"]";
		}
		
	}

	ColorMapTest()
	{
		TreeMap<MyColor,Vector<Point>> map=new TreeMap<MyColor,Vector<Point>>();
		Random r=new Random();
		for (int i=0;i<100;i++)
		{
			int red=r.nextInt(5);
			int green=r.nextInt(5);
			int blue=r.nextInt(5);
			MyColor col=new MyColor(red,green,blue);
			Vector<Point> points;
			if(map.containsKey(col))
			{
				points=map.get(col);
			}
			else
			{
				points=new Vector<Point>();
			}
			int x=r.nextInt(100);
			int y=r.nextInt(100);
			points.add(new Point(x,y));
			map.put(col, points);
		}
		System.out.println(map);
		
	}
	public static void main(String [] args)
	{
		new ColorMapTest();
	}
}

danke, ich brauche aber 3 Listen, die jew. nach R, B, G sortiert sind und kosistent zueinander sind. und wenn man eine der drei nach Rot sortieren würde, dann können Schlüssel mehrfach vorkommen:

nach RGB sortiert (wie in deinem Code) sind sie Schlüssel eindeutig, weil ja alle 3 zum Schlüssel gehören;
Eintrag1: (255,100,7) ,Vector<Point>
Eintrag2: (255,230,2) ,Vector<Point>

dann z.b. nur nach R:
- die zwei Einträge haben den gleichen Schlüssel (255), aber TreeMap will lässt keine doppelten Schlüssel zu und überschreibt dann einen Eintrag mit dem anderen.

Verstehst du mein Problem? (oder ich hab etwas nicht richtig verstanden)

 

[bERt0r]

Edit:
1 Treemap<MyColor,Vector<Point>>
3 Vector<MyColor>
3 Comparatoren

import java.awt.Point;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Random;
import java.util.TreeMap;
import java.util.Vector;


public class ColorMapTest {
	
	class MyColor implements Comparable<MyColor>
	{
		private int r,g,b;

		public MyColor(int r, int g, int b) {
			super();
			this.r = r;
			this.g = g;
			this.b = b;
		}

		public int getR() {
			return r;
		}

		public void setR(int r) {
			this.r = r;
		}

		public int getG() {
			return g;
		}

		public void setG(int g) {
			this.g = g;
		}

		public int getB() {
			return b;
		}

		public void setB(int b) {
			this.b = b;
		}

		public String toString()
		{
			return "MyColor["+r+","+g+","+b+"]";
		}

		@Override
		public int compareTo(MyColor c) 
		{
			int red=c.getR();
			int blue=c.getB();
			int green=c.getG();

			if(r==red)
			{
				if(g==c.getG())
				{
					if(b==blue)
					{
						return 0;
					}
					else
					{
						if(b>blue)
						{
							return 1;
						}
						else
						{
							return -1;
						}
					}
				}
				else
				{
					if(g>green)
					{
						return 1;
					}
					else
					{
						return -1;
					}
				}
			}
			else
			{
				if(r>red)
				{
					return 1;
				}
				else
				{
					return -1;
				}
			}

		}

	}

	
	ColorMapTest()
	{
		TreeMap<MyColor,Vector<Point>> pointMap=new TreeMap<MyColor,Vector<Point>>();
		Vector<MyColor> rVect=new Vector<MyColor>();
		Vector<MyColor> gVect=new Vector<MyColor>();
		Vector<MyColor> bVect=new Vector<MyColor>();
				
		
		Random r=new Random();
		for (int i=0;i<100;i++)
		{
			int red=r.nextInt(5);
			int green=r.nextInt(5);
			int blue=r.nextInt(5);
			MyColor col=new MyColor(red,green,blue);
			Vector<Point> points;
			if(pointMap.containsKey(col))
			{
				points=pointMap.get(col);
			}
			else
			{
				points=new Vector<Point>();
			}
			int x=r.nextInt(100);
			int y=r.nextInt(100);
			points.add(new Point(x,y));
			pointMap.put(col, points);
		}
		
		Comparator<MyColor> rCompare=new Comparator<MyColor>()
		{
			@Override
			public int compare(MyColor c1, MyColor c2) {			
				if (c1.getR()==c2.getR())
				{
					return 0;
				}
				else
				{
					if(c1.getR()<c2.getR())
					{
						return Integer.MIN_VALUE;
					}
					else
					{
						return Integer.MAX_VALUE;
					}
				}
			}

		};

		Comparator<MyColor> gCompare=new Comparator<MyColor>()
		{
			@Override
			public int compare(MyColor c1, MyColor c2) {			
				if (c1.getR()==c2.getR())
				{
					return 0;
				}
				else
				{
					if(c1.getR()<c2.getR())
					{
						return Integer.MIN_VALUE;
					}
					else
					{
						return Integer.MAX_VALUE;
					}
				}
			}
		};



		Comparator<MyColor> bCompare=new Comparator<MyColor>()
		{
			@Override
			public int compare(MyColor c1, MyColor c2) {			
				if (c1.getR()==c2.getR())
				{
					return 0;
				}
				else
				{
					if(c1.getR()<c2.getR())
					{
						return Integer.MIN_VALUE;
					}
					else
					{
						return Integer.MAX_VALUE;
					}
				}
			}
		};
		
		
		rVect.addAll(pointMap.keySet());
		Collections.sort(rVect, rCompare);
		gVect.addAll(pointMap.keySet());
		Collections.sort(gVect, gCompare);
		bVect.addAll(pointMap.keySet());
		Collections.sort(bVect, bCompare);
		
		System.out.println("Sortiert nach rot");
		for(MyColor c:rVect)
		{
			System.out.println(c+": "+pointMap.get(c));
		}
		System.out.println("\n\nSortiert nach grün");
		for(MyColor c:gVect)
		{
			System.out.println(c+": "+pointMap.get(c));
		}
		System.out.println("\n\nSortiert nach blau");
		for(MyColor c:bVect)
		{
			System.out.println(c+": "+pointMap.get(c));
		}
		
	}
	public static void main(String [] args)
	{
		new ColorMapTest();
	}
}

 

[glörf]

Lässt sich eine HashMap denn mittels einem Comparator sortieren?

 

[bERt0r]

HashMaps sind nicht sortiert.

 

[glörf]

sorry, war in gedanken bei TreeMap