Jarak terpendek antara titik dan segmen garis

360

Saya memerlukan fungsi dasar untuk menemukan jarak terpendek antara titik dan segmen garis. Jangan ragu untuk menulis solusi dalam bahasa apa pun yang Anda inginkan; Saya bisa menerjemahkannya ke dalam apa yang saya gunakan (Javascript).

EDIT: Segmen baris saya ditentukan oleh dua titik akhir. Jadi segmen garis saya ABditentukan oleh dua poin A (x1,y1)dan B (x2,y2). Saya mencoba mencari jarak antara segmen garis ini dan satu titik C (x3,y3). Keterampilan geometri saya berkarat, jadi contoh yang saya lihat membingungkan, saya minta maaf untuk mengakui.

Eli Courtwright
sumber
Aku tidak tahu bagaimana Anda mewakili garis dan titik, tapi di sini adalah semua matematika yang Anda butuhkan untuk memulai. Seharusnya tidak terlalu sulit untuk mencari tahu apa yang perlu Anda lakukan.
mandaleeka
4
@ArthurKalliokoski: tautan itu sudah mati, tapi saya sudah menemukan salinannya: paulbourke.net/geometry/pointline
Gunther Struyf
11
@GuntherStruyf: tautan itu sudah mati juga, tetapi tautan serupa ini berfungsi: paulbourke.net/geometry/pointlineplane
Michael
1
Jika seseorang mencari jarak antara titik dan garis, bukan titik dan garis SEGMENT, periksa tautan ini: gist.github.com/rhyolight/2846020
Nick Budden
1
Tautan di atas sudah mati. Inilah pseudo-code dan sampel c ++, dijelaskan dan diturunkan sedetail sebagai buku teks, geomalgorithms.com/a02-_lines.html
Eric

Jawaban:

448

Eli, kode yang Anda pilih salah. Suatu titik di dekat garis di mana segmen terletak tetapi jauh salah satu ujung segmen akan dinilai secara salah di dekat segmen. Pembaruan: Jawaban yang salah tersebut tidak lagi diterima.

Berikut ini beberapa kode yang benar, di C ++. Ini mengandaikan kelas 2D-vektor class vec2 {float x,y;}, pada dasarnya, dengan operator untuk menambahkan, subract, skala, dll, dan fungsi produk jarak dan titik (yaitu x1 x2 + y1 y2)

float minimum_distance(vec2 v, vec2 w, vec2 p) {
  // Return minimum distance between line segment vw and point p
  const float l2 = length_squared(v, w);  // i.e. |w-v|^2 -  avoid a sqrt
  if (l2 == 0.0) return distance(p, v);   // v == w case
  // Consider the line extending the segment, parameterized as v + t (w - v).
  // We find projection of point p onto the line. 
  // It falls where t = [(p-v) . (w-v)] / |w-v|^2
  // We clamp t from [0,1] to handle points outside the segment vw.
  const float t = max(0, min(1, dot(p - v, w - v) / l2));
  const vec2 projection = v + t * (w - v);  // Projection falls on the segment
  return distance(p, projection);
}

EDIT: Saya membutuhkan implementasi Javascript, jadi ini dia, tanpa dependensi (atau komentar, tetapi ini adalah port langsung di atas). Poin direpresentasikan sebagai objek dengan xdan yatribut.

function sqr(x) { return x * x }
function dist2(v, w) { return sqr(v.x - w.x) + sqr(v.y - w.y) }
function distToSegmentSquared(p, v, w) {
  var l2 = dist2(v, w);
  if (l2 == 0) return dist2(p, v);
  var t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
  t = Math.max(0, Math.min(1, t));
  return dist2(p, { x: v.x + t * (w.x - v.x),
                    y: v.y + t * (w.y - v.y) });
}
function distToSegment(p, v, w) { return Math.sqrt(distToSegmentSquared(p, v, w)); }

EDIT 2: Saya membutuhkan versi Java, tetapi yang lebih penting, saya membutuhkannya di 3d bukan 2d.

float dist_to_segment_squared(float px, float py, float pz, float lx1, float ly1, float lz1, float lx2, float ly2, float lz2) {
  float line_dist = dist_sq(lx1, ly1, lz1, lx2, ly2, lz2);
  if (line_dist == 0) return dist_sq(px, py, pz, lx1, ly1, lz1);
  float t = ((px - lx1) * (lx2 - lx1) + (py - ly1) * (ly2 - ly1) + (pz - lz1) * (lz2 - lz1)) / line_dist;
  t = constrain(t, 0, 1);
  return dist_sq(px, py, pz, lx1 + t * (lx2 - lx1), ly1 + t * (ly2 - ly1), lz1 + t * (lz2 - lz1));
}
Grumdrig
sumber
1
Saya telah menambahkan versi yang lebih lengkap dari ini sebagai jawaban terpisah.
M Katz
4
Terima kasih @Grumdrig, solusi javascript Anda tepat dan menghemat waktu. Saya porting solusi Anda ke Objective-C dan menambahkannya di bawah ini.
awolf
1
Kami benar-benar hanya berusaha menghindari kesenjangan dengan nol di sana.
Grumdrig
9
Proyeksi titik pke garis adalah titik pada garis yang paling dekat dengannya p. (Dan tegak lurus terhadap garis proyeksi akan melewati p.) Jumlah tadalah seberapa jauh sepanjang segmen garis dari vke wproyeksi jatuh. Jadi jika t0 proyeksi jatuh tepat v; jika 1, aktif w; misalnya 0,5, misalnya, maka separuh jalan. Jika tkurang dari 0 atau lebih besar dari 1 itu jatuh pada garis melewati satu ujung atau yang lain dari segmen. Dalam hal ini jarak ke segmen akan menjadi jarak ke ujung yang lebih dekat.
Grumdrig
1
Ups - tidak melihat ada yang menyediakan versi 3D. @RogiSolorzano, Anda harus mengubah koordinat lat, koordinat panjang menjadi koordinat x, y, z dalam ruang 3 terlebih dahulu.
Grumdrig
112

Berikut ini adalah kode lengkap paling sederhana dalam Javascript.

x, y adalah titik target Anda dan x1, y1 ke x2, y2 adalah segmen garis Anda.

DIPERBARUI: perbaiki untuk masalah garis 0 panjang dari komentar.

function pDistance(x, y, x1, y1, x2, y2) {

  var A = x - x1;
  var B = y - y1;
  var C = x2 - x1;
  var D = y2 - y1;

  var dot = A * C + B * D;
  var len_sq = C * C + D * D;
  var param = -1;
  if (len_sq != 0) //in case of 0 length line
      param = dot / len_sq;

  var xx, yy;

  if (param < 0) {
    xx = x1;
    yy = y1;
  }
  else if (param > 1) {
    xx = x2;
    yy = y2;
  }
  else {
    xx = x1 + param * C;
    yy = y1 + param * D;
  }

  var dx = x - xx;
  var dy = y - yy;
  return Math.sqrt(dx * dx + dy * dy);
}

Gambar untuk membantu memvisualisasikan solusi

Joshua
sumber
8
Dari semua kode yang saya lihat untuk menyelesaikan masalah ini, saya paling suka yang ini. Sangat jelas dan mudah dibaca. Namun matematika di baliknya agak mistis. Apa yang dimaksud dengan produk-titik dibagi dengan panjang kuadrat, misalnya?
user1815201
2
Produk titik dibagi dengan kuadrat panjang memberi Anda jarak proyeksi dari (x1, y1). Ini adalah sebagian kecil dari garis yang titik (x, y) terdekat. Perhatikan klausa final lainnya di mana (xx, yy) dihitung - ini proyeksi titik (x, y) ke segmen (x1, y1) - (x2, y2).
Logan Pickup
4
Pemeriksaan untuk segmen garis dengan panjang 0 terlalu jauh ke bawah dalam kode. 'len_sq' akan menjadi nol dan kode akan dibagi 0 sebelum sampai ke pemeriksaan keamanan.
HostedMetrics.com
17
Meter. Itu dikembalikan dalam meter.
Joshua
1
@nevermind, mari kita sebut titik kita p0 dan titik-titik yang mendefinisikan garis sebagai p1 dan p2. Kemudian Anda mendapatkan vektor A = p0 - p1 dan B = p2 - p1. Param adalah nilai skalar yang bila dikalikan dengan B memberi Anda titik pada garis terdekat dengan p0. Jika param <= 0, titik terdekat adalah p1. Jika param> = 1, titik terdekat adalah p1. Jika berada di antara 0 dan 1, di suatu tempat antara p1 dan p2 jadi kami interpolasi. XX dan YY adalah titik terdekat pada segmen garis, dx / dy adalah vektor dari p0 ke titik itu, dan akhirnya kita mengembalikan panjang vektor itu.
Sean
70

