Avoid 2D shape intersection by rotating the collider

user_4845566 0
Viewed 88

I have to avoid intersections among some basic 2-D shapes, mainly rectangles. Other shapes are circles and triangles. For instance, in the picture below I am checking against rectangles intersection using the separating-axis test. The shape [A,B,C,D] will translate horizontally while the shape [E,F,G,H] is costrained and can only rotate about the origin (0,0):

sample collision

To avoid shape intersection, now I am rotating the collider [E,F,G,H] until the check against intersection returns false. The pseudo-code looks like this:

var polygonA = [array of points...];
var intersect = false;
do {
  var polygonB= [array of points...];
  intersect = doPolygonsIntersect(polygonA, polygonB);
  if(intersect) {
    setRotationPolyB(currentRotationPolyB - 1degree);
  }
} while(intersect);

I wonder if there is a faster method to compute the rotation angle without this time-consuming loop.

Here is a complete playground:

function rotP(pX, pY, oX, oY, d) {
  var r = d*Math.PI/180,
      x = Math.cos(r)*(pX-oX)-Math.sin(r)*(pY-oY)+oX,
      y = Math.sin(r)*(pX-oX)+Math.cos(r)*(pY-oY)+oY;
  return {X:x, Y:y};
}

function doPolygonsIntersect(a, b) {
  var polygons=[a, b], nA=a.length, nB=b.length;
  var minA, maxA, minB, maxB, k = 0;
  do {
    var poly = polygons[k], n = poly.length;
    for(var i1=0; i1<n; i1++) {
      var i2=(i1 + 1) % poly.length;
      var p1=poly[i1], p2=poly[i2];
      var normX = p2.y - p1.y, normY = p1.x - p2.x;
      minA = +Infinity;
      maxA = -Infinity;
      for(var j=0; j<nA; j++) {
        var projected = normX * a[j].x + normY * a[j].y;
        if (projected < minA) minA = projected;
        if (projected > maxA) maxA = projected;
      }
      minB = +Infinity;
      maxB = -Infinity;
      for(var j=0; j<nB; j++) {
        var projected = normX * b[j].x + normY * b[j].y;
        if (projected < minB) minB = projected;
        if (projected > maxB) maxB = projected;
      }
      if (maxA < minB || maxB < minA) return false;
    }
  } while (k++ < 1);
  return true;
}

function drawOccluder() {
  var y=-2, w=3, h=1, p=[];
  p.push(board.create('point',
      [function(){return sO.Value()+w},function(){return y}],
      {color:'red'}));
  p.push(board.create('point',
      [function(){return sO.Value()},function(){return y}],
      {color:'red'}));
  p.push(board.create('point',
      [function(){return sO.Value()},function(){return y-h}],
      {color:'red'}));
  p.push(board.create('point',
      [function(){return sO.Value() + w},function(){return y-h}],
      {color:'red'}));
  var poly = board.create('polygon', p, {hasInnerPoints:true});
  return p;
}

function drawCollider() {
  var x0=-2.5, y0=1, w=5, h=6, p=[];
  var r=[{x:x0, y:y0},{x:x0+w, y:y0},{x:x0+w, y:y0-h},{x:x0, y:y0-h}];
  p.push(board.create('point',
      [function(){var v=sC.Value(); return rotP(r[0].x,r[0].y,0,0,v).X},
        function(){var v=sC.Value(); return rotP(r[0].x,r[0].y,0,0,v).Y}],
      {color:'green'}));
  p.push(board.create('point',
      [function(){var v=sC.Value(); return rotP(r[1].x,r[1].y,0,0,v).X},
       function(){var v=sC.Value(); return rotP(r[1].x,r[1].y,0,0,v).Y}],
      {color:'green'}));
  p.push(board.create('point',
      [function(){var v=sC.Value(); return rotP(r[2].x,r[2].y,0,0,v).X},
       function(){var v=sC.Value(); return rotP(r[2].x,r[2].y,0,0,v).Y}],
      {color:'green'}));
  p.push(board.create('point',
      [function(){var v=sC.Value(); return rotP(r[3].x,r[3].y,0,0,v).X},
       function(){var v=sC.Value(); return rotP(r[3].x,r[3].y,0,0,v).Y}],
      {color:'green'}));
  var poly = board.create('polygon', p, {hasInnerPoints:true});
  return p;
}

var board, sO, sC, pO, pC;

