查找节点之间最近的距离

Question

我想查找节点之间最近的距离。

这是我的示例数据：

节点，X，Y

 
1, 3, 5 
2, 6, 9 
3, 13, 15 
4, 16, 20 
5, 30, 50 

作为一个例子，从节点1到节点2的5最近距离我想找到从最近距离所有节点都作为节点2,3,4,5。

我该如何在Perl中实现这个功能？

这是我到目前为止有：

use strict; 
use warnings; 
use Data::Dumper; 

open(IN , "<" , "sample.txt") or die "Can't open this file."; 

my @two_dimentional_array; 
while (my $line=<IN>) 
{ 
    my @arr_line=split (" *, *" , $line); 
     my @one_dimentional_array; 
     push @one_dimentional_array , @arr_line; 
     push @two_dimentional_array, [@arr_line]; 
} 

for(my $i=0 ; $i<=$#two_dimentional_array ; $i++) 
{ 
    my ($n_1 , $X_1 , $y_1)=@{$two_dimentional_array[$i]}; 
    for (my $j=0 ; $j<=$#two_dimentional_array ; $j++) 
    { 
     my ($n_2 , $X_2 , $y_2)=@{$two_dimentional_array[$j]}; 

     chomp($y_1); 
     chomp($y_2); 
     if($n_1 != $n_2) 
     { 
      my $distance=sqrt(($X_2-$X_1)**2 + ($y_2-$y_1)**2); 
      print "Distance ".$distance." from node ".$n_1." to node ".$n_2."\n"; 
     } 
    } 
} 
#print Dumper(\@two_dimentional_array); 

Answer 1

#!/usr/bin/perl 

use strict; 
use warnings; 

my (@data, @temp, @result); 

sub calc { 
    my ($a, $b) = @_; 
    my $dat = 0; 
    $dat += ($a->[$_] - $b->[$_]) ** 2 for (1,2); 
    return sqrt $dat; 
} 

while (<DATA>) { 
    push @data, [split /,?\s+/]; 
} 

for my $x (@data) { 
    for my $y (@data) { 
     push @temp, [calc($x, $y), $x, $y] if ($x->[0] > $y->[0]); 
    } 
} 

@result = sort { $a->[0] <=> $b->[0]; } @temp; 
printf "%-18s => [%s], [%s]\n", $_->[0], 
    join(', ', @{$_->[1]}), join(', ', @{$_->[2]}) for @result; 

__DATA__ 
1, 3, 5 
2, 6, 9 
3, 13, 15 
4, 16, 20 
5, 30, 50 

输出：

5     => [2, 6, 9], [1, 3, 5] 
5.8309518948453 => [4, 16, 20], [3, 13, 15] 
9.21954445729289 => [3, 13, 15], [2, 6, 9] 
14.142135623731 => [3, 13, 15], [1, 3, 5] 
14.8660687473185 => [4, 16, 20], [2, 6, 9] 
19.8494332412792 => [4, 16, 20], [1, 3, 5] 
33.1058907144937 => [5, 30, 50], [4, 16, 20] 
38.9101529166874 => [5, 30, 50], [3, 13, 15] 
47.5078940808788 => [5, 30, 50], [2, 6, 9] 
52.4785670536077 => [5, 30, 50], [1, 3, 5] 

Answer 2

该代码会发现第一对是最小距离分开。

use strict; 
use warnings; 

# @data contains (node number, x, y) from the file 
# 
my @data; 

open my $fh, '<', 'sample.data' or die $!; 

while (<$fh>) { 
    my @node = /\d+/g; 
    push @data, \@node if @node; 
} 

# @min contains (first node number, second node number, distance) 
# for the most recently-found minimum distance 
# 
my @min; 

for my $node1 (0 .. $#data-1) { 
    for my $node2 ($node1+1 .. $#data-1) { 
    my $dist; 
    $dist += ($data[$node2][$_] - $data[$node1][$_]) ** 2 for 1, 2; 
    $dist = sqrt $dist; 
    @min = ($data[$node1][0], $data[$node2][0], $dist) unless @min and $min[2] <= $dist; 
    } 
} 

printf "%d to %d = %f\n", @min; 

输出

1 to 2 = 5.000000