Ini adalah implementasi yang dibuat untuk FINANCE LINE SEGMENTS, bukan garis tak terbatas seperti kebanyakan fungsi lain di sini (itulah sebabnya saya membuat ini).

Implementasi teori oleh Paul Bourke .

Python:

def dist(x1, y1, x2, y2, x3, y3): # x3,y3 is the point
    px = x2-x1
    py = y2-y1

    norm = px*px + py*py

    u =  ((x3 - x1) * px + (y3 - y1) * py) / float(norm)

    if u > 1:
        u = 1
    elif u < 0:
        u = 0

    x = x1 + u * px
    y = y1 + u * py

    dx = x - x3
    dy = y - y3

    # Note: If the actual distance does not matter,
    # if you only want to compare what this function
    # returns to other results of this function, you
    # can just return the squared distance instead
    # (i.e. remove the sqrt) to gain a little performance

    dist = (dx*dx + dy*dy)**.5

    return dist

AS3:

public static function segmentDistToPoint(segA:Point, segB:Point, p:Point):Number
{
    var p2:Point = new Point(segB.x - segA.x, segB.y - segA.y);
    var something:Number = p2.x*p2.x + p2.y*p2.y;
    var u:Number = ((p.x - segA.x) * p2.x + (p.y - segA.y) * p2.y) / something;

    if (u > 1)
        u = 1;
    else if (u < 0)
        u = 0;

    var x:Number = segA.x + u * p2.x;
    var y:Number = segA.y + u * p2.y;

    var dx:Number = x - p.x;
    var dy:Number = y - p.y;

    var dist:Number = Math.sqrt(dx*dx + dy*dy);

    return dist;
}

Jawa

private double shortestDistance(float x1,float y1,float x2,float y2,float x3,float y3)
    {
        float px=x2-x1;
        float py=y2-y1;
        float temp=(px*px)+(py*py);
        float u=((x3 - x1) * px + (y3 - y1) * py) / (temp);
        if(u>1){
            u=1;
        }
        else if(u<0){
            u=0;
        }
        float x = x1 + u * px;
        float y = y1 + u * py;

        float dx = x - x3;
        float dy = y - y3;
        double dist = Math.sqrt(dx*dx + dy*dy);
        return dist;

    }
quano
sumber
2
Maaf, tapi saya mencoba ini dan masih memberi saya hasil seolah-olah garis itu meluas hingga tak terbatas. Saya telah menemukan jawaban Grumdig untuk bekerja.
Frederik
1
Dalam hal ini Anda salah menggunakannya atau memaknai sesuatu yang tidak terbatas. Lihat contoh kode ini di sini: boomie.se/upload/Drawdebug.swf
quano
Tampak seperti kesalahan dalam kode atau sesuatu, saya mendapatkan hasil yang sama dengan Frederik /
Kromster
30
Pilihan nama variabel jauh dari baik (p2, sesuatu, u, ...)
miguelSantirso
2
Saya sudah mencoba versi Python fungsi dan menemukan bahwa itu menunjukkan hasil yang salah jika parameternya adalah bilangan bulat. distAnother(0, 0, 4, 0, 2, 2)memberikan 2.8284271247461903 (salah). distAnother(0., 0., 4., 0., 2., 2.)memberi 2.0 (benar). Harap perhatikan hal ini. Saya pikir kode dapat ditingkatkan untuk memiliki konversi mengambang di suatu tempat.
Vladimir Obrizan
22

Di utas pertanyaan saya sendiri bagaimana cara menghitung jarak 2D terpendek antara titik dan segmen garis dalam semua kasus di C, C # / .NET 2.0 atau Java? Saya diminta untuk memberikan jawaban C # di sini ketika saya menemukan satu: jadi ini dia, dimodifikasi dari http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static :

//Compute the dot product AB . BC
private double DotProduct(double[] pointA, double[] pointB, double[] pointC)
{
    double[] AB = new double[2];
    double[] BC = new double[2];
    AB[0] = pointB[0] - pointA[0];
    AB[1] = pointB[1] - pointA[1];
    BC[0] = pointC[0] - pointB[0];
    BC[1] = pointC[1] - pointB[1];
    double dot = AB[0] * BC[0] + AB[1] * BC[1];

    return dot;
}

//Compute the cross product AB x AC
private double CrossProduct(double[] pointA, double[] pointB, double[] pointC)
{
    double[] AB = new double[2];
    double[] AC = new double[2];
    AB[0] = pointB[0] - pointA[0];
    AB[1] = pointB[1] - pointA[1];
    AC[0] = pointC[0] - pointA[0];
    AC[1] = pointC[1] - pointA[1];
    double cross = AB[0] * AC[1] - AB[1] * AC[0];

    return cross;
}

//Compute the distance from A to B
double Distance(double[] pointA, double[] pointB)
{
    double d1 = pointA[0] - pointB[0];
    double d2 = pointA[1] - pointB[1];

    return Math.Sqrt(d1 * d1 + d2 * d2);
}

//Compute the distance from AB to C
//if isSegment is true, AB is a segment, not a line.
double LineToPointDistance2D(double[] pointA, double[] pointB, double[] pointC, 
    bool isSegment)
{
    double dist = CrossProduct(pointA, pointB, pointC) / Distance(pointA, pointB);
    if (isSegment)
    {
        double dot1 = DotProduct(pointA, pointB, pointC);
        if (dot1 > 0) 
            return Distance(pointB, pointC);

        double dot2 = DotProduct(pointB, pointA, pointC);
        if (dot2 > 0) 
            return Distance(pointA, pointC);
    }
    return Math.Abs(dist);
} 

Saya @SO bukan untuk menjawab tetapi mengajukan pertanyaan jadi saya harap saya tidak mendapatkan jutaan suara untuk beberapa alasan tetapi membangun kritik. Saya hanya ingin (dan didorong) untuk berbagi ide orang lain karena solusi di utas ini baik dengan beberapa bahasa eksotis (Fortran, Mathematica) atau ditandai sebagai salah oleh seseorang. Satu-satunya yang berguna (oleh Grumdrig) bagi saya ditulis dengan C ++ dan tidak ada yang menandainya salah. Tetapi tidak ada metode (titik dll.) Yang dipanggil.

karakter m
sumber
1
Terima kasih telah memposting ini. Tapi sepertinya ada optimasi yang jelas mungkin dalam metode terakhir: Jangan menghitung dist sampai setelah ditentukan bahwa itu diperlukan
RenniePet
2
Komentar pada DotProduct mengatakan ini komputasi AB.AC, tetapi komputasi AB.BC.
Metal450
Produk silang menurut definisi mengembalikan vektor tetapi mengembalikan skalar di sini.
SteakOverflow
21

Dalam F #, jarak dari titik cke segmen garis antara adan bdiberikan oleh:

let pointToLineSegmentDistance (a: Vector, b: Vector) (c: Vector) =
  let d = b - a
  let s = d.Length
  let lambda = (c - a) * d / s
  let p = (lambda |> max 0.0 |> min s) * d / s
  (a + p - c).Length

Vektor dmenunjuk dari ake bsepanjang segmen garis. Produk titik d/sdengan c-amemberikan parameter titik pendekatan terdekat antara garis tak terbatas dan titik c. Fungsi mindan maxdigunakan untuk menjepit parameter ini ke rentang 0..ssehingga titik terletak di antara adan b. Akhirnya, panjangnya a+p-cadalah jarak dari cke titik terdekat pada segmen garis.

Contoh penggunaan:

pointToLineSegmentDistance (Vector(0.0, 0.0), Vector(1.0, 0.0)) (Vector(-1.0, 1.0))
Jon Harrop
sumber
1
Saya pikir baris terakhir salah, dan harus membaca:(a + p - c).Length
Blair Holloway
Itu masih belum sepenuhnya memperbaiki masalah. Salah satu cara untuk memperbaiki fungsi adalah mendefinisikan ulang lambdadan psebagai let lambda = (c - a) * d / (s * s)dan let p = a + (lambda |> max 0.0 |> min 1.0) * d, masing-masing. Setelah itu fungsi mengembalikan jarak yang benar misalnya untuk kasus di mana a = (0,1), b = (1,0)dan c = (1,1).
mikkoma
20

Bagi siapa pun yang tertarik, inilah konversi sepele kode Javascript Joshua ke Objective-C:

