Thread: algorithm

Sorry, but I'm not a electrical person...

Could you explain what this algorithm does in plain english

A step-by-step description of what your algorithm is would be nice, too.

Ok, tell me if this is what you want:

* You have 4 different inputs for signal strengths, a,b,c,d which are floating point numbers (inactive set).
* You have a set of sensor readings for xa,xb,xc,xd, and ya,yb,yc,yd from each sensor (active set)
* The points |p1-x|,|p2-x|,|p3-x|...|pn-x| are computed via sqrt((an-ax)^2+...
* The value to take is the smallest |pn-x| of this list
* Do the same thing with y (|p1-y|,|p2-y|,...|pn-y|)

Is this correct?

edit: Here's the code I came up with based on the above algorithm

public static class SensorDatabase
	{
		private Point[] inactiveDatabase, x, y;
 
		/**
		 * Constructs a database of sensor readings
		 * 
		 * @param inactiveAValues
		 * @param inactiveBValues
		 * @param inactiveCValues
		 * @param inactiveDValues
		 * @param xAValues
		 * @param xBValues
		 * @param xCValues
		 * @param xDValues
		 * @param yAValues
		 * @param yBValues
		 * @param yCValues
		 * @param yDValues
		 */
		public SensorDatabase(double[] inactiveAValues,
				double[] inactiveBValues, double[] inactiveCValues,
				double[] inactiveDValues, double[] xAValues, double[] xBValues,
				double[] xCValues, double[] xDValues, double[] yAValues,
				double[] yBValues, double[] yCValues, double[] yDValues)
		{
			try
			{
				this.inactiveDatabase = new Point[inactiveAValues.length];
				this.x = new Point[xAValues.length];
				this.y = new Point[yAValues.length];
				for (int i = 0; i < inactiveAValues.length; i++)
				{
					this.inactiveDatabase[i] = new Point(inactiveAValues[i],
							inactiveBValues[i], inactiveCValues[i],
							inactiveDValues[i]);
				}
				for (int i = 0; i < xAValues.length; i++)
				{
					this.x[i] = new Point(xAValues[i], xBValues[i],
							xCValues[i], xDValues[i]);
					this.y[i] = new Point(yAValues[i], yBValues[i],
							yCValues[i], yDValues[i]);
				}
			}
			catch (Exception e)
			{
				throw new RuntimeException("Error: array indices didn't match!");
			}
		}
 
		/**
		 * Constructs a database of sensor readings
		 * 
		 * @param inactiveDatabase
		 * @param x
		 * @param y
		 */
		public SensorDatabase(Point[] inactiveDatabase, Point[] x, Point[] y)
		{
			if (x.length != y.length)
			{
				throw new RuntimeException(
						"Error: x and y lengths aren't the same");
			}
			this.inactiveDatabase = inactiveDatabase.clone();
			this.x = x.clone();
			this.y = y.clone();
		}
 
		/**
		 * Finds the closest x value
		 * 
		 * @return
		 */
		public Point computeClosestX()
		{
			Point closest = this.x[0];
			double distance = Point.computeDistance(this.inactiveDatabase[0],
					this.x[0]);
			for (int i = 1; i < this.x.length; i++)
			{
				if (distance > Point.computeDistance(this.inactiveDatabase[i],
						this.x[i]))
				{
					closest = this.x[i];
					distance = Point.computeDistance(this.inactiveDatabase[i],
							this.x[i]);
				}
			}
			return closest;
		}
 
		/**
		 * Finds the closest y value
		 * 
		 * @return
		 */
		public Point computeClosestY()
		{
			Point closest = this.y[0];
			double distance = Point.computeDistance(this.inactiveDatabase[0],
					this.y[0]);
			for (int i = 1; i < this.y.length; i++)
			{
				if (distance > Point.computeDistance(this.inactiveDatabase[i],
						this.y[i]))
				{
					closest = this.y[i];
					distance = Point.computeDistance(this.inactiveDatabase[i],
							this.y[i]);
				}
			}
			return closest;
		}
 
		public static class Point
		{
			public double a, b, c, d;
 
			/**
			 * Constructs a point
			 * 
			 * @param a
			 * @param b
			 * @param c
			 * @param d
			 */
			public Point(double a, double b, double c, double d)
			{
				this.a = a;
				this.b = b;
				this.c = c;
				this.d = d;
			}
 
			/**
			 * Computes the distance between p1 and p2 as defined as:
			 * 
			 * sqrt((p1.a - p2.a)^2 + (p1.b - p2.b)^2 + (p1.c - p2.c)^2 + (p1.d
			 * - p2.d, 2)^2);
			 * 
			 * @param p1
			 * @param p2
			 * @return
			 */
			public static double computeDistance(Point p1, Point p2)
			{
				return Math.sqrt(Math.pow(p1.a - p2.a, 2)
						+ Math.pow(p1.b - p2.b, 2) + Math.pow(p1.c - p2.c, 2)
						+ Math.pow(p1.d - p2.d, 2));
			}
		}
	}

Ok, here's the what i've come up with:

* You have access points on 8 different floors. They will read in 4 (or more) x values each, and compute their mean via those formula you had for |xa|,...|xh|. *note: did you mean to divide by 4 since you wanted an average, or was that intentionally left out?
* p_1,p_2,...p_n are SNR sample data from different access points (each have an a,b,c,d,e,f,g,h value)
* compute |p_1-x|...|p_n-x| and pick the smallest value. This is ≈x

correct?

public class SensorList
{
	private Readings[] snrList;
	private Readings averageX;
 
	/**
	 * Constructs the SNR list
	 * 
	 * @param snrList
	 * @param x
	 */
	public SensorList(Readings[] snrList, Readings[] x)
	{
		this.snrList = snrList.clone();
		// compute the mean values for x
		// compute a
		double a = 0;
		for (int i = 0; i < x.length; i++)
		{
			a += x[i].a;
		}
		a /= x.length;
		// compute b
		double b = 0;
		for (int i = 0; i < x.length; i++)
		{
			b += x[i].b;
		}
		b /= x.length;
		// compute c
		double c = 0;
		for (int i = 0; i < x.length; i++)
		{
			c += x[i].c;
		}
		c /= x.length;
		// compute d
		double d = 0;
		for (int i = 0; i < x.length; i++)
		{
			d += x[i].d;
		}
		d /= x.length;
		// compute e
		double e = 0;
		for (int i = 0; i < x.length; i++)
		{
			e += x[i].e;
		}
		e /= x.length;
		// compute f
		double f = 0;
		for (int i = 0; i < x.length; i++)
		{
			f += x[i].f;
		}
		f /= x.length;
		// compute g
		double g = 0;
		for (int i = 0; i < x.length; i++)
		{
			g += x[i].g;
		}
		g /= x.length;
		// compute h
		double h = 0;
		for (int i = 0; i < x.length; i++)
		{
			h += x[i].h;
		}
		h /= x.length;
		this.averageX = new Readings(a, b, c, d, e, f, g, h);
	}
 
	/**
	 * Finds the smallest |pn-x| value
	 * 
	 * @return |pn-x|
	 */
	public double computeSmallestX()
	{
		double smallest = Readings.computeVal(this.snrList[0], this.averageX);
		for (int i = 1; i < this.snrList.length; i++)
		{
			double val = Readings.computeVal(this.snrList[i], this.averageX);
			if (smallest > val)
			{
				smallest = val;
			}
		}
		return smallest;
	}
 
	/**
	 * Finds the which pn gives the smallest |pn-x| value
	 * 
	 * @return Readings of |pn-x| that is the smallest
	 */
	public Readings computeWhichSmallestX()
	{
		int index = 0;
		double smallest = Readings.computeVal(this.snrList[0], this.averageX);
		for (int i = 1; i < this.snrList.length; i++)
		{
			double val = Readings.computeVal(this.snrList[i], this.averageX);
			if (smallest > val)
			{
				index = i;
				smallest = val;
			}
		}
		return this.snrList[index];
	}
 
	public static class Readings
	{
		public double a, b, c, d, e, f, g, h;
 
		/**
		 * Constructs a reading sample
		 * @param a
		 * @param b
		 * @param c
		 * @param d
		 * @param e
		 * @param f
		 * @param g
		 * @param h
		 */
		public Readings(double a, double b, double c, double d, double e,
				double f, double g, double h)
		{
			this.a = a;
			this.b = b;
			this.c = c;
			this.d = d;
			this.e = e;
			this.f = f;
			this.g = g;
			this.h = h;
		}
 
		/**
		 * Computes |pn-x| as defined:
		 * 
		 * sqrt((pn.a - x.a)^2 + (pn.b - x.b)^2 + (pn.c - x.c)^2 + (pn.d -
		 * x.d)^2+(pn.e-x.e)^2+(pn.f-x.f)^2+(pn.g-x.g)^2+(pn.h-x.h)^2);
		 * 
		 * @param pn
		 * @param x
		 * @return
		 */
		public static double computeVal(Readings pn, Readings x)
		{
			return Math.sqrt(Math.pow(pn.a - x.a, 2) + Math.pow(pn.b - x.b, 2)
					+ Math.pow(pn.c - x.c, 2) + Math.pow(pn.d - x.d, 2)
					+ Math.pow(pn.e - x.e, 2) + Math.pow(pn.f - x.f, 2)
					+ Math.pow(pn.g - x.g, 2) + Math.pow(pn.h - x.h, 2));
		}
	}
}

Hmm... ok, maybe finally i've understood what you want

From the program's perspective, it doesn't matter which floor the access points are on, just that there are 8 of them

I do have to change computing the averages, though.

Whether it's called a list or a database from the program's perspective doesn't matter.

What did you mean by comparing to P_1? Is that the user's location? Or is P_1 through P_N a potential position for the user?

public class SensorList
{
	private Readings[] snrList;
	private Readings averageX;
 
	/**
	 * Constructs the SNR list
	 * 
	 * @param snrList
	 * @param x
	 */
	public SensorList(Readings[] snrList, Readings[] x)
	{
		this.snrList = snrList.clone();
		// compute the mean values for x
		// compute a
		double a = 0;
		for (int i = 0; i < x.length; i++)
		{
			a += x[i].a * x[i].a;
		}
		a = Math.sqrt(a);
		// compute b
		double b = 0;
		for (int i = 0; i < x.length; i++)
		{
			b += x[i].b * x[i].b;
		}
		b = Math.sqrt(b);
		// compute c
		double c = 0;
		for (int i = 0; i < x.length; i++)
		{
			c += x[i].c * x[i].c;
		}
		c = Math.sqrt(c);
		// compute d
		double d = 0;
		for (int i = 0; i < x.length; i++)
		{
			d += x[i].d * x[i].d;
		}
		d = Math.sqrt(d);
		// compute e
		double e = 0;
		for (int i = 0; i < x.length; i++)
		{
			e += x[i].e * x[i].e;
		}
		e = Math.sqrt(e);
		// compute f
		double f = 0;
		for (int i = 0; i < x.length; i++)
		{
			f += x[i].f * x[i].f;
		}
		f = Math.sqrt(f);
		// compute g
		double g = 0;
		for (int i = 0; i < x.length; i++)
		{
			g += x[i].g * x[i].g;
		}
		g = Math.sqrt(g);
		// compute h
		double h = 0;
		for (int i = 0; i < x.length; i++)
		{
			h += x[i].h * x[i].h;
		}
		h = Math.sqrt(h);
		this.averageX = new Readings(a, b, c, d, e, f, g, h);
	}
 
	/**
	 * Finds the smallest |pn-x| value
	 * 
	 * @return |pn-x|
	 */
	public double computeSmallestX()
	{
		double smallest = Readings.computeVal(this.snrList[0], this.averageX);
		for (int i = 1; i < this.snrList.length; i++)
		{
			double val = Readings.computeVal(this.snrList[i], this.averageX);
			if (smallest > val)
			{
				smallest = val;
			}
		}
		return smallest;
	}
 
	/**
	 * Finds the which pn gives the smallest |pn-x| value
	 * 
	 * @return Readings of |pn-x| that is the smallest
	 */
	public Readings computeWhichSmallestX()
	{
		int index = 0;
		double smallest = Readings.computeVal(this.snrList[0], this.averageX);
		for (int i = 1; i < this.snrList.length; i++)
		{
			double val = Readings.computeVal(this.snrList[i], this.averageX);
			if (smallest > val)
			{
				index = i;
				smallest = val;
			}
		}
		return this.snrList[index];
	}
 
	public static class Readings
	{
		public double a, b, c, d, e, f, g, h;
 
		/**
		 * Constructs a reading sample
		 * 
		 * @param a
		 * @param b
		 * @param c
		 * @param d
		 * @param e
		 * @param f
		 * @param g
		 * @param h
		 */
		public Readings(double a, double b, double c, double d, double e,
				double f, double g, double h)
		{
			this.a = a;
			this.b = b;
			this.c = c;
			this.d = d;
			this.e = e;
			this.f = f;
			this.g = g;
			this.h = h;
		}
 
		/**
		 * Computes |pn-x| as defined:
		 * 
		 * sqrt((pn.a - x.a)^2 + (pn.b - x.b)^2 + (pn.c - x.c)^2 + (pn.d -
		 * x.d)^2+(pn.e-x.e)^2+(pn.f-x.f)^2+(pn.g-x.g)^2+(pn.h-x.h)^2);
		 * 
		 * @param pn
		 * @param x
		 * @return
		 */
		public static double computeVal(Readings pn, Readings x)
		{
			return Math.sqrt(Math.pow(pn.a - x.a, 2) + Math.pow(pn.b - x.b, 2)
					+ Math.pow(pn.c - x.c, 2) + Math.pow(pn.d - x.d, 2)
					+ Math.pow(pn.e - x.e, 2) + Math.pow(pn.f - x.f, 2)
					+ Math.pow(pn.g - x.g, 2) + Math.pow(pn.h - x.h, 2));
		}
	}
}

Haha, it's not awesome, too be honest. It was really lousy programming, even for me. But hopefully it should get done what you needed to get done. I'd explain it, but there's an awful lot of cs topics in there. Now that I think about it, I didn't tell you how to use it...

How were you planning on sending information to this program? I can write you a harness so that you can actually use this code with little effort

I didn't change the code for the Pn stuff, so hopefully it should work correctly.

Here's what it's doing:

I'm assuming you have sensor readings at each of the access points (these are the Pn stuff), and the user has some device that has the X readings. Then, the closest access point (or what-ever the |Pn-X| formulas do) is computed by |Pn-X|

I wrote two methods, one that tells you which Pn gives the closest value, and another one that gives what that value was.

WOW, thats exactly what is its suppose to do, compare Pn with the X and the algorithm does some math and when we get the smallest value, then the user is at this Pn ..... whats up with the harness ?? how can we do this ??
i owe you seriously man...

A harness is basically code that allows someone who is either lazy or has little programming experience to use the algorithm easily Right now, it's just a bare algorithm. Depending on how this data will be sent to this program, I can write a useful harness. Is the data being read from a file? Are you/someone going to type it in (in which case, GUI or console)? Is there some sort of data stream that the program can read from? The possibilities are endless.

Oh, and it would be much easier to write the harness if you gave me specifications on how the data would be formatted, and some sample values (and the expected output if possible).