javascripttypescriptalgorithmcollision-detectioncollision

Collision detection of two rects with rounded borders

I wrote an algorithm how to detect the collision detection of two rects with rounded borders (the code was written using TypeScript but I tried to name things as clear as possible to code be readable for anyone):

const canvas = document.querySelector("canvas");

canvas.width = window.innerWidth / 1.2;
canvas.height = window.innerHeight / 1.2;

window.addEventListener('resize', () => {
  canvas.width = window.innerWidth / 1.2;
  canvas.height = window.innerHeight / 1.2;
})

const ctx = canvas.getContext("2d");

type Rect = {
  x: number;
  y: number;
  w: number;
  h: number;
};

type RoundedRect = Rect & {
  borderRadius: number;
};

const isFirstRectRighterThanSecond = (rect1: Rect, rect2: Rect): boolean => rect1.x + rect1.w < rect2.x;
const isFirstRectBelowThanSecond = (rect1: Rect, rect2: Rect): boolean => rect1.y + rect1.h < rect2.y;

const hasNotAABBCollision = (rect1: Rect, rect2: Rect): boolean =>
  isFirstRectRighterThanSecond(rect1, rect2) ||
  isFirstRectRighterThanSecond(rect2, rect1) ||
  isFirstRectBelowThanSecond(rect1, rect2) ||
  isFirstRectBelowThanSecond(rect2, rect1);

class Vector {
  constructor(
    x: number = 0,
    y: number = 0,
  ) {
    this.x = x;
    this.y = y
  }
}

const getRoundedRectTopLeftRoundedCornerCenter = (roundedRect: RoundedRect): Vector =>
  new Vector(roundedRect.x + roundedRect.borderRadius, roundedRect.y + roundedRect.borderRadius);

const getRoundedRectTopRightRoundedCornerCenter = (roundedRect: RoundedRect): Vector =>
  new Vector(roundedRect.x + roundedRect.w - roundedRect.borderRadius, roundedRect.y + roundedRect.borderRadius);

const getRoundedRectBottomRightRoundedCornerCenter = (roundedRect: RoundedRect): Vector =>
  new Vector(
    roundedRect.x + roundedRect.w - roundedRect.borderRadius,
    roundedRect.y + roundedRect.h - roundedRect.borderRadius,
  );

const getRoundedRectBottomLeftRoundedCornerCenter = (roundedRect: RoundedRect): Vector =>
  new Vector(roundedRect.x + roundedRect.borderRadius, roundedRect.y + roundedRect.h - roundedRect.borderRadius);

const getRoundedRectRoundedCornersCenters = (roundedRect: RoundedRect): Vector[] => [
  getRoundedRectTopLeftRoundedCornerCenter(roundedRect),
  getRoundedRectTopRightRoundedCornerCenter(roundedRect),
  getRoundedRectBottomRightRoundedCornerCenter(roundedRect),
  getRoundedRectBottomLeftRoundedCornerCenter(roundedRect),
];

const sqr = (x: number) => x * x;

const squareDistance = (vector1: Vector, vector2: Vector): number =>
  sqr(vector1.x - vector2.x) + sqr(vector1.y - vector2.y);

const doTwoCirclesCollide = (
  circle1Center: Vector,
  circle1Radius: number,
  circle2Center: Vector,
  circle2Radius: number,
): boolean => squareDistance(circle1Center, circle2Center) <= sqr(circle1Radius + circle2Radius);

const doCirclesCollide = (circles1Centers: Vector[], circles1Radius: number, circles2Centers: Vector[], circles2Radius: number): boolean =>
  circles1Centers.some(
    circle1Center => circles2Centers.some(
      circle2Center => doTwoCirclesCollide(circle1Center, circles1Radius, circle2Center, circles2Radius)
    )
  );


class Segment {
  constructor(
    start: Vector = new Vector(0, 0),
    end: Vector = new Vector(0, 0),
  ) {
    this.start = start;
    this.end = end;
  }
}

