Пересечение многоугольника окружности
Если мяч движется и если вы можете убедиться, что мяч всегда начинается за пределами многоугольника, решение довольно простое.
Мы назовем мяч и его движение по линии мяча. Он начинается с текущего местоположения мяча и заканчивается в том положении, в котором мяч будет в следующем кадре.
Чтобы решить, вам нужно найти ближайшую точку пересечения с началом линии мяча.
Есть два типа точки пересечения.
- Отрезок линии (шаровая линия) с отрезком линии (край многоугольника)
- Сегмент линии (линия шара) с кругом (круг на каждом (только выпуклом) многоугольнике) угол)
В примере кода есть объект Lines2, содержащий две соответствующие функции перехвата. Перехватчики возвращаются как Vec2, содержащее два единичных расстояния. Функции перехвата предназначены для строк (бесконечной длины), а не для линий. Если точки пересечения нет, то возврат не определен.
Для линий пересечения Line2.unitInterceptsLine(line, result = new Vec2()) единицы измерения (в result) представляют собой единичное расстояние вдоль каждой строки от начала. отрицательные значения отстают от начала.
Чтобы учесть радиус шара, каждое ребро многоугольника смещено на радиус шара по нормали. Важно, чтобы края многоугольника имели постоянное направление. В этом примере нормаль находится справа от линии, а точки многоугольника расположены по часовой стрелке.
Для отрезков отрезка / круга Line2.unitInterceptsCircle(center, radius, result = new Vec2()) единицы измерения (в result) являются единицами измерения расстояние по линии, где он пересекает круг. result.x всегда будет содержать ближайшую точку пересечения (при условии, что вы начинаете за пределами круга). Если есть перехват, то способов всегда будет два, даже если они находятся в одной точке.
Пример
Пример содержит все, что необходимо
Интересующие объекты ball и poly
ball определяют мяч и его движение. Также есть код для его рисования для примера
poly содержит точки многоугольника. Преобразует точки в линии смещения в зависимости от радиуса шара. Он оптимизирован для вычисления линий только при изменении радиуса шара.
Функция poly.movingBallIntercept - это функция, которая выполняет всю работу. Он принимает шар и необязательный вектор результатов.
Он возвращает позицию Vec2 шара, если он касается многоугольника.
Он делает это, находя наименьшее единичное расстояние к линиям смещения и точка (в виде круга) и использует это единичное расстояние для позиционирования результата.
Обратите внимание на то, что если мяч находится внутри многоугольника, пересечения с углами меняются местами. Функция Line2.unitInterceptsCircle обеспечивает расстояние в 2 единицы, где линия входит в круг и выходит из него. Однако вам нужно знать, находитесь ли вы внутри или снаружи, чтобы знать, какой из них использовать. В этом примере предполагается, что вы находитесь за пределами многоугольника.
Инструкции
- Переместите мышь, чтобы изменить траекторию шариков.
- Щелкните, чтобы установить начальную позицию шариков.
Math.EPSILON = 1e-6;
Math.isSmall = val => Math.abs(val) < Math.EPSILON;
Math.isUnit = u => !(u < 0 || u > 1);
Math.TAU = Math.PI * 2;
/* export {Vec2, Line2} */ // this should be a module
var temp;
function Vec2(x = 0, y = (temp = x, x === 0 ? (x = 0 , 0) : (x = x.x, temp.y))) {
this.x = x;
this.y = y;
}
Vec2.prototype = {
init(x, y = (temp = x, x = x.x, temp.y)) { this.x = x; this.y = y; return this }, // assumes x is a Vec2 if y is undefined
copy() { return new Vec2(this) },
equal(v) { return (this.x - v.x) === 0 && (this.y - v.y) === 0 },
isUnits() { return Math.isUnit(this.x) && Math.isUnit(this.y) },
add(v, res = this) { res.x = this.x + v.x; res.y = this.y + v.y; return res },
sub(v, res = this) { res.x = this.x - v.x; res.y = this.y - v.y; return res },
scale(val, res = this) { res.x = this.x * val; res.y = this.y * val; return res },
invScale(val, res = this) { res.x = this.x / val; res.y = this.y / val; return res },
dot(v) { return this.x * v.x + this.y * v.y },
uDot(v, div) { return (this.x * v.x + this.y * v.y) / div },
cross(v) { return this.x * v.y - this.y * v.x },
uCross(v, div) { return (this.x * v.y - this.y * v.x) / div },
get length() { return this.lengthSqr ** 0.5 },
set length(l) { this.scale(l / this.length) },
get lengthSqr() { return this.x * this.x + this.y * this.y },
rot90CW(res = this) {
const y = this.x;
res.x = -this.y;
res.y = y;
return res;
},
};
const wV1 = new Vec2(), wV2 = new Vec2(), wV3 = new Vec2(); // pre allocated work vectors used by Line2 functions
function Line2(p1 = new Vec2(), p2 = (temp = p1, p1 = p1.p1 ? p1.p1 : p1, temp.p2 ? temp.p2 : new Vec2())) {
this.p1 = p1;
this.p2 = p2;
}
Line2.prototype = {
init(p1, p2 = (temp = p1, p1 = p1.p1, temp.p2)) { this.p1.init(p1); this.p2.init(p2) },
copy() { return new Line2(this) },
asVec(res = new Vec2()) { return this.p2.sub(this.p1, res) },
unitDistOn(u, res = new Vec2()) { return this.p2.sub(this.p1, res).scale(u).add(this.p1) },
translate(vec, res = this) {
this.p1.add(vec, res.p1);
this.p2.add(vec, res.p2);
return res;
},
translateNormal(amount, res = this) {
this.asVec(wV1).rot90CW().length = -amount;
this.translate(wV1, res);
return res;
},
unitInterceptsLine(line, res = new Vec2()) { // segments
this.asVec(wV1);
line.asVec(wV2);
const c = wV1.cross(wV2);
if (Math.isSmall(c)) { return }
wV3.init(this.p1).sub(line.p1);
res.init(wV1.uCross(wV3, c), wV2.uCross(wV3, c));
return res;
},
unitInterceptsCircle(point, radius, res = new Vec2()) {
this.asVec(wV1);
var b = -2 * this.p1.sub(point, wV2).dot(wV1);
const c = 2 * wV1.lengthSqr;
const d = (b * b - 2 * c * (wV2.lengthSqr - radius * radius)) ** 0.5
if (isNaN(d)) { return }
return res.init((b - d) / c, (b + d) / c);
},
};
/* END of file */ // Vec2 and Line2 module
/* import {vec2, Line2} from "whateverfilename.jsm" */ // Should import vec2 and line2
const POLY_SCALE = 0.5;
const ball = {
pos: new Vec2(-150,0),
delta: new Vec2(10, 10),
radius: 20,
drawPath(ctx) {
ctx.beginPath();
ctx.arc(this.pos.x, this.pos.y, this.radius, 0, Math.TAU);
ctx.stroke();
},
}
const poly = {
bRadius: 0,
lines: [],
set ballRadius(radius) {
const len = this.points.length
this.bRadius = ball.radius;
i = 0;
while (i < len) {
let line = this.lines[i];
if (line) { line.init(this.points[i], this.points[(i + 1) % len]) }
else { line = new Line2(new Vec2(this.points[i]), new Vec2(this.points[(i + 1) % len])) }
this.lines[i++] = line.translateNormal(radius);
}
this.lines.length = i;
},
points: [
new Vec2(-200, -150).scale(POLY_SCALE),
new Vec2(200, -100).scale(POLY_SCALE),
new Vec2(100, 0).scale(POLY_SCALE),
new Vec2(200, 100).scale(POLY_SCALE),
new Vec2(-200, 75).scale(POLY_SCALE),
new Vec2(-150, -50).scale(POLY_SCALE),
],
drawBallLines(ctx) {
if (this.lines.length) {
const r = this.bRadius;
ctx.beginPath();
for (const l of this.lines) {
ctx.moveTo(l.p1.x, l.p1.y);
ctx.lineTo(l.p2.x, l.p2.y);
}
for (const p of this.points) {
ctx.moveTo(p.x + r, p.y);
ctx.arc(p.x, p.y, r, 0, Math.TAU);
}
ctx.stroke()
}
},
drawPath(ctx) {
ctx.beginPath();
for (const p of this.points) { ctx.lineTo(p.x, p.y) }
ctx.closePath();
ctx.stroke();
},
movingBallIntercept(ball, res = new Vec2()) {
if (this.bRadius !== ball.radius) { this.ballRadius = ball.radius }
var i = 0, nearest = Infinity, nearestGeom, units = new Vec2();
const ballT = new Line2(ball.pos, ball.pos.add(ball.delta, new Vec2()));
for (const p of this.points) {
const res = ballT.unitInterceptsCircle(p, ball.radius, units);
if (res && units.x < nearest && Math.isUnit(units.x)) { // assumes ball started outside poly so only need first point
nearest = units.x;
nearestGeom = ballT;
}
}
for (const line of this.lines) {
const res = line.unitInterceptsLine(ballT, units);
if (res && units.x < nearest && units.isUnits()) { // first unit.x is for unit dist on line
nearest = units.x;
nearestGeom = ballT;
}
}
if (nearestGeom) { return ballT.unitDistOn(nearest, res) }
return;
},
}
const ctx = canvas.getContext("2d");
var w = canvas.width, cw = w / 2;
var h = canvas.height, ch = h / 2
requestAnimationFrame(mainLoop);
// line and point for displaying mouse interaction. point holds the result if any
const line = new Line2(ball.pos, ball.pos.add(ball.delta, new Vec2())), point = new Vec2();
function mainLoop() {
ctx.setTransform(1,0,0,1,0,0); // reset transform
if(w !== innerWidth || h !== innerHeight){
cw = (w = canvas.width = innerWidth) / 2;
ch = (h = canvas.height = innerHeight) / 2;
}else{
ctx.clearRect(0,0,w,h);
}
ctx.setTransform(1,0,0,1,cw,ch); // center to canvas
if (mouse.button) { ball.pos.init(mouse.x - cw, mouse.y - ch) }
line.p2.init(mouse.x - cw, mouse.y - ch);
line.p2.sub(line.p1, ball.delta);
ctx.lineWidth = 1;
ctx.strokeStyle = "#000"
poly.drawPath(ctx)
ctx.strokeStyle = "#F804"
poly.drawBallLines(ctx);
ctx.strokeStyle = "#F00"
ctx.beginPath();
ctx.arc(ball.pos.x, ball.pos.y, ball.radius, 0, Math.TAU);
ctx.moveTo(line.p1.x, line.p1.y);
ctx.lineTo(line.p2.x, line.p2.y);
ctx.stroke();
ctx.strokeStyle = "#00f"
ctx.lineWidth = 2;
ctx.beginPath();
if (poly.movingBallIntercept(ball, point)) {
ctx.arc(point.x, point.y, ball.radius, 0, Math.TAU);
} else {
ctx.arc(line.p2.x, line.p2.y, ball.radius, 0, Math.TAU);
}
ctx.stroke();
requestAnimationFrame(mainLoop);
}
const mouse = {x:0, y:0, button: false};
function mouseEvents(e) {
const bounds = canvas.getBoundingClientRect();
mouse.x = e.pageX - bounds.left - scrollX;
mouse.y = e.pageY - bounds.top - scrollY;
mouse.button = e.type === "mousedown" ? true : e.type === "mouseup" ? false : mouse.button;
}
["mousedown","mouseup","mousemove"].forEach(name => document.addEventListener(name,mouseEvents));
#canvas {
position: absolute;
top: 0px;
left: 0px;
}
<canvas id="canvas"></canvas>
Click to position ball. Move mouse to test trajectory
Vec2 и Line2
Чтобы упростить задачу, поможет векторная библиотека. В этом примере я написал быстрые объекты Vec2 и Line2 (обратите внимание, что были протестированы только функции, используемые в примере, Примечание: объект предназначен для повышения производительности, неопытным кодировщикам следует избегать использования этих объектов и выбирать более стандартный вектор и линейная библиотека)