خوارزمية الكشف عن تصادم قطاع الخط الدائري؟
https://stackoverflow.com/questions/1073336
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لدي خط من A إلى B ودائرة موضوعة عند C ونصف قطرها R.
ما هي الخوارزمية الجيدة التي يجب استخدامها للتحقق مما إذا كان الخط يتقاطع مع الدائرة؟وفي أي إحداثية على طول حافة الدوائر حدث ذلك؟
المحلول
مع الأخذ
- ه هي نقطة بداية الشعاع،
- ل هي نقطة نهاية الشعاع،
- ج هو مركز الكرة الذي تختبره
- ص هو نصف قطر تلك الكرة
إحصاء - عد:
د = L - E ( متجه اتجاه الشعاع من البداية إلى النهاية )
F = E - C (المتجه من الكرة المركزية إلى بداية الشعاع)
ومن ثم يتم العثور على التقاطع ..
التوصيل:
ف = ه + ر * د
هذه معادلة بارامترية:
صس = هس + دس
صذ = هذ + دذ
داخل
(س - ح)2 + (ص - ك)2 = ص2
(ح،ك) = مركز الدائرة.
ملحوظة:لقد قمنا بتبسيط المشكلة إلى ثنائية الأبعاد هنا، والحل الذي حصلنا عليه ينطبق أيضًا على الأبعاد الثلاثية
تحصل:
- يوسع
س2 - 2xح + ح2 + ص2 - 2 سنة + ك2 - ص2 = 0 - سدادة
س = هس + دس
ص = هذ + دذ
(هس + دس )2 - 2( هس + دس ) ح + ح2 + (هـذ + دذ )2 - 2( هذ + دذ ) ك + ك2 - ص2 = 0 - ينفجر
هس2 + 2هسtdس + ر2دس2 - 2هسح - 2tdسح + ح2 + هذ2 + 2هذtdذ + ر2دذ2 - 2هذك - 2tdذك + ك2 - ص2 = 0 - مجموعة
ر2( دس2 + دذ2 ) + 2T (هـسدس + هذدذ - دسعالية الدقةذك) + هـس2 + هذ2 - 2eسح - 2هذك + ح2 + ك2 - ص2 = 0 - أخيراً،
ر2( _d * _d ) + 2t( _e * _d - _d * _c ) + _e * _e - 2( _e*_c ) + _c * _c - r2 = 0
*حيث _d هو المتجه d و * هو حاصل الضرب النقطي.* - وثم،
ر2( _d * _d ) + 2t( _d * ( _e - _c ) ) + ( _e - _c ) * ( _e - _c ) - r2 = 0 - ترك _f = _e - _c
ر2( _d * _d ) + 2t( _d * _f ) + _f * _f - r2 = 0
لذلك نحصل على:
ر2 * (d DOT d) + 2t*( f DOT d ) + ( f DOT f - r2 ) = 0
إذن حل المعادلة التربيعية:
float a = d.Dot( d ) ;
float b = 2*f.Dot( d ) ;
float c = f.Dot( f ) - r*r ;
float discriminant = b*b-4*a*c;
if( discriminant < 0 )
{
// no intersection
}
else
{
// ray didn't totally miss sphere,
// so there is a solution to
// the equation.
discriminant = sqrt( discriminant );
// either solution may be on or off the ray so need to test both
// t1 is always the smaller value, because BOTH discriminant and
// a are nonnegative.
float t1 = (-b - discriminant)/(2*a);
float t2 = (-b + discriminant)/(2*a);
// 3x HIT cases:
// -o-> --|--> | | --|->
// Impale(t1 hit,t2 hit), Poke(t1 hit,t2>1), ExitWound(t1<0, t2 hit),
// 3x MISS cases:
// -> o o -> | -> |
// FallShort (t1>1,t2>1), Past (t1<0,t2<0), CompletelyInside(t1<0, t2>1)
if( t1 >= 0 && t1 <= 1 )
{
// t1 is the intersection, and it's closer than t2
// (since t1 uses -b - discriminant)
// Impale, Poke
return true ;
}
// here t1 didn't intersect so we are either started
// inside the sphere or completely past it
if( t2 >= 0 && t2 <= 1 )
{
// ExitWound
return true ;
}
// no intn: FallShort, Past, CompletelyInside
return false ;
}
نصائح أخرى
ويبدو أن لا أحد ينظر الإسقاط، أنا تماما عن مسارها هنا؟
ومشروع لAC ناقلات على AB. متجه المتوقعة، AD، يعطي D نقطة جديدة.
إذا كانت المسافة بين D وC أصغر من (أو يساوي) R لدينا التقاطع.
ومثل هذا:
وأود أن استخدام خوارزمية لحساب المسافة بين (مركز الدائرة) نقطة والخط (خط AB). ويمكن بعد ذلك أن تستخدم هذا لتحديد نقطة تقاطع الخط مع الدائرة.
ودعونا نقول لدينا النقاط A، B، C. فأس وآي هي x و مكونات ذ النقاط A. الشيء نفسه بالنسبة لB و C. والعددية R هو نصف قطر الدائرة.
وتتطلب هذه الخوارزمية التي A، B و C وجهات متميزة وأن R ليس 0.
وهنا هو خوارزمية
// compute the euclidean distance between A and B
LAB = sqrt( (Bx-Ax)²+(By-Ay)² )
// compute the direction vector D from A to B
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB
// the equation of the line AB is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= LAB.
// compute the distance between the points A and E, where
// E is the point of AB closest the circle center (Cx, Cy)
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)
// compute the coordinates of the point E
Ex = t*Dx+Ax
Ey = t*Dy+Ay
// compute the euclidean distance between E and C
LEC = sqrt((Ex-Cx)²+(Ey-Cy)²)
// test if the line intersects the circle
if( LEC < R )
{
// compute distance from t to circle intersection point
dt = sqrt( R² - LEC²)
// compute first intersection point
Fx = (t-dt)*Dx + Ax
Fy = (t-dt)*Dy + Ay
// compute second intersection point
Gx = (t+dt)*Dx + Ax
Gy = (t+dt)*Dy + Ay
}
// else test if the line is tangent to circle
else if( LEC == R )
// tangent point to circle is E
else
// line doesn't touch circle
حسنًا، لن أعطيك رمزًا، ولكن بما أنك قمت بوضع علامة على هذا خوارزمية, ، لا أعتقد أن هذا سيهمك.أولاً، عليك الحصول على متجه عمودي على الخط.
سيكون لديك متغير غير معروف في y = ax + c ( c سوف تكون غير معروفة )
لحل ذلك، احسب قيمته عندما يمر الخط بمركز الدائرة.
إنه،
قم بتوصيل موقع مركز الدائرة بالمعادلة الخطية وحل من أجل c.
ثم احسب نقطة تقاطع الخط الأصلي مع وضعها الطبيعي.
سيعطيك هذا أقرب نقطة على الخط إلى الدائرة.
احسب المسافة بين هذه النقطة ومركز الدائرة (باستخدام حجم المتجه).
إذا كان هذا أقل من نصف قطر الدائرة، فلدينا تقاطع!
هناك طريقة أخرى تستخدم صيغة مساحة المثلث ABC.يعد اختبار التقاطع أبسط وأكثر كفاءة من طريقة الإسقاط، ولكن العثور على إحداثيات نقطة التقاطع يتطلب المزيد من العمل.على الأقل سوف يتأخر إلى النقطة المطلوبة.
صيغة حساب مساحة المثلث هي:المساحة = ب/2
حيث b هو طول القاعدة و h هو الارتفاع.لقد اخترنا القطعة AB لتكون القاعدة بحيث تكون h هي أقصر مسافة من C، مركز الدائرة، إلى الخط.
وبما أن مساحة المثلث يمكن حسابها أيضًا بواسطة منتج نقطي متجه، فيمكننا تحديد h.
// compute the triangle area times 2 (area = area2/2)
area2 = abs( (Bx-Ax)*(Cy-Ay) - (Cx-Ax)(By-Ay) )
// compute the AB segment length
LAB = sqrt( (Bx-Ax)² + (By-Ay)² )
// compute the triangle height
h = area2/LAB
// if the line intersects the circle
if( h < R )
{
...
}
التحديث 1 :
يمكنك تحسين الكود باستخدام حساب الجذر التربيعي العكسي السريع الموصوف هنا للحصول على تقريب جيد لـ 1/LAB.
حساب نقطة التقاطع ليس بالأمر الصعب.من هنا تبدأ
// compute the line AB direction vector components
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB
// compute the distance from A toward B of closest point to C
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)
// t should be equal to sqrt( (Cx-Ax)² + (Cy-Ay)² - h² )
// compute the intersection point distance from t
dt = sqrt( R² - h² )
// compute first intersection point coordinate
Ex = Ax + (t-dt)*Dx
Ey = Ay + (t-dt)*Dy
// compute second intersection point coordinate
Fx = Ax + (t+dt)*Dx
Fy = Ay + (t+dt)*Dy
إذا كانت h = R فإن الخط AB يكون مماسًا للدائرة وتكون القيمة dt = 0 وE = F.إحداثيات النقطة هي تلك الخاصة بـ E وF.
يجب عليك التحقق من أن A يختلف عن B وأن طول المقطع ليس فارغًا إذا كان هذا قد يحدث في التطبيق الخاص بك.
وكتبت نصي صغير لاختبار تقاطع من خلال إبراز نقطة مركز الدائرة إلى الخط.
vector distVector = centerPoint - projectedPoint;
if(distVector.length() < circle.radius)
{
double distance = circle.radius - distVector.length();
vector moveVector = distVector.normalize() * distance;
circle.move(moveVector);
}
http://jsfiddle.net/ercang/ornh3594/1/
إذا كنت تحتاج إلى التحقق من الاصطدام مع هذا الجزء، تحتاج أيضا إلى النظر في المسافة مركز الدائرة لبدء ونقطة نهاية.
vector distVector = centerPoint - startPoint;
if(distVector.length() < circle.radius)
{
double distance = circle.radius - distVector.length();
vector moveVector = distVector.normalize() * distance;
circle.move(moveVector);
}
وهذا الحل وجدت يبدو أسهل قليلا لمتابعة ثم بعض القضايا الأخرى.
وأخذ:
p1 and p2 as the points for the line, and
c as the center point for the circle and r for the radius
وأود أن حل للمعادلة الخط في شكل منحدر اعتراض. ومع ذلك، لم أكن أريد أن يكون التعامل مع المعادلات الصعبة مع c كنقطة، لذلك أنا فقط تحول نظام الإحداثيات أكثر من ذلك أن الدائرة هي في 0,0
p3 = p1 - c
p4 = p2 - c
وبالمناسبة، كلما طرح نقاط عن بعضها البعض وأنا طرح x وثم طرح في y، ووضعها موضع نقطة جديدة، فقط في حالة شخص لا يعرف.
وعلى أي حال، وأنا الآن حل للمعادلة الخط مع p3 وp4:
m = (p4_y - p3_y) / (p4_x - p3) (the underscore is an attempt at subscript)
y = mx + b
y - mx = b (just put in a point for x and y, and insert the m we found)
وطيب. الان انا بحاجة لتعيين هذه المعادلات على قدم المساواة. أولا أنا بحاجة إلى حل معادلة الدائرة لx
x^2 + y^2 = r^2
y^2 = r^2 - x^2
y = sqrt(r^2 - x^2)
وثم تعيين لي منها يساوي:
mx + b = sqrt(r^2 - x^2)
وحل للمعادلة من الدرجة الثانية (0 = ax^2 + bx + c):
(mx + b)^2 = r^2 - x^2
(mx)^2 + 2mbx + b^2 = r^2 - x^2
0 = m^2 * x^2 + x^2 + 2mbx + b^2 - r^2
0 = (m^2 + 1) * x^2 + 2mbx + b^2 - r^2
والآن لدي a، b، وc.
a = m^2 + 1
b = 2mb
c = b^2 - r^2
وهكذا أضع هذا في الصيغة التربيعية:
(-b ± sqrt(b^2 - 4ac)) / 2a
وبديلا في بالقيم ثم تبسيط قدر الإمكان:
(-2mb ± sqrt(b^2 - 4ac)) / 2a
(-2mb ± sqrt((-2mb)^2 - 4(m^2 + 1)(b^2 - r^2))) / 2(m^2 + 1)
(-2mb ± sqrt(4m^2 * b^2 - 4(m^2 * b^2 - m^2 * r^2 + b^2 - r^2))) / 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * b^2 - (m^2 * b^2 - m^2 * r^2 + b^2 - r^2))))/ 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * b^2 - m^2 * b^2 + m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2
(-2mb ± sqrt(4) * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(m^2 * r^2 + r^2 - b^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2
وهذا هو تقريبا بقدر ما سوف تبسيط. وأخيرا، فصل لمعادلات مع ±:
(-2mb + 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2 or
(-2mb - 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2
وثم ببساطة لسد نتيجة كل تلك المعادلات في x في mx + b. من أجل الوضوح، كتبت بعض شفرة جافا سكريبت لإظهار كيفية استخدام هذا:
function interceptOnCircle(p1,p2,c,r){
//p1 is the first line point
//p2 is the second line point
//c is the circle's center
//r is the circle's radius
var p3 = {x:p1.x - c.x, y:p1.y - c.y} //shifted line points
var p4 = {x:p2.x - c.x, y:p2.y - c.y}
var m = (p4.y - p3.y) / (p4.x - p3.x); //slope of the line
var b = p3.y - m * p3.x; //y-intercept of line
var underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2)); //the value under the square root sign
if (underRadical < 0){
//line completely missed
return false;
} else {
var t1 = (-2*m*b+2*Math.sqrt(underRadical))/(2 * Math.pow(m,2) + 2); //one of the intercept x's
var t2 = (-2*m*b-2*Math.sqrt(underRadical))/(2 * Math.pow(m,2) + 2); //other intercept's x
var i1 = {x:t1,y:m*t1+b} //intercept point 1
var i2 = {x:t2,y:m*t2+b} //intercept point 2
return [i1,i2];
}
}
وآمل أن يساعد هذا!
وP.S. إذا كان أي شخص يجد أي أخطاء أو لديه أي اقتراحات، يرجى التعليق. أنا جديدة جدا ونرحب بكل مساعدة / اقتراحات.
ويمكنك العثور على نقطة على خط لانهائي وهذا هو الأقرب إلى مركز الدائرة من خلال إبراز ناقلات AC على ناقلات AB. حساب المسافة بين تلك النقطة ومركز الدائرة. إذا كان هذا هو أكبر أن R، لا يوجد أي تقاطع. إذا كانت المسافة تساوي R، الخط المماس للدائرة ونقطة أقرب إلى مركز الدائرة هو في الواقع نقطة التقاطع. إذا مسافة أقل من R، ثم هناك 2 نقطة التقاطع. إنهم يكذبون على مسافة واحدة من نقطة أقرب إلى مركز الدائرة. يمكن بسهولة أن تحسب تلك المسافة باستخدام نظرية فيثاغورس. وهنا خوارزمية في شبة الكود:
{
dX = bX - aX;
dY = bY - aY;
if ((dX == 0) && (dY == 0))
{
// A and B are the same points, no way to calculate intersection
return;
}
dl = (dX * dX + dY * dY);
t = ((cX - aX) * dX + (cY - aY) * dY) / dl;
// point on a line nearest to circle center
nearestX = aX + t * dX;
nearestY = aY + t * dY;
dist = point_dist(nearestX, nearestY, cX, cY);
if (dist == R)
{
// line segment touches circle; one intersection point
iX = nearestX;
iY = nearestY;
if (t < 0 || t > 1)
{
// intersection point is not actually within line segment
}
}
else if (dist < R)
{
// two possible intersection points
dt = sqrt(R * R - dist * dist) / sqrt(dl);
// intersection point nearest to A
t1 = t - dt;
i1X = aX + t1 * dX;
i1Y = aY + t1 * dY;
if (t1 < 0 || t1 > 1)
{
// intersection point is not actually within line segment
}
// intersection point farthest from A
t2 = t + dt;
i2X = aX + t2 * dX;
i2Y = aY + t2 * dY;
if (t2 < 0 || t2 > 1)
{
// intersection point is not actually within line segment
}
}
else
{
// no intersection
}
}
وتحرير: وأضاف كود للتحقق ما إذا كانت نقطة تقاطع وجدت في الواقع ضمن القطعة المستقيمة
.وبغرابة أستطيع الإجابة ولكن لم يعلق ... أحببت نهج Multitaskpro للتحول كل شيء لجعل وسط سقوط دائرة على الأصل. للأسف هناك نوعان من المشاكل في التعليمات البرمجية له. لأول مرة في الجزء تحت رأس مربع الجذر تحتاج إلى إزالة قوة مزدوجة. حتى لا:
وvar underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2));
ولكن:
وvar underRadical = Math.pow(r,2)*(Math.pow(m,2)+1)) - Math.pow(b,2);
في المباراة النهائية تنسق نسي أن يتحول الحل إلى الوراء. حتى لا:
وvar i1 = {x:t1,y:m*t1+b}
ولكن:
وvar i1 = {x:t1+c.x, y:m*t1+b+c.y};
وظيفة كاملة ثم يصبح:
function interceptOnCircle(p1, p2, c, r) {
//p1 is the first line point
//p2 is the second line point
//c is the circle's center
//r is the circle's radius
var p3 = {x:p1.x - c.x, y:p1.y - c.y}; //shifted line points
var p4 = {x:p2.x - c.x, y:p2.y - c.y};
var m = (p4.y - p3.y) / (p4.x - p3.x); //slope of the line
var b = p3.y - m * p3.x; //y-intercept of line
var underRadical = Math.pow(r,2)*Math.pow(m,2) + Math.pow(r,2) - Math.pow(b,2); //the value under the square root sign
if (underRadical < 0) {
//line completely missed
return false;
} else {
var t1 = (-m*b + Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //one of the intercept x's
var t2 = (-m*b - Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //other intercept's x
var i1 = {x:t1+c.x, y:m*t1+b+c.y}; //intercept point 1
var i2 = {x:t2+c.x, y:m*t2+b+c.y}; //intercept point 2
return [i1, i2];
}
}
وستحتاج بعض الرياضيات هنا:
لنفترض A = (شى، يا)، B = (الخارجة، الإيتيربيوم) وC = (XC، البطاقة الصفراء). أي نقطة على السطر من A إلى B لها إحداثيات (ألفا * شى + (1-ألفا) <م> الخارجة، ألفا يا + (1-ألفا) * الإيتيربيوم) = P
وإذا كانت نقطة P ديها بعد R إلى C، يجب أن يكون على الدائرة. ما تريده هو أن حل
distance(P, C) = R
وهذا هو
(alpha*Xa + (1-alpha)*Xb)^2 + (alpha*Ya + (1-alpha)*Yb)^2 = R^2
alpha^2*Xa^2 + alpha^2*Xb^2 - 2*alpha*Xb^2 + Xb^2 + alpha^2*Ya^2 + alpha^2*Yb^2 - 2*alpha*Yb^2 + Yb^2=R^2
(Xa^2 + Xb^2 + Ya^2 + Yb^2)*alpha^2 - 2*(Xb^2 + Yb^2)*alpha + (Xb^2 + Yb^2 - R^2) = 0
وإذا قمت بتطبيق ABC-صيغة لهذه المعادلة لحلها ألفا، وحساب إحداثيات P باستخدام حل ل ألفا، وتحصل على نقاط التقاطع، إذا كان هناك أي.
وإذا وجدت المسافة بين مركز المجال (حيث أنها 3D أفترض أنك تعني المجال وليس دائرة) والخط، ثم معرفة ما اذا كان ذلك بعد أقل من نصف قطرها من شأنها أن تفعل خدعة.
والنقطة الاصطدام ومن الواضح أن أقرب نقطة بين الخط والمجال (والذي سيتم احتساب عندما كنت حساب المسافة بين المجال والخط)
والمسافة بين نقطة وسطر:
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html
وهنا التنفيذ في جافا سكريبت. توجهي هو تحويل أول شريحة خط إلى خط لانهائي ثم العثور على نقطة تقاطع (ق). من هناك ومعرفة ما اذا كان نقطة (ق) وجدت هي على القطعة المستقيمة. رمز موثق بشكل جيد، يجب أن تكون قادرة على متابعة طول.
ويمكنك تجربة الشفرة هنا على هذا يعيش تجريبي . واتخذ رمز من وجهة نظري خوارزميات الريبو .
// Small epsilon value
var EPS = 0.0000001;
// point (x, y)
function Point(x, y) {
this.x = x;
this.y = y;
}
// Circle with center at (x,y) and radius r
function Circle(x, y, r) {
this.x = x;
this.y = y;
this.r = r;
}
// A line segment (x1, y1), (x2, y2)
function LineSegment(x1, y1, x2, y2) {
var d = Math.sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
if (d < EPS) throw 'A point is not a line segment';
this.x1 = x1; this.y1 = y1;
this.x2 = x2; this.y2 = y2;
}
// An infinite line defined as: ax + by = c
function Line(a, b, c) {
this.a = a; this.b = b; this.c = c;
// Normalize line for good measure
if (Math.abs(b) < EPS) {
c /= a; a = 1; b = 0;
} else {
a = (Math.abs(a) < EPS) ? 0 : a / b;
c /= b; b = 1;
}
}
// Given a line in standard form: ax + by = c and a circle with
// a center at (x,y) with radius r this method finds the intersection
// of the line and the circle (if any).
function circleLineIntersection(circle, line) {
var a = line.a, b = line.b, c = line.c;
var x = circle.x, y = circle.y, r = circle.r;
// Solve for the variable x with the formulas: ax + by = c (equation of line)
// and (x-X)^2 + (y-Y)^2 = r^2 (equation of circle where X,Y are known) and expand to obtain quadratic:
// (a^2 + b^2)x^2 + (2abY - 2ac + - 2b^2X)x + (b^2X^2 + b^2Y^2 - 2bcY + c^2 - b^2r^2) = 0
// Then use quadratic formula X = (-b +- sqrt(a^2 - 4ac))/2a to find the
// roots of the equation (if they exist) and this will tell us the intersection points
// In general a quadratic is written as: Ax^2 + Bx + C = 0
// (a^2 + b^2)x^2 + (2abY - 2ac + - 2b^2X)x + (b^2X^2 + b^2Y^2 - 2bcY + c^2 - b^2r^2) = 0
var A = a*a + b*b;
var B = 2*a*b*y - 2*a*c - 2*b*b*x;
var C = b*b*x*x + b*b*y*y - 2*b*c*y + c*c - b*b*r*r;
// Use quadratic formula x = (-b +- sqrt(a^2 - 4ac))/2a to find the
// roots of the equation (if they exist).
var D = B*B - 4*A*C;
var x1,y1,x2,y2;
// Handle vertical line case with b = 0
if (Math.abs(b) < EPS) {
// Line equation is ax + by = c, but b = 0, so x = c/a
x1 = c/a;
// No intersection
if (Math.abs(x-x1) > r) return [];
// Vertical line is tangent to circle
if (Math.abs((x1-r)-x) < EPS || Math.abs((x1+r)-x) < EPS)
return [new Point(x1, y)];
var dx = Math.abs(x1 - x);
var dy = Math.sqrt(r*r-dx*dx);
// Vertical line cuts through circle
return [
new Point(x1,y+dy),
new Point(x1,y-dy)
];
// Line is tangent to circle
} else if (Math.abs(D) < EPS) {
x1 = -B/(2*A);
y1 = (c - a*x1)/b;
return [new Point(x1,y1)];
// No intersection
} else if (D < 0) {
return [];
} else {
D = Math.sqrt(D);
x1 = (-B+D)/(2*A);
y1 = (c - a*x1)/b;
x2 = (-B-D)/(2*A);
y2 = (c - a*x2)/b;
return [
new Point(x1, y1),
new Point(x2, y2)
];
}
}
// Converts a line segment to a line in general form
function segmentToGeneralForm(x1,y1,x2,y2) {
var a = y1 - y2;
var b = x2 - x1;
var c = x2*y1 - x1*y2;
return new Line(a,b,c);
}
// Checks if a point 'pt' is inside the rect defined by (x1,y1), (x2,y2)
function pointInRectangle(pt,x1,y1,x2,y2) {
var x = Math.min(x1,x2), X = Math.max(x1,x2);
var y = Math.min(y1,y2), Y = Math.max(y1,y2);
return x - EPS <= pt.x && pt.x <= X + EPS &&
y - EPS <= pt.y && pt.y <= Y + EPS;
}
// Finds the intersection(s) of a line segment and a circle
function lineSegmentCircleIntersection(segment, circle) {
var x1 = segment.x1, y1 = segment.y1, x2 = segment.x2, y2 = segment.y2;
var line = segmentToGeneralForm(x1,y1,x2,y2);
var pts = circleLineIntersection(circle, line);
// No intersection
if (pts.length === 0) return [];
var pt1 = pts[0];
var includePt1 = pointInRectangle(pt1,x1,y1,x2,y2);
// Check for unique intersection
if (pts.length === 1) {
if (includePt1) return [pt1];
return [];
}
var pt2 = pts[1];
var includePt2 = pointInRectangle(pt2,x1,y1,x2,y2);
// Check for remaining intersections
if (includePt1 && includePt2) return [pt1, pt2];
if (includePt1) return [pt1];
if (includePt2) return [pt2];
return [];
}
في هذا المنصب دائرة خط التصادم وسيتم فحص عن طريق فحص المسافة بين مركز الدائرة ونقطة على قطعة مستقيمة (Ipoint) التي تمثل نقطة تقاطع بين N العادي (صورة 2) من مركز الدائرة إلى خط القطاع.
و( https://i.stack.imgur.com/3o6do.png) 
في صورة 1 يتم عرض دائرة واحدة وسطر واحد، ناقلات نقطة على خط نقطة، ناقلات نقطة B البدء في خط نقطة النهاية، وأشر ناقلات C إلى مركز الدائرة. الآن يجب علينا أن نجد ناقلات E (من نقطة بداية الخط إلى مركز دائرة) وناقلات D (من نقطة بداية الخط إلى خط نقطة النهاية) يظهر هذا الحساب على الصورة 1.
و( https://i.stack.imgur.com/7098a.png) 
وفي صورة 2 يمكننا أن نرى من المتوقع أن ناقلات E على المتجهات D من قبل "المنتج دوت" ناقلات E وحدة مكافحة ناقلات D، نتيجة لمنتج دوت هي إكس بي العددية التي تمثل المسافة بين نقطة بداية الخط ونقطة تقاطع ( Ipoint) من ناقلات N وناقلات D. تم العثور على ناقلات المقبل X بضرب وحدة مكافحة ناقلات D وإكس بي القياسي.
والآن نحن بحاجة للعثور على ناقلات Z (ناقلات لIpoint)، من السهل لها بسيطة بالإضافة ناقلات ناقلات A (نقطة على خط البدء) وناقلات X. القادم ونحن بحاجة للتعامل مع حالات خاصة يجب علينا التحقق من Ipoint على خط الجزء، إذا كان لا يجب علينا أن نجد من هو تبقى منها أو حق، ونحن سوف تستخدم ناقلات الأقرب إلى تحديد أي نقطة هو الأقرب إلى دائرة.
و( https://i.stack.imgur.com/p9WIr.png) 
عند إسقاط إكس بي هو سلبي تركت Ipoint من القطعة المستقيمة، ناقلات أقرب يساوي متجه من نقطة بداية الخط، وعندما إسقاط إكس بي هو أكبر ثم حجم ناقلات D ثم Ipoint هو حق قطعة مستقيمة ثم الأقرب ناقلات يساوي متجه نقطة نهاية الخط في أي حالة أخرى أقرب ناقلات تساوي متجه Z.
والآن عندما يكون لدينا أقرب ناقلات، ونحن بحاجة للعثور على ناقلات من مركز الدائرة إلى Ipoint (ناقلات حي)، وبسيطة نحن بحاجة فقط لطرح أقرب ناقلات ناقلات من الوسط. التالي فقط معرفة ما اذا كان متجه حي حجم أقل ثم دائرة نصف قطرها إذا كان ثم أنها تصطدم، إذا ليست هناك أي تصادم.
و( https://i.stack.imgur.com/QJ63q.png) 
لنهاية، يمكننا إعادة بعض القيم لحل الاصطدام وأسهل طريقة هي العودة الى تداخل الاصطدام (طرح دائرة نصف قطرها من حجم ناقلات شعبة نظم) والعودة محور الاصطدام، ناقلات لها D. أيضا نقطة تقاطع هو متجه Z إذا لزم الأمر.
إذا إحداثيات خط هي A.x، A.y وB.x، B.y ودوائر المركز C.x، C.y ثم الصيغ خطوط هي:
س = A.x ر * + * B.x (1 - ر)
ص = A.y ر * + * B.y (1 - ر)
وحيث 0 <= ر <= 1
وودائرة هو
و(C.x - س) ^ 2 + (C.y - ص) ^ 2 = R ^ 2
وإذا كنت س بديلة وصيغ ذ الخط في صيغة الدوائر تحصل على معادلة من الدرجة الثانية من طن وحلولها هي نقطة تقاطع (إذا كان هناك أي). إذا كنت تحصل على طن والذي هو أصغر من 0 أو أكبر من 1 ثم ليس لها حل ولكن يظهر أن الخط "لافتا" إلى اتجاه الدائرة.
ومجرد إضافة لهذا الموضوع ... وفيما يلي نسخة من قانون المرسلة بواسطة بهلوان، ولكن لC # / XNA وتسويتها حتى قليلا:
/// <summary>
/// Intersects a line and a circle.
/// </summary>
/// <param name="location">the location of the circle</param>
/// <param name="radius">the radius of the circle</param>
/// <param name="lineFrom">the starting point of the line</param>
/// <param name="lineTo">the ending point of the line</param>
/// <returns>true if the line and circle intersect each other</returns>
public static bool IntersectLineCircle(Vector2 location, float radius, Vector2 lineFrom, Vector2 lineTo)
{
float ab2, acab, h2;
Vector2 ac = location - lineFrom;
Vector2 ab = lineTo - lineFrom;
Vector2.Dot(ref ab, ref ab, out ab2);
Vector2.Dot(ref ac, ref ab, out acab);
float t = acab / ab2;
if (t < 0)
t = 0;
else if (t > 1)
t = 1;
Vector2 h = ((ab * t) + lineFrom) - location;
Vector2.Dot(ref h, ref h, out h2);
return (h2 <= (radius * radius));
}
' VB.NET - Code
Function CheckLineSegmentCircleIntersection(x1 As Double, y1 As Double, x2 As Double, y2 As Double, xc As Double, yc As Double, r As Double) As Boolean
Static xd As Double = 0.0F
Static yd As Double = 0.0F
Static t As Double = 0.0F
Static d As Double = 0.0F
Static dx_2_1 As Double = 0.0F
Static dy_2_1 As Double = 0.0F
dx_2_1 = x2 - x1
dy_2_1 = y2 - y1
t = ((yc - y1) * dy_2_1 + (xc - x1) * dx_2_1) / (dy_2_1 * dy_2_1 + dx_2_1 * dx_2_1)
If 0 <= t And t <= 1 Then
xd = x1 + t * dx_2_1
yd = y1 + t * dy_2_1
d = Math.Sqrt((xd - xc) * (xd - xc) + (yd - yc) * (yd - yc))
Return d <= r
Else
d = Math.Sqrt((xc - x1) * (xc - x1) + (yc - y1) * (yc - y1))
If d <= r Then
Return True
Else
d = Math.Sqrt((xc - x2) * (xc - x2) + (yc - y2) * (yc - y2))
If d <= r Then
Return True
Else
Return False
End If
End If
End If
End Function
ولقد خلقت هذه الوظيفة لدائرة الرقابة الداخلية بعد الإجابة التي قدمها chmike
+ (NSArray *)intersectionPointsOfCircleWithCenter:(CGPoint)center withRadius:(float)radius toLinePoint1:(CGPoint)p1 andLinePoint2:(CGPoint)p2
{
NSMutableArray *intersectionPoints = [NSMutableArray array];
float Ax = p1.x;
float Ay = p1.y;
float Bx = p2.x;
float By = p2.y;
float Cx = center.x;
float Cy = center.y;
float R = radius;
// compute the euclidean distance between A and B
float LAB = sqrt( pow(Bx-Ax, 2)+pow(By-Ay, 2) );
// compute the direction vector D from A to B
float Dx = (Bx-Ax)/LAB;
float Dy = (By-Ay)/LAB;
// Now the line equation is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= 1.
// compute the value t of the closest point to the circle center (Cx, Cy)
float t = Dx*(Cx-Ax) + Dy*(Cy-Ay);
// This is the projection of C on the line from A to B.
// compute the coordinates of the point E on line and closest to C
float Ex = t*Dx+Ax;
float Ey = t*Dy+Ay;
// compute the euclidean distance from E to C
float LEC = sqrt( pow(Ex-Cx, 2)+ pow(Ey-Cy, 2) );
// test if the line intersects the circle
if( LEC < R )
{
// compute distance from t to circle intersection point
float dt = sqrt( pow(R, 2) - pow(LEC,2) );
// compute first intersection point
float Fx = (t-dt)*Dx + Ax;
float Fy = (t-dt)*Dy + Ay;
// compute second intersection point
float Gx = (t+dt)*Dx + Ax;
float Gy = (t+dt)*Dy + Ay;
[intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Fx, Fy)]];
[intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Gx, Gy)]];
}
// else test if the line is tangent to circle
else if( LEC == R ) {
// tangent point to circle is E
[intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Ex, Ey)]];
}
else {
// line doesn't touch circle
}
return intersectionPoints;
}
وهذه وظيفة جافا بإرجاع كائن DVec2. فإنه يأخذ DVec2 عن مركز الدائرة، و نصف قطر الدائرة، والخط.
public static DVec2 CircLine(DVec2 C, double r, Line line)
{
DVec2 A = line.p1;
DVec2 B = line.p2;
DVec2 P;
DVec2 AC = new DVec2( C );
AC.sub(A);
DVec2 AB = new DVec2( B );
AB.sub(A);
double ab2 = AB.dot(AB);
double acab = AC.dot(AB);
double t = acab / ab2;
if (t < 0.0)
t = 0.0;
else if (t > 1.0)
t = 1.0;
//P = A + t * AB;
P = new DVec2( AB );
P.mul( t );
P.add( A );
DVec2 H = new DVec2( P );
H.sub( C );
double h2 = H.dot(H);
double r2 = r * r;
if(h2 > r2)
return null;
else
return P;
}
واحد آخر في ج # (جزئي الطبقة الدائرة). اختبارها وتعمل مثل السحر.
public class Circle : IEquatable<Circle>
{
// ******************************************************************
// The center of a circle
private Point _center;
// The radius of a circle
private double _radius;
// ******************************************************************
/// <summary>
/// Find all intersections (0, 1, 2) of the circle with a line defined by its 2 points.
/// Using: http://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle
/// Note: p is the Center.X and q is Center.Y
/// </summary>
/// <param name="linePoint1"></param>
/// <param name="linePoint2"></param>
/// <returns></returns>
public List<Point> GetIntersections(Point linePoint1, Point linePoint2)
{
List<Point> intersections = new List<Point>();
double dx = linePoint2.X - linePoint1.X;
if (dx.AboutEquals(0)) // Straight vertical line
{
if (linePoint1.X.AboutEquals(Center.X - Radius) || linePoint1.X.AboutEquals(Center.X + Radius))
{
Point pt = new Point(linePoint1.X, Center.Y);
intersections.Add(pt);
}
else if (linePoint1.X > Center.X - Radius && linePoint1.X < Center.X + Radius)
{
double x = linePoint1.X - Center.X;
Point pt = new Point(linePoint1.X, Center.Y + Math.Sqrt(Radius * Radius - (x * x)));
intersections.Add(pt);
pt = new Point(linePoint1.X, Center.Y - Math.Sqrt(Radius * Radius - (x * x)));
intersections.Add(pt);
}
return intersections;
}
// Line function (y = mx + b)
double dy = linePoint2.Y - linePoint1.Y;
double m = dy / dx;
double b = linePoint1.Y - m * linePoint1.X;
double A = m * m + 1;
double B = 2 * (m * b - m * _center.Y - Center.X);
double C = Center.X * Center.X + Center.Y * Center.Y - Radius * Radius - 2 * b * Center.Y + b * b;
double discriminant = B * B - 4 * A * C;
if (discriminant < 0)
{
return intersections; // there is no intersections
}
if (discriminant.AboutEquals(0)) // Tangeante (touch on 1 point only)
{
double x = -B / (2 * A);
double y = m * x + b;
intersections.Add(new Point(x, y));
}
else // Secant (touch on 2 points)
{
double x = (-B + Math.Sqrt(discriminant)) / (2 * A);
double y = m * x + b;
intersections.Add(new Point(x, y));
x = (-B - Math.Sqrt(discriminant)) / (2 * A);
y = m * x + b;
intersections.Add(new Point(x, y));
}
return intersections;
}
// ******************************************************************
// Get the center
[XmlElement("Center")]
public Point Center
{
get { return _center; }
set
{
_center = value;
}
}
// ******************************************************************
// Get the radius
[XmlElement]
public double Radius
{
get { return _radius; }
set { _radius = value; }
}
//// ******************************************************************
//[XmlArrayItemAttribute("DoublePoint")]
//public List<Point> Coordinates
//{
// get { return _coordinates; }
//}
// ******************************************************************
// Construct a circle without any specification
public Circle()
{
_center.X = 0;
_center.Y = 0;
_radius = 0;
}
// ******************************************************************
// Construct a circle without any specification
public Circle(double radius)
{
_center.X = 0;
_center.Y = 0;
_radius = radius;
}
// ******************************************************************
// Construct a circle with the specified circle
public Circle(Circle circle)
{
_center = circle._center;
_radius = circle._radius;
}
// ******************************************************************
// Construct a circle with the specified center and radius
public Circle(Point center, double radius)
{
_center = center;
_radius = radius;
}
// ******************************************************************
// Construct a circle based on one point
public Circle(Point center)
{
_center = center;
_radius = 0;
}
// ******************************************************************
// Construct a circle based on two points
public Circle(Point p1, Point p2)
{
Circle2Points(p1, p2);
}
والمطلوبة:
using System;
namespace Mathematic
{
public static class DoubleExtension
{
// ******************************************************************
// Base on Hans Passant Answer on:
// http://stackoverflow.com/questions/2411392/double-epsilon-for-equality-greater-than-less-than-less-than-or-equal-to-gre
/// <summary>
/// Compare two double taking in account the double precision potential error.
/// Take care: truncation errors accumulate on calculation. More you do, more you should increase the epsilon.
public static bool AboutEquals(this double value1, double value2)
{
if (double.IsPositiveInfinity(value1))
return double.IsPositiveInfinity(value2);
if (double.IsNegativeInfinity(value1))
return double.IsNegativeInfinity(value2);
if (double.IsNaN(value1))
return double.IsNaN(value2);
double epsilon = Math.Max(Math.Abs(value1), Math.Abs(value2)) * 1E-15;
return Math.Abs(value1 - value2) <= epsilon;
}
// ******************************************************************
// Base on Hans Passant Answer on:
// http://stackoverflow.com/questions/2411392/double-epsilon-for-equality-greater-than-less-than-less-than-or-equal-to-gre
/// <summary>
/// Compare two double taking in account the double precision potential error.
/// Take care: truncation errors accumulate on calculation. More you do, more you should increase the epsilon.
/// You get really better performance when you can determine the contextual epsilon first.
/// </summary>
/// <param name="value1"></param>
/// <param name="value2"></param>
/// <param name="precalculatedContextualEpsilon"></param>
/// <returns></returns>
public static bool AboutEquals(this double value1, double value2, double precalculatedContextualEpsilon)
{
if (double.IsPositiveInfinity(value1))
return double.IsPositiveInfinity(value2);
if (double.IsNegativeInfinity(value1))
return double.IsNegativeInfinity(value2);
if (double.IsNaN(value1))
return double.IsNaN(value2);
return Math.Abs(value1 - value2) <= precalculatedContextualEpsilon;
}
// ******************************************************************
public static double GetContextualEpsilon(this double biggestPossibleContextualValue)
{
return biggestPossibleContextualValue * 1E-15;
}
// ******************************************************************
/// <summary>
/// Mathlab equivalent
/// </summary>
/// <param name="dividend"></param>
/// <param name="divisor"></param>
/// <returns></returns>
public static double Mod(this double dividend, double divisor)
{
return dividend - System.Math.Floor(dividend / divisor) * divisor;
}
// ******************************************************************
}
}
وهنا هو حل جيد في جافا سكريبت (مع كل الرياضيات المطلوبة والتوضيح الحية) https://bl.ocks.org/milkbread/11000965
وعلى الرغم من وظيفة is_on في هذا الحل يحتاج التعديلات:
function is_on(a, b, c) {
return Math.abs(distance(a,c) + distance(c,b) - distance(a,b))<0.000001;
}
الدائرة هي حقًا رجل سيء :) لذا فإن الطريقة الجيدة هي تجنب الدائرة الحقيقية، إذا استطعت.إذا كنت تقوم بالتحقق من التصادم للألعاب، فيمكنك اتباع بعض التبسيطات والحصول على 3 منتجات نقطية فقط وبعض المقارنات.
أسمي هذه "النقطة السمينة" أو "الدائرة الرفيعة".إنه نوع من القطع الناقص نصف قطره صفر في اتجاه موازٍ للقطعة.ولكن نصف قطرها الكامل في اتجاه عمودي على قطعة
أولاً، سأفكر في إعادة تسمية نظام الإحداثيات وتبديله لتجنب البيانات الزائدة:
s0s1 = B-A;
s0qp = C-A;
rSqr = r*r;
ثانيًا، يعني الفهرس h في hvec2f أن المتجه يجب أن يفضل العمليات الأفقية، مثل dot()/det().مما يعني أن مكوناته يجب وضعها في سجلات xmm منفصلة، لتجنب الخلط/الحد/الضرب.وها نحن ذا، مع الإصدار الأكثر أداءً من أبسط اكتشاف للاصطدام للعبة ثنائية الأبعاد:
bool fat_point_collides_segment(const hvec2f& s0qp, const hvec2f& s0s1, const float& rSqr) {
auto a = dot(s0s1, s0s1);
//if( a != 0 ) // if you haven't zero-length segments omit this, as it would save you 1 _mm_comineq_ss() instruction and 1 memory fetch
{
auto b = dot(s0s1, s0qp);
auto t = b / a; // length of projection of s0qp onto s0s1
//std::cout << "t = " << t << "\n";
if ((t >= 0) && (t <= 1)) //
{
auto c = dot(s0qp, s0qp);
auto r2 = c - a * t * t;
return (r2 <= rSqr); // true if collides
}
}
return false;
}
أشك في أنه يمكنك تحسينه بشكل أكبر.أنا أستخدمه للكشف عن تصادمات سباقات السيارات التي تعتمد على الشبكة العصبية، لمعالجة ملايين الملايين من خطوات التكرار.
وهنا هو الحل بلدي في نسخة مطبوعة على الآلة الكاتبة، وبعد فكرة أنMizipzor اقترح (باستخدام الإسقاط):
/**
* Determines whether a line segment defined by a start and end point intersects with a sphere defined by a center point and a radius
* @param a the start point of the line segment
* @param b the end point of the line segment
* @param c the center point of the sphere
* @param r the radius of the sphere
*/
export function lineSphereIntersects(
a: IPoint,
b: IPoint,
c: IPoint,
r: number
): boolean {
// find the three sides of the triangle formed by the three points
const ab: number = distance(a, b);
const ac: number = distance(a, c);
const bc: number = distance(b, c);
// check to see if either ends of the line segment are inside of the sphere
if (ac < r || bc < r) {
return true;
}
// find the angle between the line segment and the center of the sphere
const numerator: number = Math.pow(ac, 2) + Math.pow(ab, 2) - Math.pow(bc, 2);
const denominator: number = 2 * ac * ab;
const cab: number = Math.acos(numerator / denominator);
// find the distance from the center of the sphere and the line segment
const cd: number = Math.sin(cab) * ac;
// if the radius is at least as long as the distance between the center and the line
if (r >= cd) {
// find the distance between the line start and the point on the line closest to
// the center of the sphere
const ad: number = Math.cos(cab) * ac;
// intersection occurs when the point on the line closest to the sphere center is
// no further away than the end of the line
return ad <= ab;
}
return false;
}
export function distance(a: IPoint, b: IPoint): number {
return Math.sqrt(
Math.pow(b.z - a.z, 2) + Math.pow(b.y - a.y, 2) + Math.pow(b.x - a.x, 2)
);
}
export interface IPoint {
x: number;
y: number;
z: number;
}
وهنا الحل مكتوب في جولانج.الطريقة مشابهة لبعض الإجابات الأخرى المنشورة هنا، ولكنها ليست متماثلة تمامًا.إنه سهل التنفيذ، وقد تم اختباره.فيما يلي الخطوات:
- ترجمة الإحداثيات بحيث تكون الدائرة في الأصل.
- قم بالتعبير عن مقطع الخط كوظائف ذات معلمات لـ t لكل من إحداثيات x وy.إذا كانت t تساوي 0، فإن قيم الدالة هي نقطة نهاية واحدة للمقطع، وإذا كانت t تساوي 1، فإن قيم الدالة هي نقطة النهاية الأخرى.
- حل، إن أمكن، المعادلة التربيعية الناتجة عن تقييد قيم t التي تنتج إحداثيات x وy بمسافات من الأصل تساوي نصف قطر الدائرة.
- اطرح الحلول التي يكون فيها t <0 أو > 1 ( <= 0 أو >= 1 للقطعة المفتوحة).هذه النقاط غير واردة في هذا الجزء.
- ترجمة مرة أخرى إلى الإحداثيات الأصلية.
يتم هنا اشتقاق قيم A وB وC للمعادلة التربيعية، حيث (n-et) و(m-dt) هي معادلات إحداثيات الخط x وy على التوالي.r هو نصف قطر الدائرة
(n-et)(n-et) + (m-dt)(m-dt) = rr
nn - 2etn + etet + mm - 2mdt + dtdt = rr
(ee+dd)tt - 2(en + dm)t + nn + mm - rr = 0
لذلك A = ee+dd، B = - 2(en + dm)، وC = nn + mm - rr.
إليك رمز جولانج للوظيفة:
package geom
import (
"math"
)
// SegmentCircleIntersection return points of intersection between a circle and
// a line segment. The Boolean intersects returns true if one or
// more solutions exist. If only one solution exists,
// x1 == x2 and y1 == y2.
// s1x and s1y are coordinates for one end point of the segment, and
// s2x and s2y are coordinates for the other end of the segment.
// cx and cy are the coordinates of the center of the circle and
// r is the radius of the circle.
func SegmentCircleIntersection(s1x, s1y, s2x, s2y, cx, cy, r float64) (x1, y1, x2, y2 float64, intersects bool) {
// (n-et) and (m-dt) are expressions for the x and y coordinates
// of a parameterized line in coordinates whose origin is the
// center of the circle.
// When t = 0, (n-et) == s1x - cx and (m-dt) == s1y - cy
// When t = 1, (n-et) == s2x - cx and (m-dt) == s2y - cy.
n := s2x - cx
m := s2y - cy
e := s2x - s1x
d := s2y - s1y
// lineFunc checks if the t parameter is in the segment and if so
// calculates the line point in the unshifted coordinates (adds back
// cx and cy.
lineFunc := func(t float64) (x, y float64, inBounds bool) {
inBounds = t >= 0 && t <= 1 // Check bounds on closed segment
// To check bounds for an open segment use t > 0 && t < 1
if inBounds { // Calc coords for point in segment
x = n - e*t + cx
y = m - d*t + cy
}
return
}
// Since we want the points on the line distance r from the origin,
// (n-et)(n-et) + (m-dt)(m-dt) = rr.
// Expanding and collecting terms yeilds the following quadratic equation:
A, B, C := e*e+d*d, -2*(e*n+m*d), n*n+m*m-r*r
D := B*B - 4*A*C // discriminant of quadratic
if D < 0 {
return // No solution
}
D = math.Sqrt(D)
var p1In, p2In bool
x1, y1, p1In = lineFunc((-B + D) / (2 * A)) // First root
if D == 0.0 {
intersects = p1In
x2, y2 = x1, y1
return // Only possible solution, quadratic has one root.
}
x2, y2, p2In = lineFunc((-B - D) / (2 * A)) // Second root
intersects = p1In || p2In
if p1In == false { // Only x2, y2 may be valid solutions
x1, y1 = x2, y2
} else if p2In == false { // Only x1, y1 are valid solutions
x2, y2 = x1, y1
}
return
}
لقد قمت باختبارها بهذه الدالة التي تؤكد أن نقاط الحل موجودة داخل قطعة الخط وعلى الدائرة.يقوم بإنشاء مقطع اختبار ويمسحه حول الدائرة المحددة:
package geom_test
import (
"testing"
. "**put your package path here**"
)
func CheckEpsilon(t *testing.T, v, epsilon float64, message string) {
if v > epsilon || v < -epsilon {
t.Error(message, v, epsilon)
t.FailNow()
}
}
func TestSegmentCircleIntersection(t *testing.T) {
epsilon := 1e-10 // Something smallish
x1, y1 := 5.0, 2.0 // segment end point 1
x2, y2 := 50.0, 30.0 // segment end point 2
cx, cy := 100.0, 90.0 // center of circle
r := 80.0
segx, segy := x2-x1, y2-y1
testCntr, solutionCntr := 0, 0
for i := -100; i < 100; i++ {
for j := -100; j < 100; j++ {
testCntr++
s1x, s2x := x1+float64(i), x2+float64(i)
s1y, s2y := y1+float64(j), y2+float64(j)
sc1x, sc1y := s1x-cx, s1y-cy
seg1Inside := sc1x*sc1x+sc1y*sc1y < r*r
sc2x, sc2y := s2x-cx, s2y-cy
seg2Inside := sc2x*sc2x+sc2y*sc2y < r*r
p1x, p1y, p2x, p2y, intersects := SegmentCircleIntersection(s1x, s1y, s2x, s2y, cx, cy, r)
if intersects {
solutionCntr++
//Check if points are on circle
c1x, c1y := p1x-cx, p1y-cy
deltaLen1 := (c1x*c1x + c1y*c1y) - r*r
CheckEpsilon(t, deltaLen1, epsilon, "p1 not on circle")
c2x, c2y := p2x-cx, p2y-cy
deltaLen2 := (c2x*c2x + c2y*c2y) - r*r
CheckEpsilon(t, deltaLen2, epsilon, "p2 not on circle")
// Check if points are on the line through the line segment
// "cross product" of vector from a segment point to the point
// and the vector for the segment should be near zero
vp1x, vp1y := p1x-s1x, p1y-s1y
crossProd1 := vp1x*segy - vp1y*segx
CheckEpsilon(t, crossProd1, epsilon, "p1 not on line ")
vp2x, vp2y := p2x-s1x, p2y-s1y
crossProd2 := vp2x*segy - vp2y*segx
CheckEpsilon(t, crossProd2, epsilon, "p2 not on line ")
// Check if point is between points s1 and s2 on line
// This means the sign of the dot prod of the segment vector
// and point to segment end point vectors are opposite for
// either end.
wp1x, wp1y := p1x-s2x, p1y-s2y
dp1v := vp1x*segx + vp1y*segy
dp1w := wp1x*segx + wp1y*segy
if (dp1v < 0 && dp1w < 0) || (dp1v > 0 && dp1w > 0) {
t.Error("point not contained in segment ", dp1v, dp1w)
t.FailNow()
}
wp2x, wp2y := p2x-s2x, p2y-s2y
dp2v := vp2x*segx + vp2y*segy
dp2w := wp2x*segx + wp2y*segy
if (dp2v < 0 && dp2w < 0) || (dp2v > 0 && dp2w > 0) {
t.Error("point not contained in segment ", dp2v, dp2w)
t.FailNow()
}
if s1x == s2x && s2y == s1y { //Only one solution
// Test that one end of the segment is withing the radius of the circle
// and one is not
if seg1Inside && seg2Inside {
t.Error("Only one solution but both line segment ends inside")
t.FailNow()
}
if !seg1Inside && !seg2Inside {
t.Error("Only one solution but both line segment ends outside")
t.FailNow()
}
}
} else { // No intersection, check if both points outside or inside
if (seg1Inside && !seg2Inside) || (!seg1Inside && seg2Inside) {
t.Error("No solution but only one point in radius of circle")
t.FailNow()
}
}
}
}
t.Log("Tested ", testCntr, " examples and found ", solutionCntr, " solutions.")
}
هنا هو إخراج الاختبار:
=== RUN TestSegmentCircleIntersection
--- PASS: TestSegmentCircleIntersection (0.00s)
geom_test.go:105: Tested 40000 examples and found 7343 solutions.
أخيرًا، يمكن توسيع الطريقة بسهولة لتشمل حالة الشعاع الذي يبدأ من نقطة واحدة، ويمر عبر النقطة الأخرى ويمتد إلى ما لا نهاية، وذلك عن طريق اختبار فقط ما إذا كان t > 0 أو t < 1 ولكن ليس كليهما.
وأنا في حاجة فقط، حتى خطرت لي هذا الحل. اللغة هي maxscript، ولكن يجب ان تترجم بسهولة إلى أي لغة أخرى. sideA، sideB وCircleRadius هي سكالارس، والباقي من المتغيرات هي نقطة ل[س، ص، ض]. أفترض ض = 0 إلى حل على متن الطائرة XY
fn projectPoint p1 p2 p3 = --project p1 perpendicular to the line p2-p3
(
local v= normalize (p3-p2)
local p= (p1-p2)
p2+((dot v p)*v)
)
fn findIntersectionLineCircle CircleCenter CircleRadius LineP1 LineP2=
(
pp=projectPoint CircleCenter LineP1 LineP2
sideA=distance pp CircleCenter
--use pythagoras to solve the third side
sideB=sqrt(CircleRadius^2-sideA^2) -- this will return NaN if they don't intersect
IntersectV=normalize (pp-CircleCenter)
perpV=[IntersectV.y,-IntersectV.x,IntersectV.z]
--project the point to both sides to find the solutions
solution1=pp+(sideB*perpV)
solution2=pp-(sideB*perpV)
return #(solution1,solution2)
)
