点 A から点 B までの直線があります。両方の点の (x,y) があります。また、B を中心とする長方形と、長方形の幅と高さもあります。
長方形と交差する線の点を見つける必要があります。その点の (x,y) を求める式はありますか?
70184 次
13 に答える
26
点 A は常に長方形の外側にあり、点 B は常に長方形の中心にあります。
長方形が軸に沿って配置されていると仮定すると、これは非常に単純になります。
直線の傾きは s = (Ay - By)/(Ax - Bx) です。
- -h/2 <= s * w/2 <= h/2 の場合、線は交差します。
- Ax > Bx の場合は右端
- Ax < Bx の場合は左端。
- -w/2 <= (h/2)/s <= w/2 の場合、線は交差します。
- Ay > By の場合は上端
- Ay < By の場合は下端。
交差するエッジが分かれば、1 つの座標がわかります: x = Bx ± w/2 または y = By ± h/2 は、ヒットするエッジに応じて異なります。もう 1 つの座標は、y = By + s * w/2 または x = Bx + (h/2)/s で与えられます。
于 2009-10-18T18:18:43.123 に答える
23
/**
* Finds the intersection point between
* * the rectangle
* with parallel sides to the x and y axes
* * the half-line pointing towards (x,y)
* originating from the middle of the rectangle
*
* Note: the function works given min[XY] <= max[XY],
* even though minY may not be the "top" of the rectangle
* because the coordinate system is flipped.
* Note: if the input is inside the rectangle,
* the line segment wouldn't have an intersection with the rectangle,
* but the projected half-line does.
* Warning: passing in the middle of the rectangle will return the midpoint itself
* there are infinitely many half-lines projected in all directions,
* so let's just shortcut to midpoint (GIGO).
*
* @param x:Number x coordinate of point to build the half-line from
* @param y:Number y coordinate of point to build the half-line from
* @param minX:Number the "left" side of the rectangle
* @param minY:Number the "top" side of the rectangle
* @param maxX:Number the "right" side of the rectangle
* @param maxY:Number the "bottom" side of the rectangle
* @param validate:boolean (optional) whether to treat point inside the rect as error
* @return an object with x and y members for the intersection
* @throws if validate == true and (x,y) is inside the rectangle
* @author TWiStErRob
* @licence Dual CC0/WTFPL/Unlicence, whatever floats your boat
* @see <a href="http://stackoverflow.com/a/31254199/253468">source</a>
* @see <a href="http://stackoverflow.com/a/18292964/253468">based on</a>
*/
function pointOnRect(x, y, minX, minY, maxX, maxY, validate) {
//assert minX <= maxX;
//assert minY <= maxY;
if (validate && (minX < x && x < maxX) && (minY < y && y < maxY))
throw "Point " + [x,y] + "cannot be inside "
+ "the rectangle: " + [minX, minY] + " - " + [maxX, maxY] + ".";
var midX = (minX + maxX) / 2;
var midY = (minY + maxY) / 2;
// if (midX - x == 0) -> m == ±Inf -> minYx/maxYx == x (because value / ±Inf = ±0)
var m = (midY - y) / (midX - x);
if (x <= midX) { // check "left" side
var minXy = m * (minX - x) + y;
if (minY <= minXy && minXy <= maxY)
return {x: minX, y: minXy};
}
if (x >= midX) { // check "right" side
var maxXy = m * (maxX - x) + y;
if (minY <= maxXy && maxXy <= maxY)
return {x: maxX, y: maxXy};
}
if (y <= midY) { // check "top" side
var minYx = (minY - y) / m + x;
if (minX <= minYx && minYx <= maxX)
return {x: minYx, y: minY};
}
if (y >= midY) { // check "bottom" side
var maxYx = (maxY - y) / m + x;
if (minX <= maxYx && maxYx <= maxX)
return {x: maxYx, y: maxY};
}
// edge case when finding midpoint intersection: m = 0/0 = NaN
if (x === midX && y === midY) return {x: x, y: y};
// Should never happen :) If it does, please tell me!
throw "Cannot find intersection for " + [x,y]
+ " inside rectangle " + [minX, minY] + " - " + [maxX, maxY] + ".";
}
(function tests() {
var left = 100, right = 200, top = 50, bottom = 150; // a square, really
var hMiddle = (left + right) / 2, vMiddle = (top + bottom) / 2;
function intersectTestRect(x, y) { return pointOnRect(x,y, left,top, right,bottom, true); }
function intersectTestRectNoValidation(x, y) { return pointOnRect(x,y, left,top, right,bottom, false); }
function checkTestRect(x, y) { return function() { return pointOnRect(x,y, left,top, right,bottom, true); }; }
QUnit.test("intersects left side", function(assert) {
var leftOfRect = 0, closerLeftOfRect = 25;
assert.deepEqual(intersectTestRect(leftOfRect, 25), {x:left, y:75}, "point above top");
assert.deepEqual(intersectTestRect(closerLeftOfRect, top), {x:left, y:80}, "point in line with top");
assert.deepEqual(intersectTestRect(leftOfRect, 70), {x:left, y:90}, "point above middle");
assert.deepEqual(intersectTestRect(leftOfRect, vMiddle), {x:left, y:100}, "point exact middle");
assert.deepEqual(intersectTestRect(leftOfRect, 130), {x:left, y:110}, "point below middle");
assert.deepEqual(intersectTestRect(closerLeftOfRect, bottom), {x:left, y:120}, "point in line with bottom");
assert.deepEqual(intersectTestRect(leftOfRect, 175), {x:left, y:125}, "point below bottom");
});
QUnit.test("intersects right side", function(assert) {
var rightOfRect = 300, closerRightOfRect = 250;
assert.deepEqual(intersectTestRect(rightOfRect, 25), {x:right, y:75}, "point above top");
assert.deepEqual(intersectTestRect(closerRightOfRect, top), {x:right, y:75}, "point in line with top");
assert.deepEqual(intersectTestRect(rightOfRect, 70), {x:right, y:90}, "point above middle");
assert.deepEqual(intersectTestRect(rightOfRect, vMiddle), {x:right, y:100}, "point exact middle");
assert.deepEqual(intersectTestRect(rightOfRect, 130), {x:right, y:110}, "point below middle");
assert.deepEqual(intersectTestRect(closerRightOfRect, bottom), {x:right, y:125}, "point in line with bottom");
assert.deepEqual(intersectTestRect(rightOfRect, 175), {x:right, y:125}, "point below bottom");
});
QUnit.test("intersects top side", function(assert) {
var aboveRect = 0;
assert.deepEqual(intersectTestRect(80, aboveRect), {x:115, y:top}, "point left of left");
assert.deepEqual(intersectTestRect(left, aboveRect), {x:125, y:top}, "point in line with left");
assert.deepEqual(intersectTestRect(120, aboveRect), {x:135, y:top}, "point left of middle");
assert.deepEqual(intersectTestRect(hMiddle, aboveRect), {x:150, y:top}, "point exact middle");
assert.deepEqual(intersectTestRect(180, aboveRect), {x:165, y:top}, "point right of middle");
assert.deepEqual(intersectTestRect(right, aboveRect), {x:175, y:top}, "point in line with right");
assert.deepEqual(intersectTestRect(220, aboveRect), {x:185, y:top}, "point right of right");
});
QUnit.test("intersects bottom side", function(assert) {
var belowRect = 200;
assert.deepEqual(intersectTestRect(80, belowRect), {x:115, y:bottom}, "point left of left");
assert.deepEqual(intersectTestRect(left, belowRect), {x:125, y:bottom}, "point in line with left");
assert.deepEqual(intersectTestRect(120, belowRect), {x:135, y:bottom}, "point left of middle");
assert.deepEqual(intersectTestRect(hMiddle, belowRect), {x:150, y:bottom}, "point exact middle");
assert.deepEqual(intersectTestRect(180, belowRect), {x:165, y:bottom}, "point right of middle");
assert.deepEqual(intersectTestRect(right, belowRect), {x:175, y:bottom}, "point in line with right");
assert.deepEqual(intersectTestRect(220, belowRect), {x:185, y:bottom}, "point right of right");
});
QUnit.test("intersects a corner", function(assert) {
assert.deepEqual(intersectTestRect(left-50, top-50), {x:left, y:top}, "intersection line aligned with top-left corner");
assert.deepEqual(intersectTestRect(right+50, top-50), {x:right, y:top}, "intersection line aligned with top-right corner");
assert.deepEqual(intersectTestRect(left-50, bottom+50), {x:left, y:bottom}, "intersection line aligned with bottom-left corner");
assert.deepEqual(intersectTestRect(right+50, bottom+50), {x:right, y:bottom}, "intersection line aligned with bottom-right corner");
});
QUnit.test("on the corners", function(assert) {
assert.deepEqual(intersectTestRect(left, top), {x:left, y:top}, "top-left corner");
assert.deepEqual(intersectTestRect(right, top), {x:right, y:top}, "top-right corner");
assert.deepEqual(intersectTestRect(right, bottom), {x:right, y:bottom}, "bottom-right corner");
assert.deepEqual(intersectTestRect(left, bottom), {x:left, y:bottom}, "bottom-left corner");
});
QUnit.test("on the edges", function(assert) {
assert.deepEqual(intersectTestRect(hMiddle, top), {x:hMiddle, y:top}, "top edge");
assert.deepEqual(intersectTestRect(right, vMiddle), {x:right, y:vMiddle}, "right edge");
assert.deepEqual(intersectTestRect(hMiddle, bottom), {x:hMiddle, y:bottom}, "bottom edge");
assert.deepEqual(intersectTestRect(left, vMiddle), {x:left, y:vMiddle}, "left edge");
});
QUnit.test("validates inputs", function(assert) {
assert.throws(checkTestRect(hMiddle, vMiddle), /cannot be inside/, "center");
assert.throws(checkTestRect(hMiddle-10, vMiddle-10), /cannot be inside/, "top left of center");
assert.throws(checkTestRect(hMiddle-10, vMiddle), /cannot be inside/, "left of center");
assert.throws(checkTestRect(hMiddle-10, vMiddle+10), /cannot be inside/, "bottom left of center");
assert.throws(checkTestRect(hMiddle, vMiddle-10), /cannot be inside/, "above center");
assert.throws(checkTestRect(hMiddle, vMiddle), /cannot be inside/, "center");
assert.throws(checkTestRect(hMiddle, vMiddle+10), /cannot be inside/, "below center");
assert.throws(checkTestRect(hMiddle+10, vMiddle-10), /cannot be inside/, "top right of center");
assert.throws(checkTestRect(hMiddle+10, vMiddle), /cannot be inside/, "right of center");
assert.throws(checkTestRect(hMiddle+10, vMiddle+10), /cannot be inside/, "bottom right of center");
assert.throws(checkTestRect(left+10, vMiddle-10), /cannot be inside/, "right of left edge");
assert.throws(checkTestRect(left+10, vMiddle), /cannot be inside/, "right of left edge");
assert.throws(checkTestRect(left+10, vMiddle+10), /cannot be inside/, "right of left edge");
assert.throws(checkTestRect(right-10, vMiddle-10), /cannot be inside/, "left of right edge");
assert.throws(checkTestRect(right-10, vMiddle), /cannot be inside/, "left of right edge");
assert.throws(checkTestRect(right-10, vMiddle+10), /cannot be inside/, "left of right edge");
assert.throws(checkTestRect(hMiddle-10, top+10), /cannot be inside/, "below top edge");
assert.throws(checkTestRect(hMiddle, top+10), /cannot be inside/, "below top edge");
assert.throws(checkTestRect(hMiddle+10, top+10), /cannot be inside/, "below top edge");
assert.throws(checkTestRect(hMiddle-10, bottom-10), /cannot be inside/, "above bottom edge");
assert.throws(checkTestRect(hMiddle, bottom-10), /cannot be inside/, "above bottom edge");
assert.throws(checkTestRect(hMiddle+10, bottom-10), /cannot be inside/, "above bottom edge");
});
QUnit.test("doesn't validate inputs", function(assert) {
assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle-10), {x:left, y:top}, "top left of center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle), {x:left, y:vMiddle}, "left of center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle+10), {x:left, y:bottom}, "bottom left of center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle-10), {x:hMiddle, y:top}, "above center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle), {x:hMiddle, y:vMiddle}, "center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle+10), {x:hMiddle, y:bottom}, "below center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle-10), {x:right, y:top}, "top right of center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle), {x:right, y:vMiddle}, "right of center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle+10), {x:right, y:bottom}, "bottom right of center");
});
})();<link href="https://code.jquery.com/qunit/qunit-2.3.2.css" rel="stylesheet"/>
<script src="https://code.jquery.com/qunit/qunit-2.3.2.js"></script>
<div id="qunit"></div>于 2015-07-06T19:37:16.397 に答える
19
Graphics Gemsをチェックしてみてください。これは、グラフィックスの古典的なルーチン セットであり、必要なアルゴリズムの多くが含まれています。これは C で作成されており、少し古くなっていますが、アルゴリズムは今でも輝きを放っており、他の言語に移行するのは簡単なはずです。
現在の問題については、長方形の 4 つの線を作成し、指定された線と交差するものを確認してください。
于 2009-10-18T18:31:39.087 に答える
10
線分 (最初の 4 つのパラメーター) が軸に沿った長方形 (最後の 4 つのパラメーター) と交差する場合に true を返す Java のソリューションを次に示します。ブール値の代わりに交点を返すのは簡単です。最初に完全に外側かどうかをチェックし、それ以外の場合は直線方程式を使用して機能しますy=m*x+b。長方形を構成する線は軸が揃っていることがわかっているので、チェックは簡単です。
public boolean aabbContainsSegment (float x1, float y1, float x2, float y2, float minX, float minY, float maxX, float maxY) {
// Completely outside.
if ((x1 <= minX && x2 <= minX) || (y1 <= minY && y2 <= minY) || (x1 >= maxX && x2 >= maxX) || (y1 >= maxY && y2 >= maxY))
return false;
float m = (y2 - y1) / (x2 - x1);
float y = m * (minX - x1) + y1;
if (y > minY && y < maxY) return true;
y = m * (maxX - x1) + y1;
if (y > minY && y < maxY) return true;
float x = (minY - y1) / m + x1;
if (x > minX && x < maxX) return true;
x = (maxY - y1) / m + x1;
if (x > minX && x < maxX) return true;
return false;
}
セグメントの始点または終点が四角形の内側にある場合はショートカットできますが、計算を行うほうがよいでしょう。セグメントの一方または両方の終点が内側にある場合は常に true が返されます。とにかくショートカットが必要な場合は、「完全に外側」チェックの後に以下のコードを挿入します。
// Start or end inside.
if ((x1 > minX && x1 < maxX && y1 > minY && y1 < maxY) || (x2 > minX && x2 < maxX && y2 > minY && y2 < maxY)) return true;
于 2013-08-17T20:20:31.457 に答える
3
私は数学のファンではありませんし、他の言語からの翻訳を特に楽しんでいるわけでもありません (他の人が既に翻訳を行っている場合)。誰かが二重の仕事をするのを防ぐために。
したがって、この交差コードを C# で使用する場合は、ここを参照してくださいhttp://dotnetbyexample.blogspot.nl/2013/09/utility-classes-to-check-if-lines-andor.html
于 2013-10-04T16:12:42.467 に答える
3
そのためのプログラムは提供しませんが、次の方法で実行できます。
- 線の角度を計算する
- 長方形の中心から角の 1 つまでの線の角度を計算する
- 角度に基づいて、線が長方形と交差する側を決定します
- 長方形の辺と直線の交点を計算する
于 2009-10-18T17:52:28.073 に答える
2
特に同じ四角形で多くの線をテストすることを計画している場合に考慮できるもう 1 つのオプションは、座標系を変換して軸を四角形の対角線に揃えることです。次に、線または光線が長方形の中心から始まるため、角度を決定でき、角度によって交差するセグメントを知ることができます (つまり、<90 度セグメント 1、90 度 < <180 度セグメント 2 など...)。もちろん、元の座標系に戻す必要があります
これはより多くの作業のように見えますが、変換行列とその逆行列を一度計算してから再利用できます。これは、象限や 3D の面との交点などを考慮する必要がある高次元の四角形にも簡単に拡張できます。
于 2016-01-20T07:21:55.747 に答える
1
これが最善の方法かどうかはわかりませんが、できることは、長方形の内側にある線の割合を把握することです。長方形の幅と、A と B の x 座標 (または高さと y 座標) の差からそれを取得できます。幅と高さに基づいて、どのケースが適用されるかを確認できます。他のケースは拡張機能になります。長方形の一辺の）。これを取得したら、B から A へのベクトルのその比率を取得するだけで、交点の座標が得られます。
于 2009-10-18T17:56:21.117 に答える
0
基本的な数学のみを使用して、(無限の) 線と四角形の間の交差間隔を返す、少し冗長なメソッドを次に示します。
// Line2 - 2D line with origin (= offset from 0,0) and direction
// Rectangle2 - 2D rectangle by min and max points
// Contacts - Stores entry and exit times of a line through a convex shape
Contacts findContacts(const Line2 &line, const Rectangle2 &rect) {
Contacts contacts;
// If the line is not parallel to the Y axis, find out when it will cross
// the limits of the rectangle horizontally
if(line.Direction.X != 0.0f) {
float leftTouch = (rect.Min.X - line.Origin.X) / line.Direction.X;
float rightTouch = (rect.Max.X - line.Origin.X) / line.Direction.X;
contacts.Entry = std::fmin(leftTouch, rightTouch);
contacts.Exit = std::fmax(leftTouch, rightTouch);
} else if((line.Offset.X < rect.Min.X) || (line.Offset.X >= rect.Max.X)) {
return Contacts::None; // Rectangle missed by vertical line
}
// If the line is not parallel to the X axis, find out when it will cross
// the limits of the rectangle vertically
if(line.Direction.Y != 0.0f) {
float topTouch = (rectangle.Min.Y - line.Offset.Y) / line.Direction.Y;
float bottomTouch = (rectangle.Max.Y - line.Offset.Y) / line.Direction.Y;
// If the line is parallel to the Y axis (and it goes through
// the rectangle), only the Y axis needs to be taken into account.
if(line.Direction.X == 0.0f) {
contacts.Entry = std::fmin(topTouch, bottomTouch);
contacts.Exit = std::fmax(topTouch, bottomTouch);
} else {
float verticalEntry = std::fmin(topTouch, bottomTouch);
float verticalExit = std::fmax(topTouch, bottomTouch);
// If the line already left the rectangle on one axis before entering it
// on the other, it has missed the rectangle.
if((verticalExit < contacts.Entry) || (contacts.Exit < verticalEntry)) {
return Contacts::None;
}
// Restrict the intervals from the X axis of the rectangle to where
// the line is also within the limits of the rectangle on the Y axis
contacts.Entry = std::fmax(verticalEntry, contacts.Entry);
contacts.Exit = std::fmin(verticalExit, contacts.Exit);
}
} else if((line.Offset.Y < rect.Min.Y) || (line.Offset.Y > rect.Max.Y)) {
return Contacts::None; // Rectangle missed by horizontal line
}
return contacts;
}
このアプローチは高度な数値安定性を提供します (区間は、すべての場合において、1 回の減算と除算の結果です) が、いくつかの分岐が含まれます。
ライン セグメント (始点と終点を含む) の場合、セグメントの始点を原点として、方向として指定する必要がありますend - start。2 つの交点の座標の計算は、entryPoint = origin + direction * contacts.Entryおよびとして簡単exitPoint = origin + direction * contacts.Exitです。
于 2014-03-04T10:45:24.980 に答える