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

haxe collision sat gamedev
  1. package;
  2.  
  3. import js.Browser.document;
  4. import js.Browser.window;
  5. import js.html.CanvasElement;
  6. import js.html.CanvasRenderingContext2D in Context2D;
  7.  
  8. typedef Point = {x:Float, y:Float}
  9.  
  10. class Main {
  11.  
  12.     var canvas:CanvasElement;
  13.     var g:Context2D;
  14.     var poly:Array<Point>;
  15.     var poly2:Array<Point>;
  16.  
  17.     static function main():Void {
  18.         new Main();
  19.     }
  20.  
  21.     function new() {
  22.         canvas = document.createCanvasElement();
  23.         canvas.id = "canvas";
  24.         canvas.style.border = "1px solid #000";
  25.         canvas.style.cursor = "none";
  26.         document.body.appendChild(canvas);
  27.         g = canvas.getContext("2d");
  28.  
  29.         poly = [{x:0, y:0}, {x:30, y:2}, {x:8, y:30}];
  30.         poly2 = [{x:60, y:60}, {x:90, y:61}, {x:98, y:100}, {x:80, y:100}];
  31.  
  32.         canvas.onmousemove = function(e) {
  33.             // moving first polygon
  34.             final rect = canvas.getBoundingClientRect();
  35.             poly[0].x = e.clientX - rect.left;
  36.             poly[0].y = e.clientY - rect.top;
  37.             poly[1].x = poly[0].x + 30;
  38.             poly[1].y = poly[0].y + 2;
  39.             poly[2].x = poly[0].x + 8;
  40.             poly[2].y = poly[0].y + 30;
  41.         }
  42.  
  43.         window.requestAnimationFrame(onRender);
  44.     }
  45.  
  46.     function onRender(stamp:Float):Void {
  47.         g.clearRect(0, 0, canvas.width, canvas.height);
  48.  
  49.         if (doPolygonsIntersect(poly, poly2)) g.fillStyle = "red";
  50.         else g.fillStyle = "black";
  51.         drawPoly(g, poly);
  52.         drawPoly(g, poly2);
  53.  
  54.         window.requestAnimationFrame(onRender);
  55.     }
  56.  
  57.     inline function drawPoly(g:Context2D, poly:Array<Point>):Void {
  58.         g.beginPath();
  59.         g.moveTo(poly[0].x, poly[0].y);
  60.         for (i in 1...poly.length) {
  61.             g.lineTo(poly[i].x, poly[i].y);
  62.         }
  63.         g.fill();
  64.     }
  65.  
  66.     function doPolygonsIntersect(a:Array<Point>, b:Array<Point>) {
  67.         final polygons = [a, b];
  68.  
  69.         for (polygon in polygons) {
  70.             for (i in 0...polygon.length) {
  71.                 // get points for normal
  72.                 final i2 = (i + 1) % polygon.length;
  73.                 final p1 = polygon[i];
  74.                 final p2 = polygon[i2];
  75.                 final normal = {
  76.                     x: p2.y - p1.y,
  77.                     y: p1.x - p2.x
  78.                 };
  79.  
  80.                 var minA = Math.POSITIVE_INFINITY;
  81.                 var maxA = Math.NEGATIVE_INFINITY;
  82.                 for (point in a) {
  83.                     final projected = normal.x * point.x + normal.y * point.y;
  84.                     if (projected < minA) minA = projected;
  85.                     if (projected > maxA) maxA = projected;
  86.                 }
  87.  
  88.                 var minB = Math.POSITIVE_INFINITY;
  89.                 var maxB = Math.NEGATIVE_INFINITY;
  90.                 for (point in b) {
  91.                     final projected = normal.x * point.x + normal.y * point.y;
  92.                     if (projected < minB) minB = projected;
  93.                     if (projected > maxB) maxB = projected;
  94.                 }
  95.  
  96.                 if (maxA < minB || maxB < minA) return false;
  97.             }
  98.         }
  99.         return true;
  100.     }
  101.  
  102. }
Очень короткая реализация сути алгоритма на основе Separating Axis Theorem. Работает только с выпуклыми полигонами (вогнутые фигуры можно разбить на несколько выпуклых).

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

Исходники в онлайн-редакторе: http://try-haxe.mrcdk.com/#0D9d6

JS версия:
https://jsfiddle.net/RblSb/38Lrqfrr/

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

Реклама

Мы в соцсетях

tw tg yt gt