Algoritma pendeteksian tabrakan segmen garis garis?

Saya memiliki garis dari A ke B dan lingkaran diposisikan di C dengan jari-jari R.

Apa algoritma yang baik untuk digunakan untuk memeriksa apakah garis memotong lingkaran? Dan pada koordinat apa di sepanjang tepi lingkaran itu terjadi?

Pengambilan

1. E adalah titik awal dari sinar,
2. L adalah titik akhir dari sinar,
3. C adalah pusat lingkup yang Anda uji menentang
4. r adalah jari-jari bola itu

Hitung:
d = L - E (Vektor arah sinar, dari awal hingga akhir)
f = E - C (Vektor dari pusat bola ke mulai sinar)

Kemudian persimpangan ditemukan oleh ..
Memasukkan:
P = E + t * d
Ini adalah persamaan parametrik:
P _x = E _x + td _x
P _y = E _y + td _y
ke dalam
(x - h) ² + (y - k) ² = r ²
(h, k) = pusat lingkaran.

Catatan: Kami telah menyederhanakan masalah menjadi 2D di sini, solusi yang kami dapatkan juga berlaku dalam 3D

mendapatkan:

1. Rentangkan
   x ² - 2xh + h ² + y ² - 2yk + k ² - r ² = 0
2. Pasang
   x = e _x + td _x
   y = e _y + td _y
   (e _x + td _x ) ² - 2 (e _x + td _x ) h + h ² + (e _y + td _y ) ² - 2 (e _y + td _y ) k + k ² - r ² = 0
3. Meledak
   e _x ² + 2e _x td _x + t ² d _x ² - 2e _x h - 2td _x h + h ² + e _y ² + ² _y td _y + t ² d _y ² - 2e _y k - 2td _y k + k ² - r ² = 0
4. Grup
   t ² (d _x ² + d _y ² ) + 2t (e _x d _x + e _y d _y - d _x h - d _y k) + e _x ² + e _y ² - 2e _x h - 2e _y k + h ² + k ² - r ² = 0
5. Akhirnya,
   t ² (_d * _d) + 2t (_e * _d - _d * _c) + _e * _e - 2 (_e * _c) + _c * _c - r ² = 0
   * Di mana _d adalah vektor d dan * adalah produk titik. *
6. Dan kemudian,
   t ² (_d * _d) + 2t (_d * (_e - _c)) + (_e - _c) * (_e - _c) - r ² = 0
7. Membiarkan _f = _e - _c
   t ² (_d * _d) + 2t (_d * _f) + _f * _f - r ² = 0

Jadi kita mendapatkan:
t ² * (d DOT d) + 2t * (f DOT d) + (f DOT f - r ² ) = 0
Jadi memecahkan persamaan kuadratik:

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 ;
}

Sepertinya tidak ada yang mempertimbangkan proyeksi, apakah saya benar-benar keluar jalur di sini?

Proyeksikan vektor ACke AB. Vektor yang diproyeksikan,, ADmemberikan titik baru D.
Jika jarak antara Ddan Clebih kecil dari (atau sama dengan), Rkami memiliki persimpangan.

Seperti ini:

Saya akan menggunakan algoritma untuk menghitung jarak antara titik (pusat lingkaran) dan garis (garis AB). Ini kemudian dapat digunakan untuk menentukan titik persimpangan garis dengan lingkaran.

Katakanlah kita memiliki titik A, B, C. Axe dan Ay adalah komponen x dan y dari titik A. Sama untuk B dan C. Skalar R adalah jari-jari lingkaran.

Algoritma ini mensyaratkan bahwa A, B dan C adalah titik yang berbeda dan R bukan 0.

Di sini adalah algoritma

// 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

Oke, saya tidak akan memberi Anda kode, tetapi karena Anda telah menandai ini algoritma, Saya tidak berpikir itu penting bagi Anda. Pertama, Anda harus mendapatkan vektor tegak lurus terhadap garis.

Anda akan memiliki variabel yang tidak dikenal di y = ax + c ( c tidak akan diketahui )
Untuk menyelesaikannya, Hitung nilainya ketika garis melewati pusat lingkaran.

Yaitu,
Pasang di lokasi pusat lingkaran ke persamaan garis dan pecahkan untuk c.
Kemudian hitung titik persimpangan dari garis asli dan normalnya.