- (double)distanceToPoint:(CGPoint)p fromLineSegmentBetween:(CGPoint)l1 and:(CGPoint)l2
{
    double A = p.x - l1.x;
    double B = p.y - l1.y;
    double C = l2.x - l1.x;
    double D = l2.y - l1.y;

    double dot = A * C + B * D;
    double len_sq = C * C + D * D;
    double param = dot / len_sq;

    double xx, yy;

    if (param < 0 || (l1.x == l2.x && l1.y == l2.y)) {
        xx = l1.x;
        yy = l1.y;
    }
    else if (param > 1) {
        xx = l2.x;
        yy = l2.y;
    }
    else {
        xx = l1.x + param * C;
        yy = l1.y + param * D;
    }

    double dx = p.x - xx;
    double dy = p.y - yy;

    return sqrtf(dx * dx + dy * dy);
}

Saya membutuhkan solusi ini untuk bekerja MKMapPointsehingga saya akan membagikannya jika ada orang lain yang membutuhkannya. Hanya beberapa perubahan kecil dan ini akan mengembalikan jarak dalam meter:

- (double)distanceToPoint:(MKMapPoint)p fromLineSegmentBetween:(MKMapPoint)l1 and:(MKMapPoint)l2
{
    double A = p.x - l1.x;
    double B = p.y - l1.y;
    double C = l2.x - l1.x;
    double D = l2.y - l1.y;

    double dot = A * C + B * D;
    double len_sq = C * C + D * D;
    double param = dot / len_sq;

    double xx, yy;

    if (param < 0 || (l1.x == l2.x && l1.y == l2.y)) {
        xx = l1.x;
        yy = l1.y;
    }
    else if (param > 1) {
        xx = l2.x;
        yy = l2.y;
    }
    else {
        xx = l1.x + param * C;
        yy = l1.y + param * D;
    }

    return MKMetersBetweenMapPoints(p, MKMapPointMake(xx, yy));
}
Ben Gotow
sumber
Ini tampaknya bekerja dengan baik untuk saya. Terima kasih telah mengonversi.
Gregir
Perlu diperhatikan, bahwa (xx, yy) adalah lokasi titik terdekat. Saya telah mengedit sedikit kode Anda, sehingga mengembalikan titik dan jarak, nama-nama yang di-refactored sehingga mereka menggambarkan apa itu dan memberikan contoh di: stackoverflow.com/a/28028023/849616 .
Vive
20

Dalam Mathematica

Ini menggunakan deskripsi parametrik segmen, dan memproyeksikan titik ke garis yang ditentukan oleh segmen. Saat parameter beralih dari 0 ke 1 di segmen, jika proyeksi berada di luar batas ini, kami menghitung jarak ke titik terkait, alih-alih garis lurus normal ke segmen.

Clear["Global`*"];
 distance[{start_, end_}, pt_] := 
   Module[{param},
   param = ((pt - start).(end - start))/Norm[end - start]^2; (*parameter. the "."
                                                       here means vector product*)

   Which[
    param < 0, EuclideanDistance[start, pt],                 (*If outside bounds*)
    param > 1, EuclideanDistance[end, pt],
    True, EuclideanDistance[pt, start + param (end - start)] (*Normal distance*)
    ]
   ];  

Merencanakan hasil:

Plot3D[distance[{{0, 0}, {1, 0}}, {xp, yp}], {xp, -1, 2}, {yp, -1, 2}]

teks alternatif

Plot titik-titik itu lebih dekat daripada jarak cutoff :

teks alternatif

Contour Plot:

masukkan deskripsi gambar di sini

Dr. belisarius
sumber
11

Hei, saya baru saja menulis ini kemarin. Ada dalam Actionscript 3.0, yang pada dasarnya adalah Javascript, meskipun Anda mungkin tidak memiliki kelas Point yang sama.

//st = start of line segment
//b = the line segment (as in: st + b = end of line segment)
//pt = point to test
//Returns distance from point to line segment.  
//Note: nearest point on the segment to the test point is right there if we ever need it
public static function linePointDist( st:Point, b:Point, pt:Point ):Number
{
    var nearestPt:Point; //closest point on seqment to pt

    var keyDot:Number = dot( b, pt.subtract( st ) ); //key dot product
    var bLenSq:Number = dot( b, b ); //Segment length squared

    if( keyDot <= 0 )  //pt is "behind" st, use st
    {
        nearestPt = st  
    }
    else if( keyDot >= bLenSq ) //pt is "past" end of segment, use end (notice we are saving twin sqrts here cuz)
    {
        nearestPt = st.add(b);
    }
    else //pt is inside segment, reuse keyDot and bLenSq to get percent of seqment to move in to find closest point
    {
        var keyDotToPctOfB:Number = keyDot/bLenSq; //REM dot product comes squared
        var partOfB:Point = new Point( b.x * keyDotToPctOfB, b.y * keyDotToPctOfB );
        nearestPt = st.add(partOfB);
    }

    var dist:Number = (pt.subtract(nearestPt)).length;

    return dist;
}

Juga, ada diskusi yang cukup lengkap dan mudah dibaca dari masalah di sini: notejot.com

Matt W
sumber
Terima kasih - ini adalah jenis kode yang saya cari. Saya telah memposting jawaban saya sendiri di bawah ini, karena saya berhasil menyatukan sesuatu yang berfungsi di era-browser-Javascript saat ini, tetapi saya telah menandai jawaban Anda sebagai diterima karena sederhana, ditulis dengan baik, mudah dipahami, dan sangat dihargai.
Eli Courtwright
Bukankah ini melewatkan metode-dot? Bagaimanapun, mudah untuk menghitung: vec1.x * vec2.x + vec1.y * vec2.y
quano
11

Untuk yang malas, inilah port Objective-C saya dari solusi @ Grumdrig di atas:

CGFloat sqr(CGFloat x) { return x*x; }
CGFloat dist2(CGPoint v, CGPoint w) { return sqr(v.x - w.x) + sqr(v.y - w.y); }
CGFloat distanceToSegmentSquared(CGPoint p, CGPoint v, CGPoint w)
{
    CGFloat l2 = dist2(v, w);
    if (l2 == 0.0f) return dist2(p, v);

    CGFloat t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
    if (t < 0.0f) return dist2(p, v);
    if (t > 1.0f) return dist2(p, w);
    return dist2(p, CGPointMake(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y)));
}
CGFloat distanceToSegment(CGPoint point, CGPoint segmentPointV, CGPoint segmentPointW)
{
    return sqrtf(distanceToSegmentSquared(point, segmentPointV, segmentPointW));
}
awolf
sumber
Saya mendapatkan 'nan' kembali dari baris ini. Ada yang tahu kenapa? ( return dist2(p, CGPointMake(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y)))
Ngomong
sqrtf () mengkuadratkan x, tidak mendapatkan akar
kuadratnya
@Senseful Tidak yakin apa yang Anda maksud. sqrtf adalah akar kuadrat. developer.apple.com/library/mac/documentation/Darwin/Reference/…
awolf
@ Hawolf: Lihatlah baris kode pertama di atas. Ini mendefinisikan metode sqrtf(x) = x*x.
Senseful
@Senseful, terima kasih, itu salah kaprah daripada melakukan operasi yang salah.
awolf
10

Tidak dapat menahan pengkodean dengan python :)

from math import sqrt, fabs
def pdis(a, b, c):
    t = b[0]-a[0], b[1]-a[1]           # Vector ab
    dd = sqrt(t[0]**2+t[1]**2)         # Length of ab
    t = t[0]/dd, t[1]/dd               # unit vector of ab
    n = -t[1], t[0]                    # normal unit vector to ab
    ac = c[0]-a[0], c[1]-a[1]          # vector ac
    return fabs(ac[0]*n[0]+ac[1]*n[1]) # Projection of ac to n (the minimum distance)

print pdis((1,1), (2,2), (2,0))        # Example (answer is 1.414)


Ditto for fortran :)

real function pdis(a, b, c)
    real, dimension(0:1), intent(in) :: a, b, c
    real, dimension(0:1) :: t, n, ac
    real :: dd
    t = b - a                          ! Vector ab
    dd = sqrt(t(0)**2+t(1)**2)         ! Length of ab
    t = t/dd                           ! unit vector of ab
    n = (/-t(1), t(0)/)                ! normal unit vector to ab
    ac = c - a                         ! vector ac
    pdis = abs(ac(0)*n(0)+ac(1)*n(1))  ! Projection of ac to n (the minimum distance)
end function pdis


program test
    print *, pdis((/1.0,1.0/), (/2.0,2.0/), (/2.0,0.0/))   ! Example (answer is 1.414)