const getRoundedRectTopSegment = (roundedRect: RoundedRect): Segment =>
  new Segment(
    new Vector(roundedRect.x + roundedRect.borderRadius, roundedRect.y),
    new Vector(roundedRect.x + roundedRect.w - roundedRect.borderRadius, roundedRect.y),
  );

const getRoundedRectRightSegment = (roundedRect: RoundedRect): Segment =>
  new Segment(
    new Vector(roundedRect.x + roundedRect.w, roundedRect.y + roundedRect.borderRadius),
    new Vector(roundedRect.x + roundedRect.w, roundedRect.y + roundedRect.h - roundedRect.borderRadius),
  );

const getRoundedRectBottomSegment = (roundedRect: RoundedRect): Segment =>
  new Segment(
    new Vector(roundedRect.x + roundedRect.borderRadius, roundedRect.y + roundedRect.h),
    new Vector(roundedRect.x + roundedRect.w - roundedRect.borderRadius, roundedRect.y + roundedRect.h),
  );

const getRoundedRectLeftSegment = (roundedRect: RoundedRect): Segment =>
  new Segment(
    new Vector(roundedRect.x, roundedRect.y + roundedRect.borderRadius),
    new Vector(roundedRect.x, roundedRect.y + roundedRect.h - roundedRect.borderRadius),
  );

const getRoundedRectSegments = (roundedRect: RoundedRect): Segment[] => [
  getRoundedRectTopSegment(roundedRect),
  getRoundedRectRightSegment(roundedRect),
  getRoundedRectBottomSegment(roundedRect),
  getRoundedRectLeftSegment(roundedRect),
];

const crossProduct = (vector1: Vector, vector2: Vector): number => vector1.x * vector2.y - vector1.y * vector2.x;

const Orientations = {
  Collinear: 0,
  Clockwise: 1,
  Counterclockwise: 2,
}

const getOrientation = (vector1: Vector, vector2: Vector, vector3: Vector): Orientations => {
  const result = crossProduct(
    new Vector(vector3.x - vector2.x, vector3.y - vector2.y),
    new Vector(vector2.x - vector1.x, vector2.y - vector1.y),
  );

  if (result === 0) return Orientations.Collinear;

  if (result > 0) return Orientations.Clockwise;

  return Orientations.Counterclockwise;
};

const Axis = {
  X: "x",
  Y: "y",
}

const isDotOnSegmentProjection = (segment: Segment, dot: Vector, axis: Axis): boolean =>
  dot[axis] <= Math.max(segment.start[axis], segment.end[axis]) &&
  dot[axis] >= Math.min(segment.start[axis], segment.end[axis]);

const isDotOnSegmentProjections = (segment: Segment, dot: Vector): boolean =>
  isDotOnSegmentProjection(segment, dot, Axis.X) && isDotOnSegmentProjection(segment, dot, Axis.Y);

const doTwoSegmentsIntersect = (segment1: Segment, segment2: Segment): boolean => {
  const orientation1 = getOrientation(segment1.start, segment1.end, segment2.start);
  const orientation2 = getOrientation(segment1.start, segment1.end, segment2.end);
  const orientation3 = getOrientation(segment2.start, segment2.end, segment1.start);
  const orientation4 = getOrientation(segment2.start, segment2.end, segment1.end);

  if (orientation1 !== orientation2 && orientation3 !== orientation4) return true;

  return (
    (orientation1 === Orientations.Collinear && isDotOnSegmentProjections(segment1, segment2.start)) ||
    (orientation2 === Orientations.Collinear && isDotOnSegmentProjections(segment1, segment2.end)) ||
    (orientation3 === Orientations.Collinear && isDotOnSegmentProjections(segment2, segment1.start)) ||
    (orientation4 === Orientations.Collinear && isDotOnSegmentProjections(segment2, segment1.end))
  );
};

const doSegmentsIntersect = (segments1: Segment[], segments2: Segment[]): boolean =>
  segments1.some(
    segment1 => segments2.some(
      segment2 => doTwoSegmentsIntersect(segment1, segment2)
    )
  );

