algorytm.org

Implementacja w C#



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Wyznaczanie obszaru poszukiwań - Implementacja w C#
Ocena użytkownikóww: *****  / 3
SłabyŚwietny
Nadesłany przez Tomasz Lubiński, 16 czerwca 2007 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

SeaTracePredictor/PositionPredictor.cs:
using System;
using System.Collections;
using System.Drawing;


namespace SeaTracePredictor
{
	/// <summary>
	/// Summary description for PositionPredictor.
	/// </summary>
	public class PositionPredictor
	{
		private static double secondLength = 30.9;
		private ArrayList triangles = new ArrayList();
		private ArrayList pies = new ArrayList();
		private ArrayList oryginalPoints = new ArrayList();
		private ArrayList calledPoints = new ArrayList();
		private	ArrayList pointsToCall = new ArrayList();
		private ArrayList points;
		public PositionPredictorPoint[] availablePoints;
		private int radius;
		private double radiusYInSeconds;
		private double radiusXInSeconds;
		private double maxRadiusYInSeconds;
		private double maxRadiusXInSeconds;
		private double longitude;
		private double latitude;

		//constructor for recurrent calls
		public PositionPredictor(object newBroker, ArrayList newCalledPoints)
		{
			//broker = newBroker;
			oryginalPoints = (ArrayList)newBroker;
			calledPoints = newCalledPoints;
		}

		//constructor for normal use
		public PositionPredictor(object newBroker)
		{
			//broker = newBroker;
			oryginalPoints = (ArrayList)newBroker;
		}

		//returns all points (Special, Additional, Base and other)
		public ArrayList Points
		{
			get 
			{
				return points;
			}
		}

		//method calculates range bewteen two points
		//coordinates are in seconds
		//result is in meter
		public double Range(double latitudeX, double longitudeX, double latitudeY, double longitudeY)
		{
			double avgLatitude, latitudeDist, longitudeDist, result;
			//conversion from seconds to degrees
			avgLatitude = (latitudeX + latitudeY) / 7200;
			longitudeDist = (longitudeX - longitudeY) * Math.Cos(Math.PI * avgLatitude / 180.0);
			latitudeDist = latitudeX - latitudeY;
			result = Math.Sqrt(Math.Pow(latitudeDist, 2) + Math.Pow(longitudeDist, 2));  //Pitagoras statement
			result *= secondLength;

			return result;
		}

		//method calculates intersection between an ellipse and a segment for two non base points
		//latitude, longitude - center of the ellipse, r - radius in y of the ellipse (radius in x is equal r*1/cos(phi))
		//latitudeX, longitudeX - start points of the segment
		//latitudeY, longitudeY - end points of the segment
		private double[] IntersectionNonBase(double latitude, double longitude, double r, double latitudeX, double longitudeX, double latitudeY, double longitudeY)
		{
			double dx, dy, dr2, D, delta;
			dx = (longitudeY - longitudeX);
			dy = (latitudeY - latitudeX)* (1 / Math.Cos(Math.PI * latitude / 648000.0));  //because of navigation deviance (648000 = 60*60*180);;;
			dr2 = Math.Pow(dx ,2) + Math.Pow(dy ,2);
			D = (longitudeX - longitude)*(latitudeY -latitude) - (longitudeY - longitude)*(latitudeX -latitude);
			delta = Math.Pow(r, 2)*dr2 - Math.Pow(D, 2);

			if (delta < 0) 
			{
				return null;
			}
			else if (delta == 0)
			{
				double[] result = new double[2];
				result[0] =  (D * dy) / (dr2 * Math.Cos(Math.PI * latitude / 648000.0)); //because of navigation deviance (648000 = 60*60*180)
				result[1] = (-D * dx) / dr2;
				result[0] += longitude;
				result[1] += latitude;
				if ((result[0]>longitudeX && result[0]>longitudeY) ||
					(result[0]<longitudeX && result[0]<longitudeY) ||
					(result[1]>latitudeX && result[1]>latitudeY) ||
					(result[1]<latitudeX && result[1]<latitudeY))
					return null;
				else
					return result;
			}
			else
			{
				double[] result = new double[4];
				delta = Math.Sqrt(delta);
				result[0] =  (D * dy + Sgn(dy) * dx * delta) / (dr2 * Math.Cos(Math.PI * latitude / 648000.0)); //because of navigation deviance (648000 = 60*60*180)
				result[1] = (-D * dx + Math.Abs(dy) * delta) / dr2;
				result[0] += longitude;
				result[1] += latitude;
				if ((result[0]>longitudeX && result[0]>longitudeY) ||
					(result[0]<longitudeX && result[0]<longitudeY) ||
					(result[1]>latitudeX && result[1]>latitudeY) ||
					(result[1]<latitudeX && result[1]<latitudeY))
					return null;
				else
				{
					result[2] =  (D * dy - Sgn(dy) * dx * delta) / (dr2 * Math.Cos(Math.PI * latitude / 648000.0)); //because of navigation deviance (648000 = 60*60*180)
					result[3] = (-D * dx - Math.Abs(dy) * delta) / dr2;
					result[2] += longitude;
					result[3] += latitude;
					return result;
				}
			}
		}