end program test
cyberthanasis
sumber
10
bukankah ini menghitung jarak titik ke garis, bukan segmen?
balint.miklos
6
Ini memang jarak ke garis segmen aktif, bukan ke segmen.
Grumdrig
12
Ini sepertinya tidak berhasil. Jika Anda memiliki segmen (0,0) dan (5,0), dan coba terhadap poin (7,0), itu akan mengembalikan 0, yang tidak benar. Jaraknya harus 2.
quano
8
Dia gagal mempertimbangkan kasus di mana proyeksi titik ke segmen berada di luar interval dari A ke B. Itu mungkin yang diinginkan si penanya, tetapi bukan yang dia tanyakan.
phkahler
5
Ini bukan yang semula ditanyakan.
Sambatyon
10

Berikut ini ejaan yang lebih lengkap dari solusi Grumdrig. Versi ini juga mengembalikan titik terdekat itu sendiri.

#include "stdio.h"
#include "math.h"

class Vec2
{
public:
    float _x;
    float _y;

    Vec2()
    {
        _x = 0;
        _y = 0;
    }

    Vec2( const float x, const float y )
    {
        _x = x;
        _y = y;
    }

    Vec2 operator+( const Vec2 &v ) const
    {
        return Vec2( this->_x + v._x, this->_y + v._y );
    }

    Vec2 operator-( const Vec2 &v ) const
    {
        return Vec2( this->_x - v._x, this->_y - v._y );
    }

    Vec2 operator*( const float f ) const
    {
        return Vec2( this->_x * f, this->_y * f );
    }

    float DistanceToSquared( const Vec2 p ) const
    {
        const float dX = p._x - this->_x;
        const float dY = p._y - this->_y;

        return dX * dX + dY * dY;
    }

    float DistanceTo( const Vec2 p ) const
    {
        return sqrt( this->DistanceToSquared( p ) );
    }

    float DotProduct( const Vec2 p ) const
    {
        return this->_x * p._x + this->_y * p._y;
    }
};

// return minimum distance between line segment vw and point p, and the closest point on the line segment, q
float DistanceFromLineSegmentToPoint( const Vec2 v, const Vec2 w, const Vec2 p, Vec2 * const q )
{
    const float distSq = v.DistanceToSquared( w ); // i.e. |w-v|^2 ... avoid a sqrt
    if ( distSq == 0.0 )
    {
        // v == w case
        (*q) = v;

        return v.DistanceTo( p );
    }

    // consider the line extending the segment, parameterized as v + t (w - v)
    // we find projection of point p onto the line
    // it falls where t = [(p-v) . (w-v)] / |w-v|^2

    const float t = ( p - v ).DotProduct( w - v ) / distSq;
    if ( t < 0.0 )
    {
        // beyond the v end of the segment
        (*q) = v;

        return v.DistanceTo( p );
    }
    else if ( t > 1.0 )
    {
        // beyond the w end of the segment
        (*q) = w;

        return w.DistanceTo( p );
    }

    // projection falls on the segment
    const Vec2 projection = v + ( ( w - v ) * t );

    (*q) = projection;

    return p.DistanceTo( projection );
}

float DistanceFromLineSegmentToPoint( float segmentX1, float segmentY1, float segmentX2, float segmentY2, float pX, float pY, float *qX, float *qY )
{
    Vec2 q;

    float distance = DistanceFromLineSegmentToPoint( Vec2( segmentX1, segmentY1 ), Vec2( segmentX2, segmentY2 ), Vec2( pX, pY ), &q );

    (*qX) = q._x;
    (*qY) = q._y;

    return distance;
}

void TestDistanceFromLineSegmentToPoint( float segmentX1, float segmentY1, float segmentX2, float segmentY2, float pX, float pY )
{
    float qX;
    float qY;
    float d = DistanceFromLineSegmentToPoint( segmentX1, segmentY1, segmentX2, segmentY2, pX, pY, &qX, &qY );
    printf( "line segment = ( ( %f, %f ), ( %f, %f ) ), p = ( %f, %f ), distance = %f, q = ( %f, %f )\n",
            segmentX1, segmentY1, segmentX2, segmentY2, pX, pY, d, qX, qY );
}

void TestDistanceFromLineSegmentToPoint()
{
    TestDistanceFromLineSegmentToPoint( 0, 0, 1, 1, 1, 0 );
    TestDistanceFromLineSegmentToPoint( 0, 0, 20, 10, 5, 4 );
    TestDistanceFromLineSegmentToPoint( 0, 0, 20, 10, 30, 15 );
    TestDistanceFromLineSegmentToPoint( 0, 0, 20, 10, -30, 15 );
    TestDistanceFromLineSegmentToPoint( 0, 0, 10, 0, 5, 1 );
    TestDistanceFromLineSegmentToPoint( 0, 0, 0, 10, 1, 5 );
}
M Katz
sumber
Terima kasih telah memposting ini. Sangat terstruktur dengan baik dan berkomentar dan diformat - hampir membuat saya lupa betapa saya tidak suka C ++. Saya telah menggunakan ini untuk membuat versi C # yang sesuai, yang sekarang saya posting di sini.
RenniePet
10

Satu solusi garis menggunakan arctangents:

Idenya adalah untuk memindahkan A ke (0, 0) dan memutar segitiga searah jarum jam untuk membuat C berbaring di sumbu X, ketika ini terjadi, By akan menjadi jarak.

  1. a angle = Atan (Cy - Ay, Cx - Axe);
  2. b angle = Atan (By-Ay, Bx - Axe);
  3. Panjang AB = Sqrt ((Bx - Axe) ^ 2 + (By - Ay) ^ 2)
  4. By = Sin (bAngle - aAngle) * ABLength

C #

public double Distance(Point a, Point b, Point c)
{
    // normalize points
    Point cn = new Point(c.X - a.X, c.Y - a.Y);
    Point bn = new Point(b.X - a.X, b.Y - a.Y);

    double angle = Math.Atan2(bn.Y, bn.X) - Math.Atan2(cn.Y, cn.X);
    double abLength = Math.Sqrt(bn.X*bn.X + bn.Y*bn.Y);

    return Math.Sin(angle)*abLength;
}

Satu baris C # (untuk dikonversi ke SQL)

double distance = Math.Sin(Math.Atan2(b.Y - a.Y, b.X - a.X) - Math.Atan2(c.Y - a.Y, c.X - a.X)) * Math.Sqrt((b.X - a.X) * (b.X - a.X) + (b.Y - a.Y) * (b.Y - a.Y))
ADOConnection
sumber
7

Pertimbangkan modifikasi ini untuk jawaban Grumdrig di atas. Sering kali Anda akan menemukan bahwa ketidaktepatan floating point dapat menyebabkan masalah. Saya menggunakan ganda dalam versi di bawah ini, tetapi Anda dapat dengan mudah berubah menjadi mengapung. Bagian yang penting adalah ia menggunakan epsilon untuk menangani "slop". Selain itu, Anda akan berkali-kali ingin tahu DI MANA persimpangan itu terjadi, atau jika itu terjadi sama sekali. Jika t yang dikembalikan <0,0 atau> 1,0, tidak ada tabrakan terjadi. Namun, bahkan jika tidak ada tabrakan, berkali-kali Anda ingin tahu di mana titik terdekat pada segmen ke P, dan dengan demikian saya menggunakan qx dan qy untuk mengembalikan lokasi ini.

