Реклама

Обнаружение коллизии полигонов

  1. var canvas = document.getElementById('canvas');
  2. var g = canvas.getContext('2d');
  3. var w = canvas.width; //размеры канваса
  4. var h = canvas.height;
  5.  
  6. var pol = [{x:0, y:0}, {x:30, y:2}, {x:8, y:30}];
  7. var pol2 = [{x:60, y:60}, {x:90, y:61}, {x:98, y:100}, {x:80, y:100}];
  8.  
  9. canvas.onmousemove = function(e) {
  10.   //перемещение 1 полигона
  11.   var rect = canvas.getBoundingClientRect();
  12.   pol[0].x = e.clientX - rect.left;
  13.   pol[0].y = e.clientY - rect.top;
  14.   pol[1].x = pol[0].x + 30;
  15.   pol[1].y = pol[0].y + 2;
  16.   pol[2].x = pol[0].x + 8;
  17.   pol[2].y = pol[0].y + 30;
  18. }
  19.  
  20. function main() {
  21.   g.clearRect(0, 0, w, h);
  22.  
  23.   if (doPolygonsIntersect(pol, pol2)) g.fillStyle = "#FF0000";
  24.   else g.fillStyle = "#000";
  25.  
  26.   //отрисовка полигонов
  27.   g.beginPath();
  28.   g.moveTo(pol[0].x, pol[0].y);
  29.   for (var i = 1; i < pol.length; i++) {
  30.     g.lineTo(pol[i].x, pol[i].y);
  31.   }
  32.   g.fill();
  33.  
  34.   g.beginPath();
  35.   g.moveTo(pol2[0].x, pol2[0].y);
  36.   for (i = 1; i < pol2.length; i++) {
  37.     g.lineTo(pol2[i].x, pol2[i].y);
  38.   }
  39.   g.fill();
  40.  
  41. }
  42.  
  43. function doPolygonsIntersect(a, b) {
  44.   var polygons = [a, b];
  45.   var minA, maxA, projected, i, i1, j, minB, maxB;
  46.  
  47.   for (i = 0; i < polygons.length; i++) {
  48.  
  49.     //на обоих полигонах смотрим каждую грань и определяем, есть ли с ней пересечение
  50.     var polygon = polygons[i];
  51.     for (i1 = 0; i1 < polygon.length; i1++) {
  52.  
  53.       //берем две вершины для создания грани
  54.       var i2 = (i1 + 1) % polygon.length;
  55.       var p1 = polygon[i1];
  56.       var p2 = polygon[i2];
  57.  
  58.       //находим перпендикуляр этой грани (линия с наклоном на 90 градусов от текущей)
  59.       var normal = {
  60.         x: p2.y - p1.y,
  61.         y: p1.x - p2.x
  62.       };
  63.  
  64.       minA = Infinity;
  65.       maxA = -Infinity;
  66.  
  67.       //каждую вершину первого полигона проецируем на линию, перпендикулярную грани
  68.       //и находим мин/макс значения
  69.       for (j = 0; j < a.length; j++) {
  70.         projected = normal.x * a[j].x + normal.y * a[j].y;
  71.         if (projected < minA) minA = projected;
  72.         if (projected > maxA) maxA = projected;
  73.       }
  74.  
  75.       //каждую вершину второго полигона проецируем на линию, перпендикулярную грани
  76.       //и находим мин/макс значения
  77.       minB = Infinity;
  78.       maxB = -Infinity;
  79.       for (j = 0; j < b.length; j++) {
  80.         projected = normal.x * b[j].x + normal.y * b[j].y;
  81.         if (projected < minB) minB = projected;
  82.         if (projected > maxB) maxB = projected;
  83.       }
  84.  
  85.       //если между проекциями нет перекрытия, то существует грань (линия), точно разделяющая два полигона
  86.       //и тогда полигоны не пересекаются!
  87.       if (maxA < minB || maxB < minA) return false;
  88.     }
  89.   }
  90.   return true;
  91. };
  92.  
  93. setInterval(main, 1000 / 60);
Очень короткая реализация сути алгоритма на основе Separating Axis Theorem. Работает только с выпуклыми полигонами (вогнутые фигуры можно разбить на несколько выпуклых).

При использовании для большого кол-ва полигонов не забудьте сначала просчитывать и проверять прямоугольные границы каждого полигона на пересечение (bounding boxes). Подробнее будет в статье по написанию своего физ. движка, появится здесь в ближайшие 5 лет.

Потестить онлайн:
https://jsfiddle.net/RblSb/38Lrqfrr/

Оригинал алгоритма (с вариациями на других языках):
http://stackoverflow.com/a/12414951/4750888


Пожертвования

Аноним2800 р.
Freddy1700 р.
NaruTrey800 р.
vlavolk522 р.
mr-demiurg200 р.
  © aNNiMON (Melnik Software)
 
Яндекс.Метрика