		//helper method for IntersectionNonBase
		private int Sgn(double a)
		{
			if (a < 0)
				return -1;
			else
				return 1;
		}

		//method calculates intersection between an ellipse and a segment for one base and one non base point
		//latitude, longitude - center of the ellipse, r - radius in y of the ellipse (radius in x is equal r*1/cos(phi))
		//latitudeX, longitudeX - start points of the segment (BASE POINT)
		//latitudeY, longitudeY - end points of the segment (NON BASE POINT)
		private double[] IntersectionBase(double latitude, double longitude, double r, double latitudeX, double longitudeX, double latitudeY, double longitudeY)
		{
			double[] result = new double[4];
			double dx, dy, dr2, D, sqrtDelta;
			dx = (longitudeY - longitudeX);
			dy = (latitudeY - latitudeX) * (1 / Math.Cos(Math.PI * latitude / 648000.0));  //because of navigation deviance (648000 = 60*60*180);
			dr2 = Math.Pow(dx ,2) + Math.Pow(dy ,2);
			D = (longitudeX - longitude)*(latitudeY -latitude) - (longitudeY - longitude)*(latitudeX -latitude);
			sqrtDelta = Math.Sqrt(Math.Pow(r, 2)* dr2 - Math.Pow(D, 2));

			result[0] =  (D * dy + dx * sqrtDelta) / (dr2 * Math.Cos(Math.PI * latitude / 648000.0)); //because of navigation deviance (648000 = 60*60*180)
			result[1] = (-D * dx + dy * sqrtDelta) / dr2;
			result[0] += longitude;
			result[1] += latitude;

			return result;
		}
		
		//function calculates real bearing for observer in point (longitudeY, latitudeY)
		//into point (longitudeX, latitudeX)
		private double Bearing(double latitudeX, double longitudeX, double latitudeY, double longitudeY)
		{
			return 270 - ((Math.Atan2(longitudeX-longitudeY , latitudeX-latitudeY) * 180) / Math.PI);
		}

		//calculates base points
		//base point - point that is inside ellipse
		private void CalculateBasePoints()
		{
			foreach(PositionPredictorPoint p in points)
			{
				if (this.Range(this.latitude, this.longitude, p.Latitude, p.Longitude) < this.radius)
				{
					p.Label = 'B';
				}
			}
		}

		//calculates additional points
		//additional point - point on intersection between ellipse and segment from one base and one non base point
		private void CalculateAdditionalPoints()
		{
			int additionalID = 0;
			int counter = 0;
			double[] result = new double[2];
			PositionPredictorPoint newP;
			PositionPredictorPoint previousP = new PositionPredictorPoint(-1, 0, 0, -1);

			foreach(PositionPredictorPoint p in (ArrayList)points.Clone())
			{
				counter++;
				if ((previousP.Label == 'x') && (p.Label == 'B') && (previousP.Region == p.Region))
				{
					result = IntersectionBase(this.latitude, this.longitude, this.radiusYInSeconds,
						p.Latitude, p.Longitude, previousP.Latitude, previousP.Longitude);
					additionalID++;
					newP = new PositionPredictorPoint(additionalID, result[0], result[1], p.Region);
					newP.Label = 'A';
					points.Insert(counter + additionalID - 2, newP);
				}
				else if ((previousP.Label == 'B') && (p.Label == 'x') && (previousP.Region == p.Region))
				{
					result = IntersectionBase(this.latitude, this.longitude, this.radiusYInSeconds,
						previousP.Latitude, previousP.Longitude, p.Latitude, p.Longitude);
					additionalID++;
					newP = new PositionPredictorPoint(additionalID, result[0], result[1], p.Region);
					newP.Label = 'A';
					points.Insert(counter + additionalID - 2, newP);
				}
				previousP = p;
			}
		}