Ini akan memberi Anda titik terdekat pada garis ke lingkaran.
Hitung jarak antara titik ini dan pusat lingkaran (menggunakan besarnya vektor).
Jika ini kurang dari jari-jari lingkaran - voila, kita memiliki persimpangan!

Metode lain menggunakan rumus luas segitiga ABC. Tes persimpangan lebih sederhana dan lebih efisien daripada metode proyeksi, tetapi menemukan koordinat titik persimpangan membutuhkan lebih banyak pekerjaan. Setidaknya itu akan ditunda ke titik yang diperlukan.

Rumus untuk menghitung luas segitiga adalah: area = bh / 2

di mana b adalah panjang dasar dan h adalah tinggi. Kami memilih segmen AB untuk menjadi basis sehingga h adalah jarak terpendek dari C, pusat lingkaran, ke garis.

Karena area segitiga juga dapat dihitung dengan produk titik vektor kita dapat menentukan 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 )
{
    ...
}        

PEMBARUAN 1:

Anda bisa mengoptimalkan kode dengan menggunakan perhitungan root kuadrat terbalik cepat yang dijelaskan di sini untuk mendapatkan perkiraan 1 / LAB yang bagus.

Menghitung titik persimpangan tidak terlalu sulit. Ini dia

// 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

Jika h = R maka garis AB bersinggungan dengan lingkaran dan nilai dt = 0 dan E = F. Koordinat titik adalah dari E dan F.

Anda harus memeriksa bahwa A berbeda dari B dan panjang segmen tidak nol jika ini dapat terjadi dalam aplikasi Anda.

Saya menulis skrip kecil untuk menguji persimpangan dengan memproyeksikan titik pusat lingkaran ke garis.

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/

Jika Anda perlu memeriksa tabrakan dengan segmen, Anda juga perlu mempertimbangkan jarak pusat lingkaran untuk memulai dan mengakhiri poin.

vector distVector = centerPoint - startPoint;
if(distVector.length() < circle.radius)
{
    double distance = circle.radius - distVector.length();
    vector moveVector = distVector.normalize() * distance;
    circle.move(moveVector);
}

https://jsfiddle.net/ercang/menp0991/

Solusi yang saya temukan ini tampak sedikit lebih mudah untuk diikuti daripada beberapa yang lain.

Pengambilan:

p1 and p2 as the points for the line, and
c as the center point for the circle and r for the radius

Saya akan memecahkan persamaan garis dalam bentuk slope-intercept. Namun, saya tidak ingin harus berurusan dengan persamaan sulit csebagai titik, jadi saya hanya menggeser sistem koordinat sehingga lingkaran berada pada0,0

p3 = p1 - c
p4 = p2 - c

Ngomong-ngomong, setiap kali saya mengurangi poin dari satu sama lain, saya mengurangi poin xdan kemudian mengurangi poin y, dan menempatkannya ke poin baru, kalau-kalau ada yang tidak tahu.

Bagaimanapun, saya sekarang memecahkan persamaan garis dengan p3dan 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)

Baik. Sekarang saya perlu mengatur persamaan ini sama. Pertama, saya perlu memecahkan persamaan lingkaran untukx

x^2 + y^2 = r^2
y^2 = r^2 - x^2
y = sqrt(r^2 - x^2)

Lalu saya mengatur mereka sama:

mx + b = sqrt(r^2 - x^2)

Dan memecahkan persamaan kuadrat ( 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

Sekarang aku punya saya a, bdan c.

a = m^2 + 1
b = 2mb
c = b^2 - r^2

Jadi saya memasukkan ini ke dalam rumus kuadratik:

(-b ± sqrt(b^2 - 4ac)) / 2a

Dan gantikan dengan nilai-nilai kemudian sederhanakan sebanyak mungkin:

(-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

Ini hampir sejauh yang disederhanakan. Akhirnya, pisahkan persamaan dengan ±:

(-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 

Kemudian cukup tancapkan hasil dari kedua persamaan tersebut ke xdalam mx + b. Untuk lebih jelasnya, saya menulis beberapa kode JavaScript untuk menunjukkan cara menggunakan ini:

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];
    }
}

Saya harap ini membantu!