const distToSegmentSquared = (dot: Vector, segment: Segment) => {
  const squaredSegmentLength = squareDistance(segment.start, segment.end);

  if (squaredSegmentLength === 0) return squareDistance(dot, segment.start);

  const t =
    ((dot.x - segment.start.x) * (segment.end.x - segment.start.x) +
      (dot.y - segment.start.y) * (segment.end.y - segment.start.y)) /
    squaredSegmentLength;

  const clampedT = Math.max(0, Math.min(1, t));

  return squareDistance(
    dot,
    new Vector(
      segment.start.x + clampedT * (segment.end.x - segment.start.x),
      segment.start.y + clampedT * (segment.end.y - segment.start.y),
    ),
  );
};

const doCircleIntersectWithSegment = (circleCenter: Vector, circleRadius: number, segment: Segment): boolean =>
  distToSegmentSquared(circleCenter, segment) <= sqr(circleRadius);

const doCirclesIntersectWithSegments = (circlesCenters: Vector[], circlesRadius: number, segments: Segment[]): boolean =>
  circlesCenters.some(
    circleCenter => segments.some(
      segment => doCircleIntersectWithSegment(circleCenter, circlesRadius, segment)
    )
  );

const doSegmentsIntersectOnProjection = (segment1: Segment, segment2: Segment, axis: Axis): boolean =>
  isDotOnSegmentProjection(segment1, segment2.start, axis) ||
  isDotOnSegmentProjection(segment1, segment2.end, axis) ||
  isDotOnSegmentProjection(segment2, segment1.start, axis) ||
  isDotOnSegmentProjection(segment2, segment1.end, axis)

const doRoundedRectsCollide = (roundedRect1: RoundedRect, roundedRect2: RoundedRect): boolean => {
  if (hasNotAABBCollision(roundedRect1, roundedRect2)) {
    return false;
  }

  const roundedRect1CornersCenters = getRoundedRectRoundedCornersCenters(roundedRect1);
  const roundedRect2CornersCenters = getRoundedRectRoundedCornersCenters(roundedRect2);

  if (
    doCirclesCollide(
      roundedRect1CornersCenters,
      roundedRect1.borderRadius,
      roundedRect2CornersCenters,
      roundedRect2.borderRadius
    )
  ) return true;

  const roundedRect1Segments = getRoundedRectSegments(roundedRect1);
  const roundedRect2Segments = getRoundedRectSegments(roundedRect2);

  if (doSegmentsIntersect(roundedRect1Segments, roundedRect2Segments)) return true;

  if (doCirclesIntersectWithSegments(roundedRect1CornersCenters, roundedRect1.borderRadius, roundedRect2Segments)) return true;

  if (doCirclesIntersectWithSegments(roundedRect2CornersCenters, roundedRect2.borderRadius, roundedRect1Segments)) return true;

  /*
   Check if one of the rects is inside another one

   The below algorithm works only because we already tested a lot of other cases

   THIS ALGORITHM MUST NOT BE USED IN GENERAL CASE
   */

  /*
   The arguments passed in that way for optimization purposes

   If you don't want to depend on the order of elements of an array which is returned by `getRoundedRectSegments`
   then you should use `getRoundedRectTopSegment` and `getRoundedRectRightSegment` functions respectively
   */
  return (
    doSegmentsIntersectOnProjection(roundedRect1Segments[0], roundedRect2Segments[0], Axis.X) ||
    doSegmentsIntersectOnProjection(roundedRect1Segments[1], roundedRect2Segments[1], Axis.Y)
  );
};


class RoundedRectElement {
  constructor(
    ctx: CanvasRenderingContext2D,
    x: number,
    y: number,
    w: number,
    h: number,
    borderRadius: number,
    boundRectColor: string = 'white',
    roundedRectColor: string = 'green',
    circlesColor: string = 'orange',
    circlesCentersColor: string = 'red',
    segmentsColor: string = 'blue',
  ) {
    this.ctx = ctx;
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
    this.borderRadius = borderRadius;
    this.boundRectColor = boundRectColor;
    this.roundedRectColor = roundedRectColor;
    this.circlesColor = circlesColor;
    this.circlesCentersColor = circlesCentersColor;
    this.segmentsColor = segmentsColor;
  }