		//calculates special points
		//special point - point on intersection between ellipse and segment from two base points
		private void CalculateSpecialPoints()
		{
			int specialID = 0;
			int counter = 0;
			double[] result = new double[2];
			PositionPredictorPoint newP;
			PositionPredictorPoint previousP = new PositionPredictorPoint(-1, 0, 0, -1);

			foreach(PositionPredictorPoint p in (ArrayList)points.Clone())
			{
				counter++;
				if ((previousP.Label == 'x') && (p.Label == 'x') && (previousP.Region == p.Region))
				{
					result = IntersectionNonBase(this.latitude, this.longitude, this.radiusYInSeconds,
						p.Latitude, p.Longitude, previousP.Latitude, previousP.Longitude);
					if (result != null)
					{
						specialID++;
						newP = new PositionPredictorPoint(specialID, result[0], result[1], p.Region);
						newP.Label = 'E';
						points.Insert(counter + specialID - 2, newP);
						if (result.Length > 2)
						{
							specialID++;
							newP = new PositionPredictorPoint(specialID, result[2], result[3], p.Region);
							newP.Label = 'E';
							if (Range(result[1], result[0], previousP.Latitude, previousP.Longitude) < 
								Range(result[3], result[2], previousP.Latitude, previousP.Longitude))
							{
								points.Insert(counter + specialID - 2, newP);
							}
							else
							{
								points.Insert(counter + specialID - 3, newP);
							}
						}
					}
				}
				previousP = p;
			}
		}

		//calculate points, that unit can achive direct
		private void CalculateAvailablePoints()
		{
			int count = 0;
			//count how many points, unit can achive direct
			foreach(PositionPredictorPoint point in points)
			{
				if ((point.Label != 'x') && (!IntersectWithSegment(point.Longitude, point.Latitude)))
				{
					count++;
				}
			}
			if (count > 0)
			{
				count++;
			}
			else
			{
				availablePoints = new PositionPredictorPoint[count];
				return;
			}
			//calculate points, that unit can achive direct
			availablePoints = new PositionPredictorPoint[count];
			PositionPredictorPoint tmpPoint;
			int ids = 0;
			count = 0;
			foreach(PositionPredictorPoint point in points)
			{
				ids++;
				if ((point.Label != 'x') && (!IntersectWithSegment(point.Longitude, point.Latitude)))
				{
					tmpPoint = new PositionPredictorPoint(ids, point.Longitude, point.Latitude, point.Region);
					tmpPoint.Bearing = Bearing(this.latitude, this.longitude, point.Latitude, point.Longitude);
					tmpPoint.Label = point.Label;
					availablePoints[count] = tmpPoint;
					count++;
				}
			}
			//sort this point in order bearing
			bool continueSort = true;
			while (continueSort)
			{
				continueSort = false;
				for(int i = 1; i < availablePoints.Length-1; i++)
				{
					if (availablePoints[i-1].Bearing > availablePoints[i].Bearing)
					{
						tmpPoint = availablePoints[i-1];
						availablePoints[i-1] = availablePoints[i];
						availablePoints[i] =  tmpPoint;
						continueSort = true;
					}
				}
			}
			//if two point has the same bearing sort them with neighbour
			for(int i = 1; i < availablePoints.Length-1; i++)
			{
				if (availablePoints[i-1].Bearing == availablePoints[i].Bearing)
				{
					if (i == 1)
					{
						if ((availablePoints[i-1].Region == availablePoints[i+1].Region) &&
							(Math.Abs(availablePoints[i-1].ID - availablePoints[i+1].ID) == 1))

						{
							tmpPoint = availablePoints[i-1];
							availablePoints[i-1] = availablePoints[i];
							availablePoints[i] =  tmpPoint;
						}

					}
					else if (i == availablePoints.Length - 2)
					{
						if ((availablePoints[i-2].Region == availablePoints[i].Region) &&
							(Math.Abs(availablePoints[i-2].ID - availablePoints[i].ID) == 1))
						{
							tmpPoint = availablePoints[i-1];
							availablePoints[i-1] = availablePoints[i];
							availablePoints[i] =  tmpPoint;
						}
					}
					else
					{
						if (((availablePoints[i-2].Region == availablePoints[i].Region) && (Math.Abs(availablePoints[i-2].ID - availablePoints[i].ID) == 1)) || 
							((availablePoints[i-1].Region == availablePoints[i+1].Region)) && (Math.Abs(availablePoints[i-1].ID - availablePoints[i+1].ID) == 1))
						{
							tmpPoint = availablePoints[i-1];
							availablePoints[i-1] = availablePoints[i];
							availablePoints[i] =  tmpPoint;
						}
					}
				}
			}
			if (availablePoints.Length > 2)
			{
				if (availablePoints[0].Bearing == availablePoints[1].Bearing)
				{
					if (Math.Abs(availablePoints[1].ID - availablePoints[count-1].ID) == 1)
					{
						availablePoints[count] = availablePoints[1];
					}
					else
					{
						availablePoints[count] = availablePoints[0];
					}
				}
				else
				{
					availablePoints[count] = availablePoints[0];
				}
			}
			else
			{
				availablePoints[count] = availablePoints[0];
			}
			if (!DifferentBearingsGreaterThanTwo())
			{
				tmpPoint = new PositionPredictorPoint(-1, availablePoints[count].Longitude, availablePoints[count].Latitude, availablePoints[count].Region);
				tmpPoint.Bearing = Bearing(this.latitude, this.longitude, availablePoints[count].Latitude, availablePoints[count].Longitude);
				tmpPoint.Label = availablePoints[count].Label;
				availablePoints[count] = tmpPoint;
			}
		}