double PointSegmentDistanceSquared( double px, double py,
                                    double p1x, double p1y,
                                    double p2x, double p2y,
                                    double& t,
                                    double& qx, double& qy)
{
    static const double kMinSegmentLenSquared = 0.00000001;  // adjust to suit.  If you use float, you'll probably want something like 0.000001f
    static const double kEpsilon = 1.0E-14;  // adjust to suit.  If you use floats, you'll probably want something like 1E-7f
    double dx = p2x - p1x;
    double dy = p2y - p1y;
    double dp1x = px - p1x;
    double dp1y = py - p1y;
    const double segLenSquared = (dx * dx) + (dy * dy);
    if (segLenSquared >= -kMinSegmentLenSquared && segLenSquared <= kMinSegmentLenSquared)
    {
        // segment is a point.
        qx = p1x;
        qy = p1y;
        t = 0.0;
        return ((dp1x * dp1x) + (dp1y * dp1y));
    }
    else
    {
        // Project a line from p to the segment [p1,p2].  By considering the line
        // extending the segment, parameterized as p1 + (t * (p2 - p1)),
        // we find projection of point p onto the line. 
        // It falls where t = [(p - p1) . (p2 - p1)] / |p2 - p1|^2
        t = ((dp1x * dx) + (dp1y * dy)) / segLenSquared;
        if (t < kEpsilon)
        {
            // intersects at or to the "left" of first segment vertex (p1x, p1y).  If t is approximately 0.0, then
            // intersection is at p1.  If t is less than that, then there is no intersection (i.e. p is not within
            // the 'bounds' of the segment)
            if (t > -kEpsilon)
            {
                // intersects at 1st segment vertex
                t = 0.0;
            }
            // set our 'intersection' point to p1.
            qx = p1x;
            qy = p1y;
            // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
            // we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)).
        }
        else if (t > (1.0 - kEpsilon))
        {
            // intersects at or to the "right" of second segment vertex (p2x, p2y).  If t is approximately 1.0, then
            // intersection is at p2.  If t is greater than that, then there is no intersection (i.e. p is not within
            // the 'bounds' of the segment)
            if (t < (1.0 + kEpsilon))
            {
                // intersects at 2nd segment vertex
                t = 1.0;
            }
            // set our 'intersection' point to p2.
            qx = p2x;
            qy = p2y;
            // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
            // we were doing PointLineDistanceSquared, then qx would be (p1x + (t * dx)) and qy would be (p1y + (t * dy)).
        }
        else
        {
            // The projection of the point to the point on the segment that is perpendicular succeeded and the point
            // is 'within' the bounds of the segment.  Set the intersection point as that projected point.
            qx = p1x + (t * dx);
            qy = p1y + (t * dy);
        }
        // return the squared distance from p to the intersection point.  Note that we return the squared distance
        // as an optimization because many times you just need to compare relative distances and the squared values
        // works fine for that.  If you want the ACTUAL distance, just take the square root of this value.
        double dpqx = px - qx;
        double dpqy = py - qy;
        return ((dpqx * dpqx) + (dpqy * dpqy));
    }
}
devnullicus
sumber
6

Saya berasumsi Anda ingin menemukan terpendekjarak antara titik dan segmen garis; untuk melakukan ini, Anda perlu menemukan garis (lineA) yang tegak lurus dengan segmen garis Anda (lineB) yang melewati titik Anda, menentukan persimpangan antara garis itu (lineA) dan garis Anda yang melewati segmen garis Anda (lineB) ; jika titik itu berada di antara dua titik segmen garis Anda, maka jaraknya adalah jarak antara titik Anda dan titik yang baru saja Anda temukan yang merupakan perpotongan garis A dan garis B; jika titik tersebut tidak berada di antara dua titik segmen garis Anda, Anda perlu mendapatkan jarak antara titik Anda dan yang lebih dekat dari dua ujung segmen garis; ini dapat dilakukan dengan mudah dengan mengambil jarak kuadrat (untuk menghindari akar kuadrat) antara titik dan dua titik segmen garis; mana yang lebih dekat, ambil akar kuadrat dari yang itu.

Paul Sonier
sumber
6

Implementasi C ++ / JavaScript Grumdrig sangat berguna bagi saya, jadi saya telah menyediakan port langsung Python yang saya gunakan. Kode lengkapnya ada di sini .

class Point(object):
  def __init__(self, x, y):
    self.x = float(x)
    self.y = float(y)

def square(x):
  return x * x

def distance_squared(v, w):
  return square(v.x - w.x) + square(v.y - w.y)

def distance_point_segment_squared(p, v, w):
  # Segment length squared, |w-v|^2
  d2 = distance_squared(v, w) 
  if d2 == 0: 
    # v == w, return distance to v
    return distance_squared(p, v)
  # Consider the line extending the segment, parameterized as v + t (w - v).
  # We find projection of point p onto the line.
  # It falls where t = [(p-v) . (w-v)] / |w-v|^2
  t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / d2;
  if t < 0:
    # Beyond v end of the segment
    return distance_squared(p, v)
  elif t > 1.0:
    # Beyond w end of the segment
    return distance_squared(p, w)
  else:
    # Projection falls on the segment.
    proj = Point(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y))
    # print proj.x, proj.y
    return distance_squared(p, proj)
wol
sumber
5

Kode Matlab, dengan built-in "self test" jika mereka memanggil fungsi tanpa argumen:

function r = distPointToLineSegment( xy0, xy1, xyP )
% r = distPointToLineSegment( xy0, xy1, xyP )

if( nargin < 3 )
    selfTest();
    r=0;
else
    vx = xy0(1)-xyP(1);
    vy = xy0(2)-xyP(2);
    ux = xy1(1)-xy0(1);
    uy = xy1(2)-xy0(2);
    lenSqr= (ux*ux+uy*uy);
    detP= -vx*ux + -vy*uy;

    if( detP < 0 )
        r = norm(xy0-xyP,2);
    elseif( detP > lenSqr )
        r = norm(xy1-xyP,2);
    else
        r = abs(ux*vy-uy*vx)/sqrt(lenSqr);
    end
end


    function selfTest()
        %#ok<*NASGU>
        disp(['invalid args, distPointToLineSegment running (recursive)  self-test...']);

        ptA = [1;1]; ptB = [-1;-1];
        ptC = [1/2;1/2];  % on the line
        ptD = [-2;-1.5];  % too far from line segment
        ptE = [1/2;0];    % should be same as perpendicular distance to line
        ptF = [1.5;1.5];      % along the A-B but outside of the segment

        distCtoAB = distPointToLineSegment(ptA,ptB,ptC)
        distDtoAB = distPointToLineSegment(ptA,ptB,ptD)
        distEtoAB = distPointToLineSegment(ptA,ptB,ptE)
        distFtoAB = distPointToLineSegment(ptA,ptB,ptF)
        figure(1); clf;
        circle = @(x, y, r, c) rectangle('Position', [x-r, y-r, 2*r, 2*r], ...
            'Curvature', [1 1], 'EdgeColor', c);
        plot([ptA(1) ptB(1)],[ptA(2) ptB(2)],'r-x'); hold on;
        plot(ptC(1),ptC(2),'b+'); circle(ptC(1),ptC(2), 0.5e-1, 'b');
        plot(ptD(1),ptD(2),'g+'); circle(ptD(1),ptD(2), distDtoAB, 'g');
        plot(ptE(1),ptE(2),'k+'); circle(ptE(1),ptE(2), distEtoAB, 'k');
        plot(ptF(1),ptF(2),'m+'); circle(ptF(1),ptF(2), distFtoAB, 'm');
        hold off;
        axis([-3 3 -3 3]); axis equal;
    end

end
peter karasev
sumber
Terima kasih, kode Matlab ini memang menghitung jarak terpendek ke garis SEGMENT dan bukan jarak ke garis tak terbatas di mana segmen berada.
Rudolf Meijering
4

Dan sekarang solusi saya juga ...... (Javascript)

Ini sangat cepat karena saya mencoba menghindari fungsi Math.pow.

Seperti yang Anda lihat, pada akhir fungsi saya memiliki jarak garis.

kode berasal dari lib http://www.draw2d.org/graphiti/jsdoc/#!/example

/**
 * Static util function to determine is a point(px,py) on the line(x1,y1,x2,y2)
 * A simple hit test.
 * 
 * @return {boolean}
 * @static
 * @private
 * @param {Number} coronaWidth the accepted corona for the hit test
 * @param {Number} X1 x coordinate of the start point of the line
 * @param {Number} Y1 y coordinate of the start point of the line
 * @param {Number} X2 x coordinate of the end point of the line
 * @param {Number} Y2 y coordinate of the end point of the line
 * @param {Number} px x coordinate of the point to test
 * @param {Number} py y coordinate of the point to test
 **/
graphiti.shape.basic.Line.hit= function( coronaWidth, X1, Y1,  X2,  Y2, px, py)
{
  // Adjust vectors relative to X1,Y1
  // X2,Y2 becomes relative vector from X1,Y1 to end of segment
  X2 -= X1;
  Y2 -= Y1;
  // px,py becomes relative vector from X1,Y1 to test point
  px -= X1;
  py -= Y1;
  var dotprod = px * X2 + py * Y2;
  var projlenSq;
  if (dotprod <= 0.0) {
      // px,py is on the side of X1,Y1 away from X2,Y2
      // distance to segment is length of px,py vector
      // "length of its (clipped) projection" is now 0.0
      projlenSq = 0.0;
  } else {
      // switch to backwards vectors relative to X2,Y2
      // X2,Y2 are already the negative of X1,Y1=>X2,Y2
      // to get px,py to be the negative of px,py=>X2,Y2
      // the dot product of two negated vectors is the same
      // as the dot product of the two normal vectors
      px = X2 - px;
      py = Y2 - py;
      dotprod = px * X2 + py * Y2;
      if (dotprod <= 0.0) {
          // px,py is on the side of X2,Y2 away from X1,Y1
          // distance to segment is length of (backwards) px,py vector
          // "length of its (clipped) projection" is now 0.0
          projlenSq = 0.0;
      } else {
          // px,py is between X1,Y1 and X2,Y2
          // dotprod is the length of the px,py vector
          // projected on the X2,Y2=>X1,Y1 vector times the
          // length of the X2,Y2=>X1,Y1 vector
          projlenSq = dotprod * dotprod / (X2 * X2 + Y2 * Y2);
      }
  }
    // Distance to line is now the length of the relative point
    // vector minus the length of its projection onto the line
    // (which is zero if the projection falls outside the range
    //  of the line segment).
    var lenSq = px * px + py * py - projlenSq;
    if (lenSq < 0) {
        lenSq = 0;
    }
    return Math.sqrt(lenSq)<coronaWidth;
};
pengguna1397870
sumber
4