  draw() {
    const path = new Path2D();

    path.rect(this.x, this.y, this.w, this.h);

    this.ctx.strokeStyle = this.boundRectColor;
    this.ctx.stroke(path);

    const path2 = new Path2D();

    path2.roundRect(this.x, this.y, this.w, this.h, this.borderRadius);

    this.ctx.strokeStyle = this.roundedRectColor;
    this.ctx.stroke(path2);

    const circlesCenters = getRoundedRectRoundedCornersCenters(this);

    for (const circleCenter of circlesCenters) {
      const center = new Path2D();

      center.arc(circleCenter.x, circleCenter.y, 4, 0, 2 * Math.PI);

      this.ctx.fillStyle = this.circlesCentersColor;
      this.ctx.fill(center);

      const circle = new Path2D();

      circle.arc(circleCenter.x, circleCenter.y, this.borderRadius, 0, 2 * Math.PI);

      this.ctx.strokeStyle = this.circlesColor;
      this.ctx.stroke(circle);
    }

    const segments = getRoundedRectSegments(this);

    for (const segment of segments) {
      const line = new Path2D();

      line.moveTo(segment.start.x, segment.start.y);
      line.lineTo(segment.end.x, segment.end.y);

      this.ctx.strokeStyle = this.segmentsColor;
      this.ctx.stroke(line);
    }
  }
};

const roundedRect1 = new RoundedRectElement(
  ctx,
  150,
  150,
  400,
  400,
  50
);
const roundedRect2 = new RoundedRectElement(
  ctx,
  0,
  0,
  125,
  100,
  25
);

const objects = [
  roundedRect1,
  roundedRect2
];

window.addEventListener('mousemove', (e) => {
  roundedRect2.x = e.offsetX;
  roundedRect2.y = e.offsetY;

  console.log(doRoundedRectsCollide(roundedRect1, roundedRect2));
});

const draw = () => {
  requestAnimationFrame(draw);

  ctx.clearRect(0, 0, canvas.width, canvas.height);

  objects.forEach(object => object.draw());
};

requestAnimationFrame(draw);
*,
*:before,
*:after {
  box-sizing: border-box;
  margin: 0;
  padding: 0;
}

html {
  height: 100%;
}

body {
  display: flex;
  justify-content: center;
  align-items: center;

  background-color: black;

  height: 100%;
}

canvas {
  background-color: black;
  outline: 2px solid white;
}
<canvas></canvas>

The algorithm passes my test so for me it works perfectly BUT i think that my algorithms is so complicated and can be simplified

Here is the main steps of my algorithm:

  1. Check if here is AABB collision. If not then return false
  2. Find centers of circles whcih create the rounded borders for both rects. Then check if any of circles of first rect collides with other ones. If yes then return true
  3. Find all segments for both rects. Then check if any of segments of first rect collides with other ones. If yes then return true
  4. Check if any of segments of first rect collides with circles other one. If yes then return true
  5. Check if any of segments of second rect collides with circles other one. If yes then return true
  6. Check if one of rect is inside another one. If yes the return true
  7. Return false

Can any of this steps be skipped?

May be some math can be simplifed. Beacuse I tried to find an easy solution for all steps and as I understand they cover a lot of cases which may be I don't need at all (for example my rects can't bu turned, so may be I can use this to simplifying or for optimization)

I would appreciate any help!

Solution

  • It seems inverse logic is simpler a bit:

    If AABB collision result is true - what case might give false for rectangles with rounded corners? I see only outer corner-corner case.

    enter image description here

    We can check now 4 collisions for "inner" AABB's - EFHG and KJIL versus analogues of the second rectangle

    If all results are false, we definitely have close corners case. So we determine what corners should be treated. Using components signs of vector between rectangle centers, we can select the only pair of corresponding corners and check whether radius sum is larger than circle-circle center distance