		//check if thare are greater than two different bearings
		private bool DifferentBearingsGreaterThanTwo()
		{
			double bearing1 = availablePoints[0].Bearing;
			double bearing2 = -1;
			for(int i = 1; i < availablePoints.Length; i++)
			{
				if ((bearing2 == -1) && (availablePoints[i].Bearing != bearing1))
				{
					bearing2 = availablePoints[i].Bearing;
				}
				if ((availablePoints[i].Bearing != bearing1) && (availablePoints[i].Bearing != bearing2))
				{
					return true;
				}
			}
			return false;
		}

		//set predictor boudaries, maximum radius, longitude and latitude of central point
		//get points from database
		public void SetBoudaries(int newRadius, double newLongitude, double newLatitude)
		{
			radius = newRadius;
			radiusYInSeconds = newRadius/secondLength;
			radiusXInSeconds = radiusYInSeconds * (1/(float)Math.Cos(Math.PI * newLatitude / 648000.0)); //because of navigation deviance (648000 = 60*60*180)
			maxRadiusYInSeconds = newRadius/secondLength;
			maxRadiusXInSeconds = radiusYInSeconds * (1/(float)Math.Cos(Math.PI * newLatitude / 648000.0)); //because of navigation deviance (648000 = 60*60*180)
			longitude = newLongitude;
			latitude = newLatitude;
		}