PS Jika ada yang menemukan kesalahan atau punya saran, silakan komentar. Saya sangat baru dan menyambut semua bantuan / saran.

Anda dapat menemukan titik pada garis tak terbatas yang terdekat dengan pusat lingkaran dengan memproyeksikan vektor AC ke vektor AB. Hitung jarak antara titik dan pusat lingkaran itu. Jika lebih besar dari R, tidak ada persimpangan. Jika jaraknya sama dengan R, garis adalah garis singgung lingkaran dan titik terdekat dengan pusat lingkaran sebenarnya adalah titik persimpangan. Jika jarak kurang dari R, maka ada 2 titik persimpangan. Mereka berbaring pada jarak yang sama dari titik terdekat ke pusat lingkaran. Jarak itu dapat dengan mudah dihitung menggunakan teorema Pythagoras. Berikut algoritma dalam pseudocode:

{
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
  }
}

EDIT: kode yang ditambahkan untuk memeriksa apakah titik persimpangan yang ditemukan sebenarnya berada dalam segmen garis.

Anehnya saya bisa menjawab tetapi tidak berkomentar ... Saya menyukai pendekatan Multitaskpro dalam mengubah segalanya untuk membuat pusat lingkaran jatuh pada asalnya. Sayangnya ada dua masalah dalam kodenya. Pertama di bagian root di bawah Anda perlu menghapus kekuatan ganda. Jadi tidak:

var underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2));

tapi:

var underRadical = Math.pow(r,2)*(Math.pow(m,2)+1)) - Math.pow(b,2);

Dalam koordinat terakhir dia lupa untuk menggeser solusi kembali. Jadi tidak:

var i1 = {x:t1,y:m*t1+b}

tapi:

var i1 = {x:t1+c.x, y:m*t1+b+c.y};

Seluruh fungsi kemudian menjadi:

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];
    }
}

Anda perlu matematika di sini:

Misalkan A = (Xa, Ya), B = (Xb, Yb) dan C = (Xc, Yc). Setiap titik pada garis dari A ke B memiliki koordinat (alpha * Xa + (1-alpha) Xb, alpha Ya + (1-alpha) * Yb) = P

Jika titik P memiliki jarak R ke C, itu harus di lingkaran. Yang Anda inginkan adalah menyelesaikannya

distance(P, C) = R

itu adalah

(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

jika Anda menerapkan rumus-ABC untuk persamaan ini untuk menyelesaikannya untuk alpha, dan menghitung koordinat P menggunakan solusi (s) untuk alpha, Anda mendapatkan titik persimpangan, jika ada.

Jika Anda menemukan jarak antara pusat bola (karena itu 3D saya anggap Anda maksud bola dan bukan lingkaran) dan garis, lalu periksa apakah jarak itu kurang dari jari-jari yang akan melakukan trik.

Titik tumbukan jelas merupakan titik terdekat antara garis dan bola (yang akan dihitung saat Anda menghitung jarak antara bola dan garis)

Jarak antara titik dan garis:
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

Berikut ini adalah implementasi dalam Javascript. Pendekatan saya adalah pertama-tama mengubah segmen garis menjadi garis yang tak terbatas kemudian menemukan titik persimpangan. Dari sana saya memeriksa apakah titik yang ditemukan berada di segmen garis. Kode ini didokumentasikan dengan baik, Anda harus dapat mengikuti.

Anda dapat mencoba kode di sini di demo langsung ini . Kode diambil dari repo algoritme saya .

// 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 [];

}

Dalam tumbukan garis lingkaran posting ini akan diperiksa dengan memeriksa jarak antara pusat lingkaran dan titik pada segmen garis (Ipoint) yang mewakili titik persimpangan antara N normal (Gambar 2) dari pusat lingkaran ke segmen garis.