dikodekan dalam t-sql

intinya adalah (@px, @py) dan segmen baris berjalan dari (@ax, @ay) ke (@bx, @by)

create function fn_sqr (@NumberToSquare decimal(18,10)) 
returns decimal(18,10)
as 
begin
    declare @Result decimal(18,10)
    set @Result = @NumberToSquare * @NumberToSquare
    return @Result
end
go

create function fn_Distance(@ax decimal (18,10) , @ay decimal (18,10), @bx decimal(18,10),  @by decimal(18,10)) 
returns decimal(18,10)
as
begin
    declare @Result decimal(18,10)
    set @Result = (select dbo.fn_sqr(@ax - @bx) + dbo.fn_sqr(@ay - @by) )
    return @Result
end
go

create function fn_DistanceToSegmentSquared(@px decimal(18,10), @py decimal(18,10), @ax decimal(18,10), @ay decimal(18,10), @bx decimal(18,10), @by decimal(18,10)) 
returns decimal(18,10)
as 
begin
    declare @l2 decimal(18,10)
    set @l2 = (select dbo.fn_Distance(@ax, @ay, @bx, @by))
    if @l2 = 0
        return dbo.fn_Distance(@px, @py, @ax, @ay)
    declare @t decimal(18,10)
    set @t = ((@px - @ax) * (@bx - @ax) + (@py - @ay) * (@by - @ay)) / @l2
    if (@t < 0) 
        return dbo.fn_Distance(@px, @py, @ax, @ay);
    if (@t > 1) 
        return dbo.fn_Distance(@px, @py, @bx, @by);
    return dbo.fn_Distance(@px, @py,  @ax + @t * (@bx - @ax),  @ay + @t * (@by - @ay))
end
go

create function fn_DistanceToSegment(@px decimal(18,10), @py decimal(18,10), @ax decimal(18,10), @ay decimal(18,10), @bx decimal(18,10), @by decimal(18,10)) 
returns decimal(18,10)
as 
begin
    return sqrt(dbo.fn_DistanceToSegmentSquared(@px, @py , @ax , @ay , @bx , @by ))
end
go

--example execution for distance from a point at (6,1) to line segment that runs from (4,2) to (2,1)
select dbo.fn_DistanceToSegment(6, 1, 4, 2, 2, 1) 
--result = 2.2360679775

--example execution for distance from a point at (-3,-2) to line segment that runs from (0,-2) to (-2,1)
select dbo.fn_DistanceToSegment(-3, -2, 0, -2, -2, 1) 
--result = 2.4961508830

--example execution for distance from a point at (0,-2) to line segment that runs from (0,-2) to (-2,1)
select dbo.fn_DistanceToSegment(0,-2, 0, -2, -2, 1) 
--result = 0.0000000000
merampok mcnicol
sumber
4

Sepertinya hampir semua orang di StackOverflow telah menyumbangkan jawaban (23 jawaban sejauh ini), jadi inilah kontribusi saya untuk C #. Ini sebagian besar didasarkan pada jawaban oleh M. Katz, yang pada gilirannya didasarkan pada jawaban oleh Grumdrig.

   public struct MyVector
   {
      private readonly double _x, _y;


      // Constructor
      public MyVector(double x, double y)
      {
         _x = x;
         _y = y;
      }


      // Distance from this point to another point, squared
      private double DistanceSquared(MyVector otherPoint)
      {
         double dx = otherPoint._x - this._x;
         double dy = otherPoint._y - this._y;
         return dx * dx + dy * dy;
      }


      // Find the distance from this point to a line segment (which is not the same as from this 
      //  point to anywhere on an infinite line). Also returns the closest point.
      public double DistanceToLineSegment(MyVector lineSegmentPoint1, MyVector lineSegmentPoint2,
                                          out MyVector closestPoint)
      {
         return Math.Sqrt(DistanceToLineSegmentSquared(lineSegmentPoint1, lineSegmentPoint2, 
                          out closestPoint));
      }


      // Same as above, but avoid using Sqrt(), saves a new nanoseconds in cases where you only want 
      //  to compare several distances to find the smallest or largest, but don't need the distance
      public double DistanceToLineSegmentSquared(MyVector lineSegmentPoint1, 
                                              MyVector lineSegmentPoint2, out MyVector closestPoint)
      {
         // Compute length of line segment (squared) and handle special case of coincident points
         double segmentLengthSquared = lineSegmentPoint1.DistanceSquared(lineSegmentPoint2);
         if (segmentLengthSquared < 1E-7f)  // Arbitrary "close enough for government work" value
         {
            closestPoint = lineSegmentPoint1;
            return this.DistanceSquared(closestPoint);
         }

         // Use the magic formula to compute the "projection" of this point on the infinite line
         MyVector lineSegment = lineSegmentPoint2 - lineSegmentPoint1;
         double t = (this - lineSegmentPoint1).DotProduct(lineSegment) / segmentLengthSquared;

         // Handle the two cases where the projection is not on the line segment, and the case where 
         //  the projection is on the segment
         if (t <= 0)
            closestPoint = lineSegmentPoint1;
         else if (t >= 1)
            closestPoint = lineSegmentPoint2;
         else 
            closestPoint = lineSegmentPoint1 + (lineSegment * t);
         return this.DistanceSquared(closestPoint);
      }


      public double DotProduct(MyVector otherVector)
      {
         return this._x * otherVector._x + this._y * otherVector._y;
      }

      public static MyVector operator +(MyVector leftVector, MyVector rightVector)
      {
         return new MyVector(leftVector._x + rightVector._x, leftVector._y + rightVector._y);
      }

      public static MyVector operator -(MyVector leftVector, MyVector rightVector)
      {
         return new MyVector(leftVector._x - rightVector._x, leftVector._y - rightVector._y);
      }

      public static MyVector operator *(MyVector aVector, double aScalar)
      {
         return new MyVector(aVector._x * aScalar, aVector._y * aScalar);
      }

      // Added using ReSharper due to CodeAnalysis nagging

      public bool Equals(MyVector other)
      {
         return _x.Equals(other._x) && _y.Equals(other._y);
      }

      public override bool Equals(object obj)
      {
         if (ReferenceEquals(null, obj)) return false;
         return obj is MyVector && Equals((MyVector) obj);
      }

      public override int GetHashCode()
      {
         unchecked
         {
            return (_x.GetHashCode()*397) ^ _y.GetHashCode();
         }
      }

      public static bool operator ==(MyVector left, MyVector right)
      {
         return left.Equals(right);
      }

      public static bool operator !=(MyVector left, MyVector right)
      {
         return !left.Equals(right);
      }
   }