		//build triangles and pies from result
		private void BuildTrianglesAndPies()
		{
			double sweepAngle = -1;
			double[] triangleStartPoints = new double[2];
			double[] triangleStopPoints = new double[2];
			double[] triangleStartPoints2 = new double[2];
			double[] triangleStopPoints2 = new double[2];

			//there is only circle
			if (availablePoints.Length == 0)
			{
				pies.Add(
					new PositionPredictorPie(this.longitude, this.latitude,
					this.radiusXInSeconds, this.radiusYInSeconds, 0, 360));
			}
			else
			{
				for (int i = 1; i < availablePoints.Length; i++)
				{
					if ((availablePoints[i].Region == availablePoints[i-1].Region) &&
						(availablePoints[i].Bearing == availablePoints[i-1].Bearing))
					{
						continue;
					}
					else if ((availablePoints[i].Region == availablePoints[i-1].Region) &&
						(Math.Abs(availablePoints[i].ID - availablePoints[i-1].ID) <= 1))
					{
						//add triangle
						triangles.Add(
							new PositionPredictorTriangle(this.longitude,                 this.latitude, 
							availablePoints[i].Longitude,   availablePoints[i].Latitude, 
							availablePoints[i-1].Longitude, availablePoints[i-1].Latitude));
					}
					else
					{
						triangleStartPoints = IntersectionBase(this.latitude, this.longitude, this.radiusYInSeconds,
							this.latitude, this.longitude, availablePoints[i-1].Latitude, availablePoints[i-1].Longitude);
						triangleStopPoints = IntersectionBase(this.latitude, this.longitude, this.radiusYInSeconds,
							this.latitude, this.longitude, availablePoints[i].Latitude, availablePoints[i].Longitude);
						if (IntersectWithSegment(triangleStartPoints[0], triangleStartPoints[1], availablePoints[i-1].Longitude, availablePoints[i-1].Latitude) ||
							(IntersectWithSegment(triangleStopPoints[0],  triangleStopPoints[1], availablePoints[i].Longitude,   availablePoints[i].Latitude)))
						{
							//add special triangle
							if (!(IntersectWithSegment(triangleStartPoints[0], triangleStartPoints[1], availablePoints[i-1].Longitude, availablePoints[i-1].Latitude)))
							{
								triangleStopPoints = CalculateIntersectionSegment(triangleStopPoints[0],  triangleStopPoints[1], availablePoints[i].Longitude, availablePoints[i].Latitude);
								triangles.Add(
									new PositionPredictorTriangle(this.longitude, this.latitude, 
									triangleStopPoints[0], triangleStopPoints[1], availablePoints[i-1].Longitude, availablePoints[i-1].Latitude));
								AddCallPoint(availablePoints[i]);
							}
							else if (!(IntersectWithSegment(triangleStopPoints[0],  triangleStopPoints[1], availablePoints[i].Longitude, availablePoints[i].Latitude)))
							{
								triangleStartPoints = CalculateIntersectionSegment(triangleStartPoints[0], triangleStartPoints[1], availablePoints[i-1].Longitude, availablePoints[i-1].Latitude);
								triangles.Add(
									new PositionPredictorTriangle(this.longitude, this.latitude, 
									availablePoints[i].Longitude, availablePoints[i].Latitude, triangleStartPoints[0], triangleStartPoints[1]));
								AddCallPoint(availablePoints[i-1]);
							}
							else
							{
								triangleStopPoints = CalculateIntersectionSegment(triangleStopPoints[0],  triangleStopPoints[1], availablePoints[i].Longitude, availablePoints[i].Latitude);
								triangleStartPoints = CalculateIntersectionSegment(triangleStartPoints[0], triangleStartPoints[1], availablePoints[i-1].Longitude, availablePoints[i-1].Latitude);
								if (IntersectWithSegmentWithPoint(triangleStopPoints[0], triangleStopPoints[1],availablePoints[i-1].Longitude, availablePoints[i-1].Latitude))
								{
									triangles.Add(
										new PositionPredictorTriangle(this.longitude, this.latitude, 
										triangleStopPoints[0], triangleStopPoints[1], availablePoints[i-1].Longitude, availablePoints[i-1].Latitude));
									AddCallPoint(availablePoints[i]);
								}
								else if (IntersectWithSegmentWithPoint(triangleStartPoints[0], triangleStartPoints[1],availablePoints[i].Longitude, availablePoints[i].Latitude))
								{
									triangles.Add(
										new PositionPredictorTriangle(this.longitude, this.latitude, 
										triangleStartPoints[0], triangleStartPoints[1], availablePoints[i].Longitude, availablePoints[i].Latitude));
									AddCallPoint(availablePoints[i-1]);
								}
								else
								{
									triangles.Add(
										new PositionPredictorTriangle(this.longitude, this.latitude, 
										triangleStartPoints[0], triangleStartPoints[1], triangleStopPoints[0], triangleStopPoints[1]));
									AddCallPoint(availablePoints[i-1]);
									AddCallPoint(availablePoints[i]);
								}
							}
						}
						else
						{
							//add pie
							sweepAngle = ((availablePoints[i].Bearing - availablePoints[i-1].Bearing) + 360) % 360;
							if (sweepAngle != 0)
							{
								pies.Add(
									new PositionPredictorPie(this.longitude, this.latitude,
									this.radiusXInSeconds, this.radiusYInSeconds, availablePoints[i-1].Bearing, sweepAngle));
								AddCallPoint(availablePoints[i-1]);
								AddCallPoint(availablePoints[i]);
							}
						}
					}
				}
				BuildTrianglesAndPiesEditPie();
				BuildTrianglesAndPiesIterative();
			}
		}

		//adds point to recurrent call predictor
		private void AddCallPoint(PositionPredictorPoint point)
		{
			if (point.Label != 'B')
			{
				return;
			}
			foreach(PositionPredictorPoint pointToCall in pointsToCall)
			{
				if (pointToCall.ID == point.ID)
				{
					return;
				}
			}
			pointsToCall.Add(point);
		}