document.addEventListener('DOMContentLoaded', function(e) {
  board = JXG.JSXGraph.initBoard('jxgbox', {boundingbox:[-8.0,8.0,8.0,-8.0],axis:true});
  board.suspendUpdate();
  sO = board.create('slider', [[3.5, -6],[-3.5, -6],[3.5, 3.5, -3.5]]);
  sC = board.create('slider', [[2.5, 6],[-2.5, 6],[0, 0, -180]]);
  pO = drawOccluder();
  pC = drawCollider();
  board.unsuspendUpdate();

  document.getElementById('slider').addEventListener('input', function (e) {
    sO.setValue(this.value);
    board.update();
    var polyO = [{x:pO[0].X(),y:pO[0].Y()},{x:pO[1].X(),y:pO[1].Y()},{x:pO[2].X(),y:pO[2].Y()},{x:pO[3].X(),y:pO[3].Y()}];
    var loop = 0, intersect = false;
    do {
      if(loop++ > 180) break;
      var polyC = [{x:pC[0].X(),y:pC[0].Y()},{x:pC[1].X(),y:pC[1].Y()},{x:pC[2].X(),y:pC[2].Y()},{x:pC[3].X(),y:pC[3].Y()}];
      intersect = doPolygonsIntersect(polyO, polyC);
      if(intersect) {
        sC.setValue(sC.Value()-1);
        board.update();
      }
    } while (intersect);
  });

})
<!DOCTYPE html>
<html>
<head>
  <link rel="stylesheet" type="text/css" href="//cdnjs.cloudflare.com/ajax/libs/jsxgraph/1.3.2/jsxgraph.css" />
  <script type="text/javascript" charset="UTF-8" src="//cdnjs.cloudflare.com/ajax/libs/jsxgraph/1.3.2/jsxgraphcore.js"></script>
</head>
<body>
  <input type="range" min="-3.5" max="3.5" value="3.5" step="0.01" id="slider">
  <div id="jxgbox" class="jxgbox" style="width:560px; height:560px;"></div>
</body>
</html>

https://plnkr.co/edit/AfoOyPTMDrnwjBL0?open=lib%2Fscript.js

collision-detection trigonometry algorithm javascript
1 Answers
  1. calculate the distance from each point of the Collider to the center of rotation of the Rotator (call it cp, for center-point). Take the closest vertex to that center - let us call it ccp (closest-collider-point).
  2. calculate point on the Rotator that is closest to the center. Call it crp. There may be several of these - choose the closest one to the ccp.
  3. calculate md = dist(cp, crp) - dist(cp, ccp), the maximum distance between both shapes for any rotation of the Rotator.
    • if md < 0, there is nothing to do: both shapes will intersect no matter how you rotate the Rotator.
    • otherwise, rotating the Rotator so that the rotated crp lies along the line from cp to cpp will make the distance between both shapes equal to md. Since you are looking for the minimal displacement, this gives you an upper bound on how much you must rotate the rotator.

If you reach step 3.2 (ie, a solution is possible), and there is currently an overlap, you can find the minimal positive angle to turn by binary subdivision (where minRotation = currentRotation is initially the current rotation, epsilon is your required degree of precision, say 1 degree, and max is whatever the rotation is required according to step 3.2 above). You need max>min, so you may need to add a full turn to max to ensure this:

function findMinimalAngleToRotate(min, currentRotation, max, epsilon) {
    let nextRotation = (currentRotation + max)/2;
    let delta = nextRotation - currentRotation;
    if (overlapsWithRotation(nextRotation)) {
       // rotate more!
       return findMinimalAngleToRotate(min, nextRotation, max, epsilon);
    } else if (delta > epsilon) {
       // overdid it - rotate a bit less! 
       nextRotation -= delta/2;
       return findMinimalAngleToRotate(min, nextRotation, max, epsilon;
    } else {
       // stop: we have found the smallest (+- epsilon) rotation 
       return nextRotation;
    }
}

Note that this is just a sketch, and my findMinimalAngleToRotate's binary subdivision only goes from min to max, when it should sometimes go the other way around. On the other hand, once fixed, this will allow greater precision (if you lower epsilon), and greater performance (better-than-1 degree precision in less than 10 attempts, instead of your current 180 attempts)

Note also that sometimes the minimal angle to rotate will jump significantly as a result to small movements of the Collider. In the following figure (where the center of rotation is at x=0, y=-1.5), when point B reaches x = 3, the Rotator will need to turn to (according to your playground) -72º to avoid intersection, and would only be able to do so by intersecting with the Collider somewhere along the way. You may wish to detect and disallow this:

Rotator (large, rotates) and Collider (small, moves to the left along the x axis)

user_154720
Related