Dan inilah program pengujian kecil.

   public static class JustTesting
   {
      public static void Main()
      {
         Stopwatch stopwatch = new Stopwatch();
         stopwatch.Start();

         for (int i = 0; i < 10000000; i++)
         {
            TestIt(1, 0, 0, 0, 1, 1, 0.70710678118654757);
            TestIt(5, 4, 0, 0, 20, 10, 1.3416407864998738);
            TestIt(30, 15, 0, 0, 20, 10, 11.180339887498949);
            TestIt(-30, 15, 0, 0, 20, 10, 33.541019662496844);
            TestIt(5, 1, 0, 0, 10, 0, 1.0);
            TestIt(1, 5, 0, 0, 0, 10, 1.0);
         }

         stopwatch.Stop();
         TimeSpan timeSpan = stopwatch.Elapsed;
      }


      private static void TestIt(float aPointX, float aPointY, 
                                 float lineSegmentPoint1X, float lineSegmentPoint1Y, 
                                 float lineSegmentPoint2X, float lineSegmentPoint2Y, 
                                 double expectedAnswer)
      {
         // Katz
         double d1 = DistanceFromPointToLineSegment(new MyVector(aPointX, aPointY), 
                                              new MyVector(lineSegmentPoint1X, lineSegmentPoint1Y), 
                                              new MyVector(lineSegmentPoint2X, lineSegmentPoint2Y));
         Debug.Assert(d1 == expectedAnswer);

         /*
         // Katz using squared distance
         double d2 = DistanceFromPointToLineSegmentSquared(new MyVector(aPointX, aPointY), 
                                              new MyVector(lineSegmentPoint1X, lineSegmentPoint1Y), 
                                              new MyVector(lineSegmentPoint2X, lineSegmentPoint2Y));
         Debug.Assert(Math.Abs(d2 - expectedAnswer * expectedAnswer) < 1E-7f);
          */

         /*
         // Matti (optimized)
         double d3 = FloatVector.DistanceToLineSegment(new PointF(aPointX, aPointY), 
                                                new PointF(lineSegmentPoint1X, lineSegmentPoint1Y), 
                                                new PointF(lineSegmentPoint2X, lineSegmentPoint2Y));
         Debug.Assert(Math.Abs(d3 - expectedAnswer) < 1E-7f);
          */
      }

      private static double DistanceFromPointToLineSegment(MyVector aPoint, 
                                             MyVector lineSegmentPoint1, MyVector lineSegmentPoint2)
      {
         MyVector closestPoint;  // Not used
         return aPoint.DistanceToLineSegment(lineSegmentPoint1, lineSegmentPoint2, 
                                             out closestPoint);
      }

      private static double DistanceFromPointToLineSegmentSquared(MyVector aPoint, 
                                             MyVector lineSegmentPoint1, MyVector lineSegmentPoint2)
      {
         MyVector closestPoint;  // Not used
         return aPoint.DistanceToLineSegmentSquared(lineSegmentPoint1, lineSegmentPoint2, 
                                                    out closestPoint);
      }
   }

Seperti yang Anda lihat, saya mencoba mengukur perbedaan antara menggunakan versi yang menghindari metode Sqrt () dan versi normal. Tes saya menunjukkan Anda mungkin dapat menghemat sekitar 2,5%, tapi saya bahkan tidak yakin akan hal itu - variasi dalam berbagai uji coba memiliki urutan yang sama besarnya. Saya juga mencoba mengukur versi yang diposting oleh Matti (ditambah optimasi yang jelas), dan versi itu tampaknya sekitar 4% lebih lambat daripada versi berdasarkan kode Katz / Grumdrig.

Sunting: Kebetulan, saya juga mencoba mengukur metode yang menemukan jarak ke garis tak terbatas (bukan segmen garis) menggunakan produk silang (dan Sqrt ()), dan ini sekitar 32% lebih cepat.

RenniePet
sumber
3

Ini adalah versi C ++ devnullicus yang dikonversi ke C #. Untuk implementasi saya, saya perlu tahu titik persimpangan dan menemukan solusinya untuk bekerja dengan baik.

public static bool PointSegmentDistanceSquared(PointF point, PointF lineStart, PointF lineEnd, out double distance, out PointF intersectPoint)
{
    const double kMinSegmentLenSquared = 0.00000001; // adjust to suit.  If you use float, you'll probably want something like 0.000001f
    const double kEpsilon = 1.0E-14; // adjust to suit.  If you use floats, you'll probably want something like 1E-7f
    double dX = lineEnd.X - lineStart.X;
    double dY = lineEnd.Y - lineStart.Y;
    double dp1X = point.X - lineStart.X;
    double dp1Y = point.Y - lineStart.Y;
    double segLenSquared = (dX * dX) + (dY * dY);
    double t = 0.0;

    if (segLenSquared >= -kMinSegmentLenSquared && segLenSquared <= kMinSegmentLenSquared)
    {
        // segment is a point.
        intersectPoint = lineStart;
        t = 0.0;
        distance = ((dp1X * dp1X) + (dp1Y * dp1Y));
    }
    else
    {
        // Project a line from p to the segment [p1,p2].  By considering the line
        // extending the segment, parameterized as p1 + (t * (p2 - p1)),
        // we find projection of point p onto the line. 
        // It falls where t = [(p - p1) . (p2 - p1)] / |p2 - p1|^2
        t = ((dp1X * dX) + (dp1Y * dY)) / segLenSquared;
        if (t < kEpsilon)
        {
            // intersects at or to the "left" of first segment vertex (lineStart.X, lineStart.Y).  If t is approximately 0.0, then
            // intersection is at p1.  If t is less than that, then there is no intersection (i.e. p is not within
            // the 'bounds' of the segment)
            if (t > -kEpsilon)
            {
                // intersects at 1st segment vertex
                t = 0.0;
            }
            // set our 'intersection' point to p1.
            intersectPoint = lineStart;
            // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
            // we were doing PointLineDistanceSquared, then intersectPoint.X would be (lineStart.X + (t * dx)) and intersectPoint.Y would be (lineStart.Y + (t * dy)).
        }
        else if (t > (1.0 - kEpsilon))
        {
            // intersects at or to the "right" of second segment vertex (lineEnd.X, lineEnd.Y).  If t is approximately 1.0, then
            // intersection is at p2.  If t is greater than that, then there is no intersection (i.e. p is not within
            // the 'bounds' of the segment)
            if (t < (1.0 + kEpsilon))
            {
                // intersects at 2nd segment vertex
                t = 1.0;
            }
            // set our 'intersection' point to p2.
            intersectPoint = lineEnd;
            // Note: If you wanted the ACTUAL intersection point of where the projected lines would intersect if
            // we were doing PointLineDistanceSquared, then intersectPoint.X would be (lineStart.X + (t * dx)) and intersectPoint.Y would be (lineStart.Y + (t * dy)).
        }
        else
        {
            // The projection of the point to the point on the segment that is perpendicular succeeded and the point
            // is 'within' the bounds of the segment.  Set the intersection point as that projected point.
            intersectPoint = new PointF((float)(lineStart.X + (t * dX)), (float)(lineStart.Y + (t * dY)));
        }
        // return the squared distance from p to the intersection point.  Note that we return the squared distance
        // as an optimization because many times you just need to compare relative distances and the squared values
        // works fine for that.  If you want the ACTUAL distance, just take the square root of this value.
        double dpqX = point.X - intersectPoint.X;
        double dpqY = point.Y - intersectPoint.Y;

        distance = ((dpqX * dpqX) + (dpqY * dpqY));
    }

    return true;
}
headkaze
sumber
Bekerja seperti pesona !! Menghemat saya berjam-jam. Terima kasih banyak!!
Steve Johnson
3

Ini dia menggunakan Swift

    /* Distance from a point (p1) to line l1 l2 */
func distanceFromPoint(p: CGPoint, toLineSegment l1: CGPoint, and l2: CGPoint) -> CGFloat {
    let A = p.x - l1.x
    let B = p.y - l1.y
    let C = l2.x - l1.x
    let D = l2.y - l1.y

    let dot = A * C + B * D
    let len_sq = C * C + D * D
    let param = dot / len_sq

    var xx, yy: CGFloat

    if param < 0 || (l1.x == l2.x && l1.y == l2.y) {
        xx = l1.x
        yy = l1.y
    } else if param > 1 {
        xx = l2.x
        yy = l2.y
    } else {
        xx = l1.x + param * C
        yy = l1.y + param * D
    }

    let dx = p.x - xx
    let dy = p.y - yy

    return sqrt(dx * dx + dy * dy)
}
OzRunways
sumber
3

C #

Diadaptasi dari @Grumdrig

public static double MinimumDistanceToLineSegment(this Point p,
    Line line)
{
    var v = line.StartPoint;
    var w = line.EndPoint;

    double lengthSquared = DistanceSquared(v, w);

    if (lengthSquared == 0.0)
        return Distance(p, v);

    double t = Math.Max(0, Math.Min(1, DotProduct(p - v, w - v) / lengthSquared));
    var projection = v + t * (w - v);

    return Distance(p, projection);
}

public static double Distance(Point a, Point b)
{
    return Math.Sqrt(DistanceSquared(a, b));
}

public static double DistanceSquared(Point a, Point b)
{
    var d = a - b;
    return DotProduct(d, d);
}

public static double DotProduct(Point a, Point b)
{
    return (a.X * b.X) + (a.Y * b.Y);
}
Mateen Ulhaq
sumber
Mencoba kode ini, sepertinya tidak berfungsi dengan benar. Tampaknya mendapatkan jarak yang salah beberapa kali.
WDUK
3

Solusi 2D dan 3D

Pertimbangkan perubahan basis sedemikian rupa sehingga segmen garis menjadi (0, 0, 0)-(d, 0, 0)dan intinya (u, v, 0). Jarak terpendek terjadi di pesawat itu dan diberikan oleh

    u ≤ 0 -> d(A, C)