		//edits pie if there is only one triangle
		//in such situation pie must have greater than 180 degrees
		private void BuildTrianglesAndPiesEditPie()
		{
			if ((pies.Count == 1) && (triangles.Count == 1))
			{
				if (((PositionPredictorPie)pies[0]).SweepAngle < 180)
				{
					((PositionPredictorPie)pies[0]).SweepAngle = ((PositionPredictorPie)pies[0]).SweepAngle - 360;
				}
			}

		}

		//check if new segment intersect with existing segments
		private bool IntersectWithSegment(double longitudeToCheck, double latitiudeToCheck)
		{
			return IntersectWithSegment(longitudeToCheck, latitiudeToCheck, longitudeToCheck, latitiudeToCheck);
		}

		//check if new segment intersects with existing segments
		private bool IntersectWithSegment(double longitudeToCheck, double latitiudeToCheck, double excludeLongitudeToCheck, double excludeLatitiudeToCheck)
		{
			PositionPredictorPoint previousPoint = new PositionPredictorPoint(-1, 0, 0, -1);
			foreach(PositionPredictorPoint point in points)
			{
				if ((point.Label != 'x') && (previousPoint.Label != 'x') && (point.Region == previousPoint.Region) &&
					((point.Longitude != excludeLongitudeToCheck) || (point.Latitude != excludeLatitiudeToCheck)) && 
					((previousPoint.Longitude != excludeLongitudeToCheck) || (previousPoint.Latitude != excludeLatitiudeToCheck)) && 
					((point.Longitude != longitudeToCheck) || (point.Latitude != latitiudeToCheck)) && 
					((previousPoint.Longitude != longitudeToCheck) || (previousPoint.Latitude != latitiudeToCheck)))
				{
					if ( (Math.Sign(DetForPoints(point.Longitude, point.Latitude, previousPoint.Longitude, previousPoint.Latitude, longitudeToCheck, latitiudeToCheck))
						!= Math.Sign(DetForPoints(point.Longitude, point.Latitude, previousPoint.Longitude, previousPoint.Latitude, this.longitude, this.latitude))) &&
						(Math.Sign(DetForPoints(this.longitude, this.latitude, longitudeToCheck, latitiudeToCheck, point.Longitude, point.Latitude))
						!= Math.Sign(DetForPoints(this.longitude, this.latitude, longitudeToCheck, latitiudeToCheck, previousPoint.Longitude, previousPoint.Latitude))))
					{
						return true;
					}
				}
				previousPoint = point;
			}
			return false;
		}

		//check if new segment intersects with existing segments with point(includeLongitudeToCheck, includeLatitiudeToCheck)
		private bool IntersectWithSegmentWithPoint(double longitudeToCheck, double latitiudeToCheck, double includeLongitudeToCheck, double includeLatitiudeToCheck)
		{
			PositionPredictorPoint previousPoint = new PositionPredictorPoint(-1, 0, 0, -1);
			foreach(PositionPredictorPoint point in points)
			{
				if ((point.Label != 'x') && (previousPoint.Label != 'x') && (point.Region == previousPoint.Region) &&
					(((point.Longitude == includeLongitudeToCheck) && (point.Latitude == includeLatitiudeToCheck)) || 
					((previousPoint.Longitude == includeLongitudeToCheck) && (previousPoint.Latitude == includeLatitiudeToCheck))) && 
					((point.Longitude != longitudeToCheck) || (point.Latitude != latitiudeToCheck)) && 
					((previousPoint.Longitude != longitudeToCheck) || (previousPoint.Latitude != latitiudeToCheck)))
				{
					if ( (Math.Sign(DetForPoints(point.Longitude, point.Latitude, previousPoint.Longitude, previousPoint.Latitude, longitudeToCheck, latitiudeToCheck))
						!= Math.Sign(DetForPoints(point.Longitude, point.Latitude, previousPoint.Longitude, previousPoint.Latitude, this.longitude, this.latitude))) &&
						(Math.Sign(DetForPoints(this.longitude, this.latitude, longitudeToCheck, latitiudeToCheck, point.Longitude, point.Latitude))
						!= Math.Sign(DetForPoints(this.longitude, this.latitude, longitudeToCheck, latitiudeToCheck, previousPoint.Longitude, previousPoint.Latitude))))
					{
						return true;
					}
					//close enought
					else if (Math.Abs(DetForPoints(point.Longitude, point.Latitude, previousPoint.Longitude, previousPoint.Latitude, longitudeToCheck, latitiudeToCheck)) <= 0.1)
					{
						return true;
					}
				}
				previousPoint = point;
			}
			return false;
		}

