Source: sketch.js

  1. /*******************************************************************************
  2. *
  3. *	@file sketch.js
  4. *	@brief A quick sketch showing different methods of generating a convexhull
  5. *
  6. *	@author <a href='mailto:omareq08@gmail.com'> Omar Essilfie-Quaye </a>
  7. *	@version 1.0
  8. *	@date 27-July-2019
  9. *
  10. *******************************************************************************/
  12. let resetButton;
  14. /**
  15. *	Variable that store how far away from the side edges new points can spawn
  16. *
  17. *	@type {Integer}
  18. */
  19. let xBuffer;
  21. /**
  22. *	Variable that store how far away from the top and bottom edges new points
  23. *	can spawn
  24. *
  25. *	@type {Integer}
  26. */
  27. let yBuffer;
  29. /**
  30. *	Enumeration of the different algorithm types
  31. *
  32. *	@enum {String}
  33. */
  34. const algorithms = Object.freeze({
  35. 	MONOTONE: "Monotone Chain",
  36. 	JARVIS: "Jarvis March",
  37. 	DIVIDE: "Divide & Conquer",
  38. 	GRAHAM: "Graham Scan"
  39. });
  41. /**
  42. *	Variable that stores the current algorithm tha is being executed
  43. *
  44. *	@type {Enum<String>}
  45. */
  46. let algorithm = algorithms.JARVIS;
  48. /**
  49. *	Pointer for the number of points slider in the DOM
  50. *
  51. *	@type {p5.Element}
  52. */
  53. let pointsSlider;
  55. /**
  56. *	Number of points to be bound by the generated convex hull
  57. *
  58. *	@type {Integer}
  59. */
  60. let numPoints = 45;
  62. /**
  63. *	Pointer for the paragraph which shows the number of points in the DOM
  64. *
  65. *	@type {p5.Element}
  66. */
  67. let pointsDisplay;
  69. /**
  70. *	Size of the points drawn on the canvas
  71. *
  72. *	@type {Integer}
  73. */
  74. let pointRadius = 10;
  76. /**
  77. *	Pointer to select field that selects the executing algorithm
  78. *
  79. *	@type {p5.Element}
  80. */
  81. let selectAlgorithm;
  84. /**
  85. *	Pointer to select field that selects the method that is used to split the
  86. *	points when divide and conquer is running
  87. *
  88. *	@type {p5.Element}
  89. */
  90. let selectSplitMethod;
  92. /**
  93. *	Pointer to select field that selects the direction that the Jarvis march
  94. *	algorithm finds theconvex hull
  95. *
  96. *	@type {p5.Element}
  97. */
  98. let selectAngularDirection;
  100. /**
  101. *	Reset all algorithm variables to initial values
  102. */
  103. function reset() {
  104. 	hull = [];
  105. 	jarvisStep = 0;
  106. 	leftPointIndex = 0;;
  107. 	currentIndex = -1;
  108. 	nextIndex = 1;
  109. 	index = 2;
  110. 	time = 0;
  112. 	internalHulls = [[], [], []];
  113. 	finalHull = [];
  114. 	finalPoints = [];
  115. 	lower = [];
  116. 	upper = [];
  118. 	divideStep = divideSteps.SPLIT;
  119. 	jarvisStep = jarvisSteps.LEFT;
  120. 	monotoneStep = monotoneSteps.SORT;
  121. 	grahamStep = grahamSteps.SORT;
  123. 	points = [];
  124. 	for(let i = 0; i < numPoints; ++i) {
  125. 		const x = random(xBuffer, width - xBuffer);
  126. 		const y = random(yBuffer, height - yBuffer);
  127. 		const newPoint = createVector(x, y);
  128. 		points.push(newPoint);
  129. 	}
  130. }
  132. /**
  133. *	Changes the algorithm depending on what the value of the selectAlgorithm
  134. *	element is
  135. */
  136. function algorithmSelectEvent() {
  137. 	let selectVal = selectAlgorithm.value();
  138. 	if(selectVal != algorithm) {
  139. 		algorithm = selectVal;
  140. 	}
  142. 	if(algorithm == algorithms.DIVIDE) {
  143. 		selectSplitMethod.show();
  144. 	} else {
  145. 		selectSplitMethod.hide();
  146. 	}
  148. 	if(algorithm == algorithms.JARVIS) {
  149. 		selectAngularDirection.show();
  150. 	} else {
  151. 		selectAngularDirection.hide();
  152. 	}
  154. 	if(algorithm == algorithms.MONOTONE) {
  155. 		// show monotone chain options
  156. 	} else {
  157. 		// hide monotone chain options
  158. 	}
  160. 	if(algorithm == algorithms.GRAHAM) {
  161. 		// show graham scan options
  162. 	} else {
  163. 		// hide graham scan options
  164. 	}
  166. 	reset();
  167. }
  169. /**
  170. *	Changes the method for splitting the points in divide and conquer depending
  171. *	on the value of the selectSplitMethod element
  172. */
  173. function splitSelectEvent() {
  174. 	selectVal = selectSplitMethod.value();
  175. 	if(selectVal != splitMethod) {
  176. 		splitMethod = selectVal;
  177. 		reset();
  178. 	}
  179. }
  181. /**
  182. *	Changes the direction the jarvis march algorithm selects new points for the
  183. *	convex hull depending on the value of the selectAngularDirection element
  184. */
  185. function angularSelectEvent() {
  186. 	selectVal = selectAngularDirection.value();
  187. 	if(selectVal != angularDirection) {
  188. 		angularDirection = selectVal;
  189. 		reset();
  190. 	}
  191. }
  193. /**
  194. *	Draws a convex hull with a given colour
  195. *
  196. *	@param hullArray {Array<p5.Vector>} Array of points that amke up the
  197. *		verticies of the hull.
  198. *
  199. *	@param colour {Integer} Value of the hue of the given hull from 0 to 100
  200. */
  201. function drawHull(hullArray, colour) {
  202. 	push();
  203. 	colorMode(HSB, 100);
  204. 	fill(colour, 100, 100, 50);
  205. 	beginShape();
  206. 	for (let i = hullArray.length - 1; i >= 0; i--) {
  207. 		push();
  208. 		stroke(colour, 100,100);
  209. 		strokeWeight(0.3 * pointRadius);
  210. 		ellipse(hullArray[i].x, hullArray[i].y, pointRadius, pointRadius);
  211. 		vertex(hullArray[i].x, hullArray[i].y);
  212. 		pop();
  213. 	}
  214. 	endShape(CLOSE);
  215. 	colorMode(RGB);
  216. 	pop();
  217. }
  219. /**
  220. *	Draws the edges of a convex hull with a given colour
  221. *
  222. *	@param hullArray {Array<p5.Vector>} Array of points that amke up the
  223. *		verticies of the hull.
  224. *
  225. *	@param colour {Integer} Value of the hue of the given hull from 0 to 100
  226. */
  227. function drawEdges(hullArray, colour) {
  228. 	push();
  229. 	colorMode(HSB, 100);
  230. 	stroke(colour, 100, 100, 50);
  231. 	strokeWeight(0.3 * pointRadius);
  232. 	noFill();
  233. 	beginShape();
  234. 	for (let i = hullArray.length - 1; i >= 0; i--) {
  235. 		ellipse(hullArray[i].x, hullArray[i].y, pointRadius, pointRadius);
  236. 		vertex(hullArray[i].x, hullArray[i].y);
  237. 	}
  238. 	endShape();
  239. 	colorMode(RGB);
  240. 	pop();
  241. }
  243. /**
  244. *   p5.js setup function, creates canvas.
  245. */
  246. function setup() {
  247. 	let cnvSize;
  248. 	if(windowWidth > windowHeight) {
  249. 		cnvSize = 0.95 * windowHeight;
  250. 	} else {
  251. 		cnvSize = 0.6 * windowWidth;
  252. 	}
  253. 	let cnv = createCanvas(cnvSize, 0.7 * cnvSize);
  254. 	cnv.parent("sketch");
  256. 	pointsSlider = createSlider(12, 100, numPoints, 1);
  257. 	pointsSlider.parent("num-points");
  259. 	pointsDisplay = createP(numPoints);
  260. 	pointsDisplay.parent("points-val");
  262. 	selectAlgorithm = createSelect();
  263. 	selectAlgorithm.parent("algorithm");
  264. 	selectAlgorithm.option(algorithms.JARVIS);
  265. 	selectAlgorithm.option(algorithms.DIVIDE);
  266. 	selectAlgorithm.option(algorithms.MONOTONE);
  267. 	selectAlgorithm.option(algorithms.GRAHAM);
  268. 	selectAlgorithm.changed(algorithmSelectEvent);
  270. 	selectAngularDirection = createSelect();
  271. 	selectAngularDirection.parent("algorithm-options");
  272. 	selectAngularDirection.option(direction.CLOCKWISE);
  273. 	selectAngularDirection.option(direction.ANTICLOCKWISE);
  274. 	selectAngularDirection.changed(angularSelectEvent);
  275. 	selectAngularDirection.hide();
  277. 	selectSplitMethod = createSelect();
  278. 	selectSplitMethod.parent("algorithm-options");
  279. 	selectSplitMethod.option(splitMethods.HORIZONTAL);
  280. 	selectSplitMethod.option(splitMethods.VERTICAL);
  281. 	selectSplitMethod.option(splitMethods.RADIAL);
  282. 	selectSplitMethod.changed(splitSelectEvent);
  283. 	selectSplitMethod.hide();
  284. //TODO (omar: omareq08@gmail.com): ANGULAR split method for dnc notworking
  285. 	// selectSplitMethod.option(splitMethods.ANGULAR);
  287. 	resetButton = createButton("Reset", "value");
  288. 	resetButton.parent("reset-button");
  289. 	resetButton.mousePressed(reset);
  291. 	xBuffer = 0.05 * width;
  292. 	yBuffer = 0.05 * height;
  294. 	for(let i = 0; i < numPoints; ++i) {
  295. 		const x = random(xBuffer, width - xBuffer);
  296. 		const y = random(yBuffer, height - yBuffer);
  297. 		const newPoint = createVector(x, y);
  298. 		points.push(newPoint);
  299. 	}
  300. }
  302. /**
  303. *   p5.js draw function, is run every frame to create the desired animation
  304. */
  305. function draw() {
  306. 	background(0);
  307. 	fill(255);
  308. 	textSize(height * 0.03);
  309. 	textAlign(LEFT, TOP);
  310. 	noStroke();
  311. 	text(algorithm, 0, 0);
  313. 	let sliderVal = pointsSlider.value();
  314. 	if(sliderVal != numPoints) {
  315. 		numPoints = sliderVal;
  316. 		pointsDisplay.elt.innerText = "Number of Points: " + str(numPoints);
  317. 		reset();
  318. 	}
  320. 	for (var i = points.length - 1; i >= 0; i--) {
  321. 		ellipse(points[i].x, points[i].y, pointRadius, pointRadius);
  322. 	}
  324. 	switch(algorithm) {
  325. 		case algorithms.JARVIS:
  326. 		jarvisMarch();
  327. 		break;
  329. 		case algorithms.MONOTONE:
  330. 		monotoneChain();
  331. 		break;
  333. 		case algorithms.DIVIDE:
  334. 		divideAndConquer();
  335. 		break;
  337. 		case algorithms.GRAHAM:
  338. 		grahamScan();
  339. 		break;
  341. 		default:
  342. 		background(255);
  343. 		break;
  344. 	}
  345. }

Documentation generated by JSDoc 3.6.3 on Sun Jun 05 2022 20:10:36 GMT+0100 (BST)