Обнаружение столкновений двух прямы с округлыми границами ⇐ Javascript

[Anonymous]

Я написал алгоритм, как обнаружить обнаружение столкновений двух прямолинейных границ (код был написан с использованием TypeScript, но я старался называть вещи как можно более четкими, чтобы код был читаемым для всех):

Код: Выделить всё

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

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) 
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.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) 
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,
50,
50,
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);< /code>
*,
*: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;
}< /code>
< /code>
< /div>
< /div>
< /p>
Алгоритм проходит мой тест, так что для меня он работает отлично, но я думаю, что это Мои алгоритмы настолько сложны и могут быть упрощены < /p>
Вот основные шаги моего алгоритма: < /p>
[list]
[*] Проверьте, если здесь является AABB Collision. Если нет, то верните false 

[*] Найдите центры кругов. Затем проверьте, не сталкиваются ли какие -либо круги первого прямого прямо с другими. Если да, то верните True
[*] Найдите все сегменты для обоих прямолинейных. Затем проверьте, сталкиваются ли какие -либо из сегментов первого прямого прямого прямо с другими. Если да, то верните True
[*] Проверьте, сталкивается ли какой -либо из сегментов первого прямого прямого прямого с другими кругами. Если да, то верните True
[*] Проверьте, сталкивается ли какой -либо из сегментов второго прямого прямо с другими кругами. Если да, то верните True
[*] Проверьте, находится ли один из прямолинейных. Если да, возврат true
[*] вернуть false
[/list]
может любой из этих шагов быть пропущенным? Beacuse я попытался найти простое решение для всех шагов, и, как я понимаю, они охватывают множество случаев, которые, возможно, мне вообще не нужно (например, мои прямые не могут повернуть, так что, возможно, я могу использовать это, чтобы упрощение или для оптимизации)
Я был бы признателен за любую помощь!

Подробнее здесь: https://stackoverflow.com/questions/794 ... ed-borders