		//calculates the closest to central point, point of intersection of two segments
		private double[] CalculateIntersectionSegment(double longitudeToCheck, double latitiudeToCheck, double excludeLongitudeToCheck, double excludeLatitiudeToCheck)
		{
			PositionPredictorPoint previousPoint = new PositionPredictorPoint(-1, 0, 0, -1);
			double[] result = null;
			double[] tmpResult = new double[2];

			foreach(PositionPredictorPoint point in points)
			{
				if ((point.Label != 'x') && (previousPoint.Label != 'x') && (point.Region == previousPoint.Region) &&
					((point.Longitude != excludeLongitudeToCheck) || (point.Latitude != excludeLatitiudeToCheck)) && 
					((previousPoint.Longitude != excludeLongitudeToCheck) || (previousPoint.Latitude != excludeLatitiudeToCheck)) && 
					((point.Longitude != longitudeToCheck) || (point.Latitude != latitiudeToCheck)) && 
					((previousPoint.Longitude != longitudeToCheck) || (previousPoint.Latitude != latitiudeToCheck)))
				{
					if ( (Math.Sign(DetForPoints(point.Longitude, point.Latitude, previousPoint.Longitude, previousPoint.Latitude, longitudeToCheck, latitiudeToCheck))
						!= Math.Sign(DetForPoints(point.Longitude, point.Latitude, previousPoint.Longitude, previousPoint.Latitude, this.longitude, this.latitude))) &&
						(Math.Sign(DetForPoints(this.longitude, this.latitude, longitudeToCheck, latitiudeToCheck, point.Longitude, point.Latitude))
						!= Math.Sign(DetForPoints(this.longitude, this.latitude, longitudeToCheck, latitiudeToCheck, previousPoint.Longitude, previousPoint.Latitude))))
					{
						tmpResult = IntersectionSegment(this.longitude, this.latitude, longitudeToCheck, latitiudeToCheck,
							previousPoint.Longitude, previousPoint.Latitude, point.Longitude, point.Latitude);
						if (result == null)
						{
							result = tmpResult;
						}
						else if(Range(this.latitude, this.longitude, result[1], result[0]) > Range(this.latitude, this.longitude, tmpResult[1], tmpResult[0]))
						{
							result = tmpResult;
						}
					}
				}
				previousPoint = point;
			}
			return result;
		}

		// this function computes the intersection of the sent lines
		// and returns the intersection point, note that the function assumes
		// the lines intersect. the function can handle vertical as well
		// as horizontal lines. note the function isn't very clever, it simply
		//applies the math, but we don't need speed since this is a
		//pre-processing step
		//http://www.whisqu.se/per/docs/math28.htm
		private double[] IntersectionSegment(double x0,double y0,double x1,double y1, double x2,double y2,double x3,double y3)
		{
			double[] result = new double[2];
			double a1, b1, c1, a2, b2, c2,	// constants of linear equations
				det_inv,					// the inverse of the determinant of the coefficient	matrix
				m1,m2;						// the slopes of each line
			// compute slopes, note the cludge for infinity, however, this will be close enough
			if ((x1-x0)!=0)
				m1 = (y1-y0)/(x1-x0);
			else
				m1 = (double)1e+10;   // close enough to infinity

			if ((x3-x2)!=0)
				m2 = (y3-y2)/(x3-x2);
			else
				m2 = (double)1e+10;   // close enough to infinity

			// compute constants
			a1 = m1;
			a2 = m2;
			b1 = -1;
			b2 = -1;
			c1 = (y0 - m1 * x0);
			c2 = (y2 - m2 * x2);

			// compute the inverse of the determinate
			det_inv = 1 / ((a1 * b2) - (a2 * b1));

			// use Kramers rule to compute xi and yi
			result[0] = ((b1*c2 - b2*c1)*det_inv);
			result[1] = ((a2*c1 - a1*c2)*det_inv);
			return result;
		}

		//calculate determinant for three points
		private double DetForPoints(double x1, double y1, double x2, double y2, double x3, double y3)
		{
			return ((x1*y2) + (x2*y3) + (x3*y1) - (x3*y2) - (x1*y3) - (x2*y1));
		}

		//call algorithm recurrent if needed 
		private void BuildTrianglesAndPiesIterative()
		{
			foreach(PositionPredictorPoint point in pointsToCall)
			{
				ArrayList allCalledPoints = new ArrayList();
				allCalledPoints.AddRange(calledPoints);
				allCalledPoints.Add(point);
				CallCalculate(point, allCalledPoints);
			}
		}


		//call iterative calculate
		private bool CallCalculate(PositionPredictorPoint point, ArrayList allCalledPoints)
		{
			foreach (PositionPredictorPoint calledPoint in calledPoints)
			{
				if (calledPoint.ID == point.ID)
				{
					return false;
				}
			}

			int newRadius;
			double newLongitude, newLatitude;
			double angle = Math.PI * Bearing(this.latitude, this.longitude, point.Latitude, point.Longitude) / 180.0;

			newLongitude = point.Longitude + Math.Cos(angle);
			newLatitude = point.Latitude + Math.Sin(angle);
			newRadius = radius - (int)Math.Round(Range(this.latitude, this.longitude, newLatitude, newLongitude));
			if (newRadius > 0)
			{
				PositionPredictor predictor = new PositionPredictor(null, allCalledPoints);
				Console.WriteLine("R={0} {1} {2} {3} {4} {5}", newRadius, newLongitude, newLatitude, this.longitude, this.latitude, allCalledPoints.Count);
				predictor.Calculate(newRadius, newLongitude, newLatitude, points);
				pies.AddRange(predictor.GetPies());
				triangles.AddRange(predictor.GetTriangles());
				return true;
			}
			return false;
		}

		//get triangles from result
		public PositionPredictorTriangle[] GetTriangles()
		{
			PositionPredictorTriangle[] result = new PositionPredictorTriangle[triangles.Count];
			for (int i = 0; i < triangles.Count; i++)
			{
				result[i] = (PositionPredictorTriangle) triangles[i];
			}

			return result;
		}

		//get pies from result
		public PositionPredictorPie[] GetPies()
		{
			PositionPredictorPie[] result = new PositionPredictorPie[pies.Count];
			for (int i = 0; i < pies.Count; i++)
			{
				result[i] = (PositionPredictorPie) pies[i];
			}
			return result;
		}


		//avaialabilitysurface
		//radiuses - array of distances (non descending)
		//probabilities - array of probabilties
		//    radiuses        probabilities
		//     3000                25
		//     3500                35
		//     4200                10
		public void Calculate(int radius)
		{	
			calledPoints.Clear();
			pointsToCall.Clear();
			pies.Clear();
			triangles.Clear();
			points = (ArrayList)oryginalPoints.Clone();
			radius = radius;
			radiusYInSeconds = radius/secondLength;
			radiusXInSeconds = radiusYInSeconds * (1/(float)Math.Cos(Math.PI * latitude / 648000.0)); //because of navigation deviance (648000 = 60*60*180)
			this.CalculateBasePoints();
			this.CalculateAdditionalPoints();
			this.CalculateSpecialPoints();
			this.CalculateAvailablePoints();
			this.BuildTrianglesAndPies();
		}

		//calculate function for recurrent call inside class
		public void Calculate(int newRadius, double newLongitude, double newLatitude, ArrayList newPoints)
		{
			PositionPredictorPoint newPoint;
			points = new ArrayList();
			for(int i = 0; i < newPoints.Count; i++)
			{
				newPoint = (PositionPredictorPoint)newPoints[i];
				if (newPoint.Label == 'x' || newPoint.Label == 'B')
				{
					points.Add(new PositionPredictorPoint(newPoint.ID, newPoint.Longitude, newPoint.Latitude, newPoint.Region));
				}
			}
			radius = newRadius;
			longitude = newLongitude;
			latitude = newLatitude;
			radiusYInSeconds = radius/secondLength;
			radiusXInSeconds = radiusYInSeconds * (1/(float)Math.Cos(Math.PI * latitude / 648000.0)); //because of navigation deviance (648000 = 60*60*180)
			maxRadiusYInSeconds = radius/secondLength;
			maxRadiusXInSeconds = radiusYInSeconds * (1/(float)Math.Cos(Math.PI * latitude / 648000.0)); //because of navigation deviance (648000 = 60*60*180)
			this.CalculateBasePoints();
			this.CalculateAdditionalPoints();
			this.CalculateSpecialPoints();
			this.CalculateAvailablePoints();
			this.BuildTrianglesAndPies();
		}
	}
}
Dodaj komentarz