( https://i.stack.imgur.com/3o6do.png )

Pada gambar 1 satu lingkaran dan satu garis ditampilkan, vektor A titik ke titik awal, vektor B titik ke titik akhir garis, vektor C titik ke pusat lingkaran. Sekarang kita harus menemukan vektor E (dari titik awal garis ke pusat lingkaran) dan vektor D (dari titik awal garis ke titik akhir garis) perhitungan ini ditunjukkan pada gambar 1.

( https://i.stack.imgur.com/7098a.png )

Pada gambar 2 kita dapat melihat bahwa vektor E diproyeksikan pada Vektor D oleh "titik produk" dari vektor E dan satuan vektor D, hasil dari produk titik adalah skalar Xp yang mewakili jarak antara titik mulai garis dan titik persimpangan (titik) dari vektor N dan vektor D. Selanjutnya vektor X ditemukan dengan mengalikan vektor satuan D dan skalar Xp.

Sekarang kita perlu menemukan vektor Z (vektor ke Ipoint), mudahnya penambahan vektor sederhana dari vektor A (titik awal on line) dan vektor X. Selanjutnya kita perlu berurusan dengan kasus-kasus khusus yang harus kita periksa adalah Ipoint pada segmen garis, jika itu bukan kita harus mencari tahu apakah itu kiri atau kanan itu, kita akan menggunakan vektor terdekat untuk menentukan titik mana yang paling dekat dengan lingkaran.

( https://i.stack.imgur.com/p9WIr.png )

Ketika proyeksi Xp negatif Ipoint berada di sebelah kiri segmen garis, vektor terdekat sama dengan vektor titik awal garis, ketika proyeksi Xp lebih besar daripada besarnya vektor D maka Ipoint kanan segmen garis kemudian vektor terdekat sama dengan vektor garis akhir titik dalam hal lain vektor terdekat sama dengan vektor Z.

Sekarang ketika kita memiliki vektor terdekat, kita perlu menemukan vektor dari pusat lingkaran ke Ipoint (vektor dist), sederhana kita hanya perlu mengurangi vektor terdekat dari vektor pusat. Selanjutnya hanya memeriksa apakah besarnya dist vektor kurang dari jari-jari lingkaran jika kemudian mereka bertabrakan, jika tidak ada tabrakan.

( https://i.stack.imgur.com/QJ63q.png )

Untuk akhirnya, kita dapat mengembalikan beberapa nilai untuk menyelesaikan tabrakan, cara termudah adalah dengan mengembalikan tumpang tindih tabrakan (kurangi jari-jari dari besaran dist vektor) dan kembali sumbu tabrakan, vektor D. Juga titik persimpangan adalah vektor Z jika diperlukan.

Jika koordinat garis adalah Ax, Ay dan Bx, By dan lingkaran pusatnya adalah Cx, Cy maka rumus garisnya adalah:

x = Kapak * t + Bx * (1 - t)

y = Ay * t + Oleh * (1 - t)

di mana 0 <= t <= 1

dan lingkaran itu

(Cx - x) ^ 2 + (Cy - y) ^ 2 = R ^ 2

jika Anda mengganti rumus x dan y dari garis ke rumus lingkaran Anda mendapatkan persamaan orde kedua dari t dan solusinya adalah titik persimpangan (jika ada). Jika Anda mendapatkan yang lebih kecil dari 0 atau lebih besar dari 1 maka itu bukan solusi tetapi itu menunjukkan bahwa garis 'menunjuk' ke arah lingkaran.

Hanya tambahan untuk utas ini ... Di bawah ini adalah versi kode yang diposting oleh pahlevan, tetapi untuk C # / XNA dan dirapikan sedikit:

    /// <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

Saya telah membuat fungsi ini untuk iOS mengikuti jawaban yang diberikan oleh 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;
}

Satu lagi di c # (sebagian kelas Circle). Diuji dan bekerja seperti pesona.

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);
    }

Yg dibutuhkan:

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;
        }

        // ******************************************************************
    }
}

Berikut ini adalah solusi yang baik dalam JavaScript (dengan semua matematika yang diperlukan dan ilustrasi langsung) https://bl.ocks.org/milkbread/11000965

Padahal is_onfungsi dalam solusi itu perlu modifikasi:

function is_on(a, b, c) {
    return Math.abs(distance(a,c) + distance(c,b) - distance(a,b))<0.000001;
}

Circle benar-benar orang jahat :) Jadi cara yang baik adalah menghindari lingkaran sejati, jika Anda bisa. Jika Anda melakukan pemeriksaan tabrakan untuk gim, Anda bisa menggunakan beberapa penyederhanaan dan hanya memiliki produk 3 titik, dan beberapa perbandingan.

Saya menyebutnya "titik lemak" atau "lingkaran tipis". jenisnya berupa elips dengan jari-jari nol searah dengan suatu segmen. tetapi jari-jari penuh dalam arah yang tegak lurus terhadap suatu ruas