0 ≤ u ≤ d -> |v|
d ≤ u     -> d(B, C)

(jarak ke salah satu titik akhir atau ke garis pendukung, tergantung pada proyeksi ke garis. Lokus iso-jarak terbuat dari dua setengah lingkaran dan dua segmen garis.)

masukkan deskripsi gambar di sini

Dalam ungkapan di atas, d adalah panjang segmen AB, dan u, v masing-masing adalah produk skalar dan (modulus dari) produk silang AB / d (vektor satuan ke arah AB) dan AC. Karena itu secara vectorially,

AB.AC ≤ 0             -> |AC|
    0 ≤ AB.AC ≤ AB²   -> |ABxAC|/|AB|
          AB² ≤ AB.AC -> |BC|
Yves Daoust
sumber
2

lihat Matlab GEOMETRY toolbox di situs web berikut: http://people.sc.fsu.edu/~jburkardt/m_src/geometry/geometry.html

ctrl + f dan ketik "segmen" untuk menemukan fungsi terkait segmen garis. fungsi "segment_point_dist_2d.m" dan "segment_point_dist_3d.m" adalah yang Anda butuhkan.

Kode GEOMETRI tersedia dalam versi C dan versi C ++ dan versi FORTRAN77 dan versi FORTRAN90 dan versi MATLAB.

Bunga bakung
sumber
2

Versi AutoHotkeys berdasarkan Javascript Joshua:

plDist(x, y, x1, y1, x2, y2) {
    A:= x - x1
    B:= y - y1
    C:= x2 - x1
    D:= y2 - y1

    dot:= A*C + B*D
    sqLen:= C*C + D*D
    param:= dot / sqLen

    if (param < 0 || ((x1 = x2) && (y1 = y2))) {
        xx:= x1
        yy:= y1
    } else if (param > 1) {
        xx:= x2
        yy:= y2
    } else {
        xx:= x1 + param*C
        yy:= y1 + param*D
    }

    dx:= x - xx
    dy:= y - yy

    return sqrt(dx*dx + dy*dy)
}
Chronocide
sumber
2

Tidak melihat implementasi Java di sini, jadi saya menerjemahkan fungsi Javascript dari jawaban yang diterima ke kode Java:

static double sqr(double x) {
    return x * x;
}
static double dist2(DoublePoint v, DoublePoint w) {
    return sqr(v.x - w.x) + sqr(v.y - w.y);
}
static double distToSegmentSquared(DoublePoint p, DoublePoint v, DoublePoint w) {
    double l2 = dist2(v, w);
    if (l2 == 0) return dist2(p, v);
    double t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
    if (t < 0) return dist2(p, v);
    if (t > 1) return dist2(p, w);
    return dist2(p, new DoublePoint(
            v.x + t * (w.x - v.x),
            v.y + t * (w.y - v.y)
    ));
}
static double distToSegment(DoublePoint p, DoublePoint v, DoublePoint w) {
    return Math.sqrt(distToSegmentSquared(p, v, w));
}
static class DoublePoint {
    public double x;
    public double y;

    public DoublePoint(double x, double y) {
        this.x = x;
        this.y = y;
    }
}
Yury Fedorov
sumber
2

Versi WPF:

public class LineSegment
{
    private readonly Vector _offset;
    private readonly Vector _vector;

    public LineSegment(Point start, Point end)
    {
        _offset = (Vector)start;
        _vector = (Vector)(end - _offset);
    }

    public double DistanceTo(Point pt)
    {
        var v = (Vector)pt - _offset;

        // first, find a projection point on the segment in parametric form (0..1)
        var p = (v * _vector) / _vector.LengthSquared;

        // and limit it so it lays inside the segment
        p = Math.Min(Math.Max(p, 0), 1);

        // now, find the distance from that point to our point
        return (_vector * p - v).Length;
    }
}
torvin
sumber
1

Inilah kode yang akhirnya saya tulis. Kode ini mengasumsikan bahwa suatu titik didefinisikan dalam bentuk {x:5, y:7}. Perhatikan bahwa ini bukan cara yang paling efisien mutlak, tetapi ini adalah kode paling sederhana dan paling mudah dipahami yang bisa saya buat.

// a, b, and c in the code below are all points

function distance(a, b)
{
    var dx = a.x - b.x;
    var dy = a.y - b.y;
    return Math.sqrt(dx*dx + dy*dy);
}

function Segment(a, b)
{
    var ab = {
        x: b.x - a.x,
        y: b.y - a.y
    };
    var length = distance(a, b);

    function cross(c) {
        return ab.x * (c.y-a.y) - ab.y * (c.x-a.x);
    };

    this.distanceFrom = function(c) {
        return Math.min(distance(a,c),
                        distance(b,c),
                        Math.abs(cross(c) / length));
    };
}
Eli Courtwright
sumber
1
Kode ini memiliki bug. Suatu titik di dekat garis di mana segmen terletak, tetapi jauh dari salah satu ujung segmen, akan dinilai salah berada di dekat segmen.
Grumdrig
Menarik, saya akan melihat ini saat berikutnya saya mengerjakan basis kode ini untuk mengonfirmasi pernyataan Anda. Terima kasih atas tipnya.
Eli Courtwright
1

Fungsi di atas tidak berfungsi pada garis vertikal. Berikut adalah fungsi yang berfungsi dengan baik! Baris dengan poin p1, p2. dan CheckPoint adalah p;

public float DistanceOfPointToLine2(PointF p1, PointF p2, PointF p)
{
  //          (y1-y2)x + (x2-x1)y + (x1y2-x2y1)
  //d(P,L) = --------------------------------
  //         sqrt( (x2-x1)pow2 + (y2-y1)pow2 )

  double ch = (p1.Y - p2.Y) * p.X + (p2.X - p1.X) * p.Y + (p1.X * p2.Y - p2.X * p1.Y);
  double del = Math.Sqrt(Math.Pow(p2.X - p1.X, 2) + Math.Pow(p2.Y - p1.Y, 2));
  double d = ch / del;
  return (float)d;
}
Dmitry
sumber
Tidak menjawab pertanyaan. Ini hanya berfungsi untuk garis (yang meluas tanpa batas dalam ruang) bukan segmen garis (yang memiliki panjang terbatas).
Trinidad
"fungsi di atas" adalah referensi yang ambigu. (Membuat saya jengkel karena terkadang jawaban ini ditampilkan di bawah jawaban saya.)
RenniePet
1

Berikut hal yang sama dengan jawaban C ++ tetapi diport ke pascal. Urutan parameter titik telah berubah agar sesuai dengan kode saya tetapi merupakan hal yang sama.

function Dot(const p1, p2: PointF): double;
begin
  Result := p1.x * p2.x + p1.y * p2.y;
end;
function SubPoint(const p1, p2: PointF): PointF;
begin
  result.x := p1.x - p2.x;
  result.y := p1.y - p2.y;
end;

function ShortestDistance2(const p,v,w : PointF) : double;
var
  l2,t : double;
  projection,tt: PointF;
begin
  // Return minimum distance between line segment vw and point p
  //l2 := length_squared(v, w);  // i.e. |w-v|^2 -  avoid a sqrt
  l2 := Distance(v,w);
  l2 := MPower(l2,2);
  if (l2 = 0.0) then begin
    result:= Distance(p, v);   // v == w case
    exit;
  end;
  // Consider the line extending the segment, parameterized as v + t (w - v).
  // We find projection of point p onto the line.
  // It falls where t = [(p-v) . (w-v)] / |w-v|^2
  t := Dot(SubPoint(p,v),SubPoint(w,v)) / l2;
  if (t < 0.0) then begin
    result := Distance(p, v);       // Beyond the 'v' end of the segment
    exit;
  end
  else if (t > 1.0) then begin
    result := Distance(p, w);  // Beyond the 'w' end of the segment
    exit;
  end;
  //projection := v + t * (w - v);  // Projection falls on the segment
  tt.x := v.x + t * (w.x - v.x);
  tt.y := v.y + t * (w.y - v.y);
  result := Distance(p, tt);
end;
pengguna1401452
sumber
Ada beberapa masalah dengan Jawaban ini: Tipe PointF tidak dideklarasikan (mungkin itu tipe standar dalam beberapa implementasi Pascal). Itu mungkin sebuah catatan x, y: dua kali lipat; akhir; 2. fungsi Distance dan MPower tidak dideklarasikan dan tidak ada penjelasan apa yang mereka lakukan (bisa kita tebak, ya). 3. Proyeksi variabel dinyatakan tetapi tidak pernah digunakan. Secara keseluruhan itu membuatnya menjadi jawaban yang agak buruk.
dummzeuch