Kollisionserkennung von zwei Rektionen mit abgerundeten Grenzen ⇐ JavaScript

[Guest]

Ich habe einem Algorithmus geschrieben, wie man die Kollisionserkennung von zwei Rektionen mit abgerundeten Grenzen erfasst (der Code wurde unter Verwendung von TypeScript geschrieben, aber ich habe versucht, Dinge wie möglich so klar wie möglich zu nennen, um für irgendjemanden lesbar zu sein):

Code: Select all

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>
Der Algorithmus besteht aus meinem Test, so dass es für mich perfekt funktioniert, aber ich denke, dass Meine Algorithmen sind so kompliziert und können vereinfacht werden. Ist AABB -Kollision. Wenn nicht, geben Sie false 

[*] Finden Sie Zentren von Kreisen, die die abgerundeten Grenzen für beide Rektionen erstellen. Überprüfen Sie dann, ob einer der Kreise von zuerst rechte Rechte mit anderen kollidiert. Wenn ja, geben Sie True
[*] Finden Sie alle Segmente für beide Rektionen. Then check if any of segments of first rect collides with other ones. Wenn ja, geben Sie true
[*] Überprüfen Sie, ob eines der Segmente der ersten rechte Rechte mit einem anderen Kreis kollidiert. Wenn ja, geben Sie True
[*] Überprüfen Sie, ob eine der Segmente des zweiten Rechtecks ​​mit einem anderen Kreis kollidiert. Wenn ja, geben Sie True
[*] Überprüfen Sie, ob sich eines von einem anderen in einem anderen befindet. Wenn ja die Rückgabe true
[*] false

Kann eines dieser Schritte eines dieser Schritte können übersprungen werden? Beacuse, ich habe versucht, eine einfache Lösung für alle Schritte zu finden, und da ich verstehe, dass sie viele Fälle abdecken, die ich vielleicht überhaupt nicht brauche Vereinfachung oder Optimierung)
Ich würde mich über jede Hilfe freuen!