Pertama, saya akan mempertimbangkan penggantian nama dan switching sistem koordinat untuk menghindari data yang berlebihan:

s0s1 = B-A;
s0qp = C-A;
rSqr = r*r;

Kedua, indeks h dalam hvec2f berarti daripada vektor harus mendukung operasi horisontal, seperti dot () / det (). Yang berarti komponen-komponennya harus ditempatkan dalam register xmm yang terpisah, untuk menghindari pengocokan / hadd'ing / hsub'ing. Dan di sini kita mulai, dengan versi paling banyak dari pendeteksian tabrakan paling sederhana untuk game 2D:

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;
}

Saya ragu Anda dapat mengoptimalkannya lebih jauh. Saya menggunakannya untuk deteksi tabrakan balap mobil yang digerakkan oleh jaringan saraf, untuk memproses jutaan langkah iterasi.

Fungsi Java ini mengembalikan Objek DVec2. Dibutuhkan DVec2 untuk pusat lingkaran, jari-jari lingkaran, dan Garis.

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;
}

Ini solusi saya di TypeScript, mengikuti gagasan yang disarankan oleh @Mizipzor (menggunakan proyeksi):

/**
 * 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;
}

Saya tahu sudah lama sejak utas ini terbuka. Dari jawaban yang diberikan oleh chmike dan ditingkatkan oleh Aqib Mumtaz. Mereka memberikan jawaban yang baik tetapi hanya bekerja untuk garis yang tak terbatas seperti kata Aqib. Jadi saya menambahkan beberapa perbandingan untuk mengetahui apakah segmen garis menyentuh lingkaran, saya menulisnya dengan Python.

def LineIntersectCircle(c, r, p1, p2):
    #p1 is the first line point
    #p2 is the second line point
    #c is the circle's center
    #r is the circle's radius

    p3 = [p1[0]-c[0], p1[1]-c[1]]
    p4 = [p2[0]-c[0], p2[1]-c[1]]

    m = (p4[1] - p3[1]) / (p4[0] - p3[0])
    b = p3[1] - m * p3[0]

    underRadical = math.pow(r,2)*math.pow(m,2) + math.pow(r,2) - math.pow(b,2)

    if (underRadical < 0):
        print("NOT")
    else:
        t1 = (-2*m*b+2*math.sqrt(underRadical)) / (2 * math.pow(m,2) + 2)
        t2 = (-2*m*b-2*math.sqrt(underRadical)) / (2 * math.pow(m,2) + 2)
        i1 = [t1+c[0], m * t1 + b + c[1]]
        i2 = [t2+c[0], m * t2 + b + c[1]]

        if p1[0] > p2[0]:                                           #Si el punto 1 es mayor al 2 en X
            if (i1[0] < p1[0]) and (i1[0] > p2[0]):                 #Si el punto iX esta entre 2 y 1 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i1[1] < p1[1]) and (i1[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i1[1] > p1[1]) and (i1[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

        if p1[0] < p2[0]:                                           #Si el punto 2 es mayor al 1 en X
            if (i1[0] > p1[0]) and (i1[0] < p2[0]):                 #Si el punto iX esta entre 1 y 2 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i1[1] < p1[1]) and (i1[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i1[1] > p1[1]) and (i1[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

        if p1[0] > p2[0]:                                           #Si el punto 1 es mayor al 2 en X
            if (i2[0] < p1[0]) and (i2[0] > p2[0]):                 #Si el punto iX esta entre 2 y 1 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i2[1] < p1[1]) and (i2[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i2[1] > p1[1]) and (i2[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

        if p1[0] < p2[0]:                                           #Si el punto 2 es mayor al 1 en X
            if (i2[0] > p1[0]) and (i2[0] < p2[0]):                 #Si el punto iX esta entre 1 y 2 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i2[1] < p1[1]) and (i2[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i2[1] > p1[1]) and (i2[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

Berikut adalah solusi yang ditulis dalam golang. Metode ini mirip dengan beberapa jawaban lain yang diposting di sini, tetapi tidak persis sama. Mudah diimplementasikan, dan telah diuji. Berikut langkah-langkahnya:

1. Terjemahkan koordinat sehingga lingkaran berada di titik asal.
2. Ekspresikan segmen garis sebagai fungsi parametrized dari t untuk koordinat x dan y. Jika t adalah 0, nilai fungsi adalah satu titik akhir segmen, dan jika t adalah 1, nilai fungsi adalah titik akhir lainnya.
3. Selesaikan, jika mungkin, persamaan kuadratik yang dihasilkan dari nilai-nilai pembatas t yang menghasilkan koordinat x, y dengan jarak dari titik asal sama dengan jari-jari lingkaran.
4. Buang solusi di mana t adalah <0 atau> 1 (<= 0 atau> = 1 untuk segmen terbuka). Poin-poin itu tidak terkandung dalam segmen.
5. Terjemahkan kembali ke koordinat asli.

Nilai untuk A, B, dan C untuk kuadrat diturunkan di sini, di mana (n-et) dan (m-dt) adalah persamaan untuk koordinat garis x dan y, masing-masing. r adalah jari-jari lingkaran.

(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

Karena itu A = ee + dd, B = - 2 (en + dm), dan C = nn + mm - rr.

Berikut adalah kode golang untuk fungsinya:

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
}

Saya mengujinya dengan fungsi ini, yang menegaskan bahwa titik solusi berada dalam segmen garis dan pada lingkaran. Itu membuat segmen tes dan menyapu di sekitar lingkaran yang diberikan:

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.")
}

Berikut ini adalah hasil tes:

=== RUN   TestSegmentCircleIntersection
--- PASS: TestSegmentCircleIntersection (0.00s)
    geom_test.go:105: Tested  40000  examples and found  7343  solutions.

Akhirnya, metode ini mudah diperluas ke kasus sinar mulai dari satu titik, melewati titik lain dan meluas hingga tak terbatas, dengan hanya menguji jika t> 0 atau t <1 tetapi tidak keduanya.

Saya hanya butuh itu, jadi saya datang dengan solusi ini. Bahasa ini maxscript, tetapi harus dengan mudah diterjemahkan ke bahasa lain. sideA, sideB dan CircleRadius adalah skalar, variabel sisanya adalah titik sebagai [x, y, z]. Saya mengasumsikan z = 0 untuk menyelesaikan di pesawat 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)
)

Solusi dalam python, berdasarkan @ Jo Skeen

def check_line_segment_circle_intersection(line, point, radious):
    """ Checks whether a point intersects with a line defined by two points.

    A `point` is list with two values: [2, 3]

    A `line` is list with two points: [point1, point2]

    """
    line_distance = distance(line[0], line[1])
    distance_start_to_point = distance(line[0], point)
    distance_end_to_point = distance(line[1], point)

    if (distance_start_to_point <= radious or distance_end_to_point <= radious):
        return True

    # angle between line and point with law of cosines
    numerator = (math.pow(distance_start_to_point, 2)
                 + math.pow(line_distance, 2)
                 - math.pow(distance_end_to_point, 2))
    denominator = 2 * distance_start_to_point * line_distance
    ratio = numerator / denominator
    ratio = ratio if ratio <= 1 else 1  # To account for float errors
    ratio = ratio if ratio >= -1 else -1  # To account for float errors
    angle = math.acos(ratio)

    # distance from the point to the line with sin projection
    distance_line_to_point = math.sin(angle) * distance_start_to_point

    if distance_line_to_point <= radious:
        point_projection_in_line = math.cos(angle) * distance_start_to_point
        # Intersection occurs whent the point projection in the line is less
        # than the line distance and positive
        return point_projection_in_line <= line_distance and point_projection_in_line >= 0
    return False

def distance(point1, point2):
    return math.sqrt(
        math.pow(point1[1] - point2[1], 2) +
        math.pow(point1[0] - point2[0], 2)
    )

Function lineCircleCollision(p1,p2,c,r,precision){
Let dx = (p2.x-p1.x)/precision
Let dy = (p2.y-p1.y)/precision
Let collision=false
For(let i = 0;i<precision:i++){
If(Math.sqrt((p1.x+dx*i-c.x)**2+(p1.y+dy*i-c.y)**2).<r {
Collision=true
}
}

Anda dapat mengambil titik-titik spasi X yang merata dari garis dan jika ada di dalam lingkaran, ada tabrakan