Posted By

jatkins on 08/11/14


Tagged

algorithm graphics Fill polygon evenoddrule


Versions (?)

Polygon fill example with even-odd rule


 / Published in: JavaScript
 

PRIVATE.

  1. <!DOCTYPE html>
  2. <html lang="en">
  3. <head>
  4. <title>Vector Fill Test</title>
  5. <script type="text/javascript">
  6. //<![CDATA[
  7. function vectorFillTest() {
  8. var canvasEl = document.createElement('canvas'),
  9. ctx = canvasEl.getContext('2d');
  10.  
  11. function getPixel(x, y) {
  12. if(!(isNaN(x) || isNaN(y)))
  13. return ctx.getImageData(Math.round(x), Math.round(y), 1, 1);
  14. };
  15.  
  16. function putPixel(x, y, r, g, b, a) {
  17. var pixel = getPixel(x, y);
  18.  
  19. if(pixel) {
  20. pixel.data[0] = r || pixel.data[0];
  21. pixel.data[1] = g || pixel.data[1];
  22. pixel.data[2] = b || pixel.data[2];
  23. pixel.data[3] = a || pixel.data[3];
  24.  
  25. ctx.putImageData(pixel, Math.round(x), Math.round(y));
  26. }
  27. }
  28.  
  29. function renderTestPixel(x, y, color) {
  30. var testPixel = document.createElement('div');
  31. testPixel.style.zIndex = '1000';
  32. testPixel.style.position = 'absolute';
  33. testPixel.style.left = x + canvasEl.offsetLeft + 'px';
  34. testPixel.style.top = y + canvasEl.offsetTop + 'px';
  35. testPixel.style.background = color;
  36. testPixel.style.width = '3px';
  37. testPixel.style.height = '3px';
  38.  
  39. document.getElementById('testPixels').appendChild(testPixel);
  40. }
  41.  
  42. function drawLine(startPoint, endPoint) {
  43. ctx.beginPath();
  44. ctx.moveTo(startPoint.x, startPoint.y);
  45. ctx.lineTo(endPoint.x, endPoint.y);
  46. ctx.closePath();
  47. ctx.stroke();
  48. }
  49.  
  50. function pointInPolygon(x, y) {
  51. var intersectionCount = 0;
  52.  
  53. if(typeof pointsByY['_' + y] != 'undefined') {
  54. for(var xIndex = 0; xIndex < pointsByY['_' + y].length; xIndex++) {
  55. if(pointsByY['_' + y][xIndex] > x)
  56. intersectionCount++;
  57. }
  58. }
  59.  
  60. return intersectionCount % 2 == 1; // per even-odd rule, true = odd = inside, false = even = outside
  61. }
  62.  
  63. canvasEl.style.margin = '10px';
  64. canvasEl.style.border = '1px solid #d3d3d3';
  65. canvasEl.width = 640;
  66. canvasEl.height = 480;
  67. canvasEl.style.width = '640px';
  68. canvasEl.style.height = '480px';
  69.  
  70. var actionState,
  71. polygonPoints = [],
  72. polygons = {},
  73. totalPolygonsCreated = 0,
  74. pointsByY = {},
  75. idOfHandleBeingDragged,
  76. prevCursorPoint,
  77. adjustingPolygon;
  78.  
  79. canvasEl.onmousedown = function(e) {
  80. if(actionState == 'drawing' && e.button == 2) { // currently drawing + right-click, so close polygon
  81. polygonPoints.push({x: parseInt(polygonPoints[0].x), y: parseInt(polygonPoints[0].y)}); // repeat first point at end of array to close polygon
  82.  
  83. totalPolygonsCreated++;
  84. var newPolygonKey = '_' + totalPolygonsCreated;
  85. polygons[newPolygonKey] = {lineSegments: []},
  86. handleContainerForThisPolygon = document.createElement('div');
  87.  
  88. //canvasEl.width = canvasEl.width; // clears canvas
  89.  
  90. // what about gradient=0/infinity lines?
  91. var xS = [], yS = [];
  92. for(var pP = 0; pP < polygonPoints.length - 1; pP++) {
  93. var newLineSegment = {
  94. minX: parseInt(Math.min(polygonPoints[pP].x, polygonPoints[pP + 1].x)),
  95. maxX: parseInt(Math.max(polygonPoints[pP].x, polygonPoints[pP + 1].x)),
  96. minY: parseInt(Math.min(polygonPoints[pP].y, polygonPoints[pP + 1].y)),
  97. maxY: parseInt(Math.max(polygonPoints[pP].y, polygonPoints[pP + 1].y)),
  98. gradient: (polygonPoints[pP + 1].y - polygonPoints[pP].y) / (polygonPoints[pP + 1].x - polygonPoints[pP].x),
  99. startPoint: {x: parseInt(polygonPoints[pP].x), y: parseInt(polygonPoints[pP].y)},
  100. endPoint: {x: parseInt(polygonPoints[pP + 1].x), y: parseInt(polygonPoints[pP + 1].y)}
  101. };
  102.  
  103. newLineSegment.yIntercept = polygonPoints[pP].y - newLineSegment.gradient * polygonPoints[pP].x;
  104. polygons[newPolygonKey].lineSegments.push(newLineSegment);
  105.  
  106. xS.push(polygonPoints[pP].x, polygonPoints[pP + 1].x);
  107. yS.push(polygonPoints[pP].y, polygonPoints[pP + 1].y);
  108.  
  109. var newHandle = document.createElement('div');
  110. newHandle.id = 'handle' + pP;
  111. newHandle.style.background = 'white';
  112. newHandle.style.border = '1px solid black';
  113. newHandle.style.width = '5px';
  114. newHandle.style.height = '5px';
  115. newHandle.style.borderRadius = '5px';
  116. newHandle.style.position = 'absolute';
  117. newHandle.style.left = canvasEl.offsetLeft + polygonPoints[pP].x - 2.5 + 'px';
  118. newHandle.style.top = canvasEl.offsetTop + polygonPoints[pP].y - 2.5 + 'px';
  119. newHandle.onmousedown = function(e) {
  120. cumXDiff = 0;
  121. cumYDiff = 0;
  122.  
  123. adjustingPolygon = true;
  124. idOfHandleBeingDragged = this.id;
  125. prevCursorPoint = {x: parseInt(e.pageX - canvasEl.offsetLeft), y: parseInt(e.pageY - canvasEl.offsetTop)};
  126.  
  127. e.preventDefault();
  128. e.stopPropagation();
  129. return false;
  130. };
  131. handleContainerForThisPolygon.appendChild(newHandle);
  132. }
  133.  
  134. handleContainerForThisPolygon.id = 'handleContainer' + totalPolygonsCreated;
  135. document.body.appendChild(handleContainerForThisPolygon);
  136.  
  137. polygons[newPolygonKey].boundingBox = {
  138. top: Math.min.apply(null, yS),
  139. right: Math.max.apply(null, xS),
  140. bottom: Math.max.apply(null, yS),
  141. left: Math.min.apply(null, xS)
  142. };
  143.  
  144. actionState = '';
  145. polygonPoints = [];
  146.  
  147. fillPolygonAndPositionHandles(newPolygonKey);
  148. }
  149. else {
  150. var newCursorPoint = {x: e.pageX - canvasEl.offsetLeft, y: e.pageY - canvasEl.offsetTop};
  151.  
  152. if(actionState == 'drawing')
  153. drawLine(polygonPoints[polygonPoints.length - 1], newCursorPoint);
  154. else
  155. actionState = 'drawing';
  156.  
  157. polygonPoints.push({x: parseInt(newCursorPoint.x), y: parseInt(newCursorPoint.y)});
  158. }
  159. };
  160.  
  161. canvasEl.onmousemove = function(e) {
  162. if(adjustingPolygon) {
  163. var handleBeingDragged = document.getElementById(idOfHandleBeingDragged),
  164. cursorPoint = {x: e.pageX - canvasEl.offsetLeft, y: e.pageY - canvasEl.offsetTop},
  165. xDiff = parseInt(cursorPoint.x - prevCursorPoint.x),
  166. yDiff = parseInt(cursorPoint.y - prevCursorPoint.y);
  167.  
  168. prevCursorPoint = {x: parseInt(cursorPoint.x), y: parseInt(cursorPoint.y)};
  169.  
  170. handleBeingDragged.style.left = parseInt(handleBeingDragged.style.left.replace('px', '')) + xDiff + 'px';
  171. handleBeingDragged.style.top = parseInt(handleBeingDragged.style.top.replace('px', '')) + yDiff + 'px';
  172.  
  173. var lineSegments = polygons['_' + handleBeingDragged.parentNode.id.substring(15)].lineSegments,
  174. firstLineSegment = lineSegments[parseInt(idOfHandleBeingDragged.substring(6))];
  175.  
  176. if(parseInt(idOfHandleBeingDragged.substring(6)) == 0)
  177. secondLineSegment = lineSegments[lineSegments.length - 1];
  178. else
  179. secondLineSegment = lineSegments[parseInt(idOfHandleBeingDragged.substring(6)) - 1];
  180.  
  181. firstLineSegment.startPoint.x += xDiff;
  182. firstLineSegment.startPoint.y += yDiff;
  183. firstLineSegment.minX = Math.min(firstLineSegment.startPoint.x, firstLineSegment.endPoint.x);
  184. firstLineSegment.minY = Math.min(firstLineSegment.startPoint.y, firstLineSegment.endPoint.y);
  185. firstLineSegment.maxX = Math.max(firstLineSegment.startPoint.x, firstLineSegment.endPoint.x);
  186. firstLineSegment.maxY = Math.max(firstLineSegment.startPoint.y, firstLineSegment.endPoint.y);
  187. firstLineSegment.gradient = (firstLineSegment.endPoint.y - firstLineSegment.startPoint.y) / (firstLineSegment.endPoint.x - firstLineSegment.startPoint.x);
  188. firstLineSegment.yIntercept = firstLineSegment.startPoint.y - firstLineSegment.gradient * firstLineSegment.startPoint.x;
  189.  
  190. secondLineSegment.endPoint.x += xDiff;
  191. secondLineSegment.endPoint.y += yDiff;
  192. secondLineSegment.minX = Math.min(secondLineSegment.startPoint.x, secondLineSegment.endPoint.x);
  193. secondLineSegment.minY = Math.min(secondLineSegment.startPoint.y, secondLineSegment.endPoint.y);
  194. secondLineSegment.maxX = Math.max(secondLineSegment.startPoint.x, secondLineSegment.endPoint.x);
  195. secondLineSegment.maxY = Math.max(secondLineSegment.startPoint.y, secondLineSegment.endPoint.y);
  196. secondLineSegment.gradient = (secondLineSegment.endPoint.y - secondLineSegment.startPoint.y) / (secondLineSegment.endPoint.x - secondLineSegment.startPoint.x);
  197. secondLineSegment.yIntercept = secondLineSegment.startPoint.y - secondLineSegment.gradient * secondLineSegment.startPoint.x;
  198.  
  199. canvasEl.width = canvasEl.width;
  200. fillPolygonAndPositionHandles('_' + handleBeingDragged.parentNode.id.substring(15));
  201. }
  202. };
  203.  
  204. canvasEl.oncontextmenu = function(e) {
  205. e.stopPropagation();
  206. e.preventDefault();
  207. return false;
  208. }
  209.  
  210. window.onmouseup = function(e) {
  211. adjustingPolygon = false;
  212.  
  213. e.stopPropagation();
  214. e.preventDefault();
  215. return false;
  216. };
  217.  
  218. function fillPolygonAndPositionHandles(poly) {
  219. pointsByY = {};
  220.  
  221. for(segmentIndex in polygons[poly].lineSegments) {
  222. var lineSegment = polygons[poly].lineSegments[segmentIndex];
  223.  
  224. for(var y = lineSegment.minY; y < lineSegment.maxY; y++) {
  225. var x = Math.round((y - lineSegment.yIntercept) / lineSegment.gradient);
  226.  
  227. if(typeof pointsByY['_' + y] == 'undefined')
  228. pointsByY['_' + y] = [];
  229.  
  230. pointsByY['_' + y].push(parseInt(x));
  231. }
  232. }
  233.  
  234. for(y in pointsByY) {
  235. pointsByY[y].sort(function(a, b){return a-b;});
  236.  
  237. for(var xIndex = 0; xIndex < pointsByY[y].length; xIndex++)
  238. putPixel(pointsByY[y][xIndex], parseInt(y.substring(1)), 0, 255, 255, 255);
  239. }
  240.  
  241. // now fill
  242.  
  243. document.getElementById('testPixels').innerHTML = '';
  244. for(y in pointsByY) {
  245. for(var xIndex = 0; xIndex < pointsByY[y].length; xIndex++) {
  246. if(xIndex < pointsByY[y].length - 1) {
  247. if(pointInPolygon(pointsByY[y][xIndex], parseInt(y.substring(1))))
  248. drawLine({x: pointsByY[y][xIndex], y: parseInt(y.substring(1))}, {x: pointsByY[y][xIndex + 1], y: parseInt(y.substring(1))});
  249. }
  250. }
  251. }
  252.  
  253. pointsByY = {};
  254. }
  255.  
  256. document.body.appendChild(canvasEl);
  257. }
  258. //]]>
  259. </script>
  260. </head>
  261. <body onload="vectorFillTest();">
  262. <h1>Deal with horizontal/vertical lines</h1>
  263. <div id="testPixels"></div>
  264. </body>
  265. </html>

Report this snippet  

You need to login to post a comment.