GeometryCalculator.cs 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Windows;
  4. using System.Linq;
  5. using System.Text;
  6. using System.Threading.Tasks;
  7. namespace SketchAssistantWPF
  8. {
  9. /// <summary>
  10. /// A class that contains all algorithms related to geometry.
  11. /// </summary>
  12. public static class GeometryCalculator
  13. {
  14. /// <summary>
  15. /// Calculate the approximate similarity of two lines.
  16. /// Using three weighted parameters to calculate a value between 0 and 1 to indicate the similarity of the lines.
  17. /// </summary>
  18. /// <param name="line0">The first line.</param>
  19. /// <param name="line1">The second line.</param>
  20. /// <returns>The similarity of the two lines.</returns>
  21. public static double CalculateSimilarity(InternalLine line0, InternalLine line1)
  22. {
  23. double CosSim = Math.Abs(CalculateAverageCosineSimilarity(line0, line1));
  24. double LenSim = CalculateLengthSimilarity(line0, line1);
  25. double AvDist = CalculateAverageDistance(line0, line1);
  26. double DistSim = (50 - AvDist) / 50;
  27. if (DistSim < 0) DistSim = 0;
  28. if (CosSim < 0.5 || Double.IsNaN(CosSim)) CosSim = 0;
  29. double output = (2 * CosSim + LenSim + DistSim) / 4;
  30. System.Diagnostics.Debug.WriteLine("Results: CosSim: {0}, LenSim: {1}, AvDist {2}, DistSim: {3}. Total: {4}",
  31. CosSim, LenSim, AvDist, DistSim, output);
  32. return output;
  33. }
  34. /// <summary>
  35. /// The cosine similarity of two vectors.
  36. /// </summary>
  37. /// <param name="v0">The first vector</param>
  38. /// <param name="v1">The second vector</param>
  39. /// <returns>The cosine similarity</returns>
  40. private static double CosineSimilarity(Vector v0, Vector v1)
  41. {
  42. return (v0.X * v1.X + v0.Y * v1.Y) / (Math.Sqrt(v0.X * v0.X + v0.Y * v0.Y) * Math.Sqrt(v1.X * v1.X + v1.Y * v1.Y));
  43. }
  44. /// <summary>
  45. /// An approximate calculation of the average cosine similarity
  46. /// of two lines, achieved by calculating the cosine similarity of subvectors.
  47. /// </summary>
  48. /// <param name="line0">The first line</param>
  49. /// <param name="line1">The second line</param>
  50. /// <returns>The approximate average cosine similarity of all subvectors</returns>
  51. public static double CalculateAverageCosineSimilarity(InternalLine line0, InternalLine line1)
  52. {
  53. //check if one of the lines is a point, or both lines are points
  54. if ((line0.isPoint && !line1.isPoint) || (line1.isPoint && !line0.isPoint)) return 0;
  55. else if (line0.isPoint && line1.isPoint) return 1;
  56. List<Point> points0 = line0.GetPoints();
  57. List<Point> points1 = line1.GetPoints();
  58. if (points0.Count == points1.Count)
  59. {
  60. //If the two lists have an equal amount of subvectors,
  61. //compare the nth subvectors from each list and average the value.
  62. double sum = 0; int i = 0;
  63. List<Point> shortL = points0; List<Point> longL = points1;
  64. for (; i < shortL.Count - 1; i++)
  65. {
  66. if (i + 1 == shortL.Count || i + 1 == longL.Count) break;
  67. Vector v0 = new Vector(shortL[i + 1].X - shortL[i].X, shortL[i + 1].Y - shortL[i].Y);
  68. Vector v1 = new Vector(longL[i + 1].X - longL[i].X, longL[i + 1].Y - longL[i].Y);
  69. sum += CosineSimilarity(v0, v1);
  70. }
  71. return sum / i;
  72. }
  73. else
  74. {
  75. //Determine if the longer list is of similar length or contains significatly more items
  76. List<Point> shortL = points0; List<Point> longL = points0;
  77. if (points0.Count < points1.Count) { longL = points1; }
  78. if (points0.Count > points1.Count) { shortL = points1;}
  79. double dif = (longL.Count - 1) / (shortL.Count - 1);
  80. if(dif > 1)
  81. {
  82. //The longer list is significantly longer
  83. //Each element in the shorter list is compared to multiple
  84. // elements in the longer list to make up the difference
  85. double sum = 0; int adds = 0;
  86. for (int i = 0; i < shortL.Count - 1; i++)
  87. {
  88. if (i + 1 == shortL.Count) break;
  89. for (int j = 0; j <= dif; j++)
  90. {
  91. var k = i + j;
  92. if (k + 1 == longL.Count) break;
  93. Vector v0 = new Vector(shortL[i + 1].X - shortL[i].X, shortL[i + 1].Y - shortL[i].Y);
  94. Vector v1 = new Vector(longL[k + 1].X - longL[k].X, longL[k + 1].Y - longL[k].Y);
  95. sum += CosineSimilarity(v0, v1); adds++;
  96. }
  97. }
  98. return sum / adds;
  99. }
  100. else
  101. {
  102. //The longer list is almost the same length as the shorter list
  103. //The remaining items are simply skipped
  104. double sum = 0; int i = 0;
  105. for (; i < shortL.Count - 1; i++)
  106. {
  107. if (i + 1 == shortL.Count || i + 1 == longL.Count) break;
  108. Vector v0 = new Vector(shortL[i + 1].X - shortL[i].X, shortL[i + 1].Y - shortL[i].Y);
  109. Vector v1 = new Vector(longL[i + 1].X - longL[i].X, longL[i + 1].Y - longL[i].Y);
  110. sum += CosineSimilarity(v0, v1);
  111. }
  112. return sum / i;
  113. }
  114. }
  115. }
  116. /// <summary>
  117. /// Calculate the similarity in length of two Lines.
  118. /// </summary>
  119. /// <param name="line0">The first line.</param>
  120. /// <param name="line1">The second line.</param>
  121. /// <returns>How similar the lines are in length.</returns>
  122. private static double CalculateLengthSimilarity(InternalLine line0, InternalLine line1)
  123. {
  124. double len0 = line0.GetLength(); double len1 = line1.GetLength();
  125. var dif = Math.Abs(len1 - len0);
  126. if (dif == 0) return 1;
  127. double shorter;
  128. if (len1 > len0) shorter = len0;
  129. else shorter = len1;
  130. if (dif >= shorter) return 0;
  131. return (shorter - dif )/shorter;
  132. }
  133. /// <summary>
  134. /// Calculate the average distance between the ends of two lines.
  135. /// </summary>
  136. /// <param name="line0">The first line.</param>
  137. /// <param name="line1">The second line.</param>
  138. /// <returns>The shortest average distance between the ends of the lines.</returns>
  139. private static double CalculateAverageDistance(InternalLine line0, InternalLine line1)
  140. {
  141. List<Point> points0 = line0.GetPoints();
  142. List<Point> points1 = line1.GetPoints();
  143. double distfirstfirst = Math.Sqrt(Math.Pow((points0[0].X - points1[0].X) , 2) + Math.Pow((points0[0].Y - points1[0].Y) , 2));
  144. double distlastlast = Math.Sqrt(Math.Pow((points0.Last().X - points1.Last().X), 2) + Math.Pow((points0.Last().Y - points1.Last().Y), 2));
  145. double distfirstlast = Math.Sqrt(Math.Pow((points0[0].X - points1.Last().X), 2) + Math.Pow((points0[0].Y - points1.Last().Y), 2));
  146. double distlastfirst = Math.Sqrt(Math.Pow((points0.Last().X - points1[0].X), 2) + Math.Pow((points0.Last().Y - points1[0].Y), 2));
  147. if ((distfirstfirst + distlastlast) / 2 < (distfirstlast + distlastfirst) / 2) return (distfirstfirst + distlastlast) / 2;
  148. else return (distfirstlast + distlastfirst) / 2;
  149. }
  150. /// <summary>
  151. /// A simple algorithm that returns a filled circle with a radius and a center point.
  152. /// </summary>
  153. /// <param name="center">The center point of the alorithm </param>
  154. /// <param name="radius">The radius of the circle, if its less or equal to 1
  155. /// only the center point is returned. </param>
  156. /// <returns>All the points in or on the circle.</returns>
  157. public static HashSet<Point> FilledCircleAlgorithm(Point center, int radius)
  158. {
  159. HashSet<Point> returnSet = new HashSet<Point> { center };
  160. //Fill the circle
  161. for (int x = 0; x < radius; x++)
  162. {
  163. for (int y = 0; y < radius; y++)
  164. {
  165. //Check if point is on or in the circle
  166. if ((x * x + y * y - radius * radius) <= 0)
  167. {
  168. returnSet.Add(new Point(center.X + x, center.Y + y));
  169. returnSet.Add(new Point(center.X - x, center.Y + y));
  170. returnSet.Add(new Point(center.X + x, center.Y - y));
  171. returnSet.Add(new Point(center.X - x, center.Y - y));
  172. }
  173. }
  174. }
  175. return returnSet;
  176. }
  177. /// <summary>
  178. /// An implementation of the Bresenham Line Algorithm,
  179. /// which calculates all points between two points in a straight line.
  180. /// Implemented using the pseudocode on Wikipedia.
  181. /// </summary>
  182. /// <param name="p0">The start point</param>
  183. /// <param name="p1">The end point</param>
  184. /// <returns>All points between p0 and p1 (including p0 and p1)</returns>
  185. public static List<Point> BresenhamLineAlgorithm(Point p0, Point p1)
  186. {
  187. int p1x = (int)p1.X;
  188. int p1y = (int)p1.Y;
  189. int p0x = (int)p0.X;
  190. int p0y = (int)p0.Y;
  191. int deltaX = p1x - p0x;
  192. int deltaY = p1y - p0y;
  193. List<Point> returnList;
  194. if (Math.Abs(deltaY) < Math.Abs(deltaX))
  195. {
  196. if (p0.X > p1.X)
  197. {
  198. returnList = GetLineLow(p1x, p1y, p0x, p0y);
  199. returnList.Reverse();
  200. }
  201. else
  202. {
  203. returnList = GetLineLow(p0x, p0y, p1x, p1y);
  204. }
  205. }
  206. else
  207. {
  208. if (p0.Y > p1.Y)
  209. {
  210. returnList = GetLineHigh(p1x, p1y, p0x, p0y);
  211. returnList.Reverse();
  212. }
  213. else
  214. {
  215. returnList = GetLineHigh(p0x, p0y, p1x, p1y);
  216. }
  217. }
  218. return returnList;
  219. }
  220. /// <summary>
  221. /// Helping function of the Bresenham Line algorithm,
  222. /// under the assumption that abs(deltaY) is smaller than abs(deltX)
  223. /// and x0 is smaller than x1
  224. /// </summary>
  225. /// <param name="x0">x value of point 0</param>
  226. /// <param name="y0">y value of point 0</param>
  227. /// <param name="x1">x value of point 1</param>
  228. /// <param name="y1">y value of point 1</param>
  229. /// <returns>All points on the line between the two points</returns>
  230. private static List<Point> GetLineLow(int x0, int y0, int x1, int y1)
  231. {
  232. List<Point> returnList = new List<Point>();
  233. int dx = x1 - x0;
  234. int dy = y1 - y0;
  235. int yi = 1;
  236. if (dy < 0)
  237. {
  238. yi = -1;
  239. dy = -dy;
  240. }
  241. int D = 2 * dy - dx;
  242. int y = y0;
  243. for (int x = x0; x <= x1; x++)
  244. {
  245. returnList.Add(new Point(x, y));
  246. if (D > 0)
  247. {
  248. y = y + yi;
  249. D = D - 2 * dx;
  250. }
  251. D = D + 2 * dy;
  252. }
  253. return returnList;
  254. }
  255. /// <summary>
  256. /// Helping function of the Bresenham Line algorithm,
  257. /// under the assumption that abs(deltaY) is larger or equal than abs(deltX)
  258. /// and y0 is smaller than y1
  259. /// </summary>
  260. /// <param name="x0">x value of point 0</param>
  261. /// <param name="y0">y value of point 0</param>
  262. /// <param name="x1">x value of point 1</param>
  263. /// <param name="y1">y value of point 1</param>
  264. /// <returns>All points on the line between the two points</returns>
  265. private static List<Point> GetLineHigh(int x0, int y0, int x1, int y1)
  266. {
  267. List<Point> returnList = new List<Point>();
  268. int dx = x1 - x0;
  269. int dy = y1 - y0;
  270. int xi = 1;
  271. if (dx < 0)
  272. {
  273. xi = -1;
  274. dx = -dx;
  275. }
  276. int D = 2 * dx - dy;
  277. int x = x0;
  278. for (int y = y0; y <= y1; y++)
  279. {
  280. returnList.Add(new Point(x, y));
  281. if (D > 0)
  282. {
  283. x = x + xi;
  284. D = D - 2 * dy;
  285. }
  286. D = D + 2 * dx;
  287. }
  288. return returnList;
  289. }
  290. }
  291. }