Алгоритм отсечения Сазерленда-Ходгмана на JS

Алгоритм отсечения Сазерленда-Ходгмана (раньше всё-таки писали Сазерленда-Ходжмена, в русской "Вики" отдельной статьи таки нет) широко используется для реализации отсечения произвольного многоугольника прямоугольным окном.

Ниже показана небольшая реализация на яваскрипте, которая выводит результаты своей работы в элемент HTML5 <canvas>.

Вот скриншот этого примера и ниже полный исходник (без обрамляющих тегов HTML). Его можно выполнить, сохранив как файл типа .html. Здесь мы отсекаем зелёный многоугольник красным отсекающим окном, получив синий многоугольник.

Алгоритм отсечения Сазерленда-Ходгмана, скриншот вывода примера

<div align="center">
 <canvas id="clipCanvas" width="400" height="400"></canvas>
</div>
<script type="text/javascript">
 function clip (subjectPolygon, clipPolygon) { //Алгоритм отсечения Сазерленда-Ходгмана
  var cp1, cp2, s, e;

  var inside = function (p) {
   return (cp2[0]-cp1[0])*(p[1]-cp1[1]) > (cp2[1]-cp1[1])*(p[0]-cp1[0]);
  };

  var intersection = function () {
   var dc = [ cp1[0] - cp2[0], cp1[1] - cp2[1] ],
       dp = [ s[0] - e[0], s[1] - e[1] ],
       n1 = cp1[0] * cp2[1] - cp1[1] * cp2[0],
       n2 = s[0] * e[1] - s[1] * e[0], 
       n3 = 1.0 / (dc[0] * dp[1] - dc[1] * dp[0]);
   return [(n1*dp[0] - n2*dc[0]) * n3, (n1*dp[1] - n2*dc[1]) * n3];
  };

  var outputList = subjectPolygon;
  cp1 = clipPolygon[clipPolygon.length-1];
  for (j in clipPolygon) {
   var cp2 = clipPolygon[j];
   var inputList = outputList;
   outputList = [];
   s = inputList[inputList.length - 1]; //последняя точка
   for (i in inputList) {
    var e = inputList[i];
    if (inside (e)) {
     if (!inside (s)) {
      outputList.push (intersection());
     }
     outputList.push (e);
    }
    else if (inside(s)) {
     outputList.push (intersection());
    }
    s = e;
   }
   cp1 = cp2;
  }
  return outputList;
 } //конец функции clip
 
 function drawPolygon (context, polygon, strokeStyle, fillStyle) {
  //Аргументы: контекст, многоугольник, цвет рисования, цвет заливки
  context.strokeStyle = strokeStyle;
  context.fillStyle = fillStyle;
  context.beginPath();
  context.moveTo (polygon[0][0],polygon[0][1]); //первая вершина
  for (var i = 1; i < polygon.length; i++) context.lineTo (polygon[i][0],polygon[i][1]);
  context.lineTo (polygon[0][0],polygon[0][1]); //назад в начало
  context.fill();
  context.stroke();
  context.closePath();
 }
 
 window.onload = function () {
  var context = document.getElementById('clipCanvas').getContext('2d');
   //канва
  var subjectPolygon = [[50, 50], [200, 110], [350,50], [290,200], [240,400], [90,345]];
   //исходный отсекаемый многоугольник
  var clipPolygon = [[100, 100], [300, 100], [300, 300], [100, 300]];
   //отсекающий многоугольник
  var clippedPolygon = clip(subjectPolygon, clipPolygon);
  drawPolygon (context, clipPolygon, '#990000','#990000');
   //красным - отсекающий многоугольник
  drawPolygon (context, subjectPolygon, '#009900','#009900');
   //зелёным - исходный, который отсекаем
  drawPolygon(context, clippedPolygon, '#000099','#000099');
   //синим - полученный отсечённый многоугольник
 }
</script>
<noscript>
 <div align="center">Извините, для работы приложения нужен включённый Javascript</div>
</noscript>

17.10.2018, 19:13 [2820 просмотров]