路徑跟蹤算法

說我有一個形狀，看起來像這樣：路徑跟蹤算法

__ __ 
|__|__|

有7條線段各2個單位長。

每條線都有一個（x，y）座標，用於開始和結束線段。

這些線可以被存儲在一個陣列像這樣：

[ 
    [0, 0, 2, 0], 
    [0, 0, 0, 2], 
    [0, 2, 2, 2], 
    [2, 0, 2, 2], 
    [2, 0, 4, 0], 
    [2, 2, 4, 2], 
    [4, 0, 4, 2] 
]

所有這些線連接。我怎麼能確定這些特定的行（所有這些）連接，因爲有其他線路沒有連接。

基本上我找不出任何可以得到所有線條的東西。

如果任何人都可以在正確的方向指向我的概念或代碼明智，將不勝感激。

來源

2013-03-13 maxhud

只要是明確的，「連接」在這裏意味着你可以在任何頂點開始與僅通過沿線追蹤到達任何其他頂點？ – phs 2013-03-13 00:37:06

我不太確定，但檢查每個（x，y）座標是否只存在兩次？如果這是真的，那意味着所有線路都連接在一起。 – Bdloul 2013-03-13 00:38:16

您的陣列不代表您的繪圖。在你的數組中，你的繪圖中缺少一條對角線（2,2）到（4,4）。 – angelatlarge 2013-03-13 00:38:35

一個天真的Perl版本：

use warnings; 
use strict; 

my $l = [ [0, 0, 2, 0], 
      [0, 0, 0, 2], 
      [0, 2, 2, 2], 
      [2, 0, 2, 2], 
      [2, 0, 4, 0], 
      [2, 2, 4, 2], 
      [4, 0, 4, 2] ]; 

my @f; 
Segment: 
while (my $line = shift @$l) { 
     for my $set (@f) { 
       push (@$set, $line), next Segment if is_conn($line, $set); 
     } 
     push @f, [$line]; 
} 

for my $set (@f) { 
     print "\n================\n"; 
     print join(",", @$_), "\n" for @$set; 
} 

sub is_conn { 
     my ($line, $set) = (shift, shift); 
     for my $cand (@$set) { 
       return 1 if has_same_point($cand, $line); 
     } 
     return 0; 
} 

sub has_same_point { 
     my ($l1, $l2) = @_; 
     my @p11 = ($l1->[0], $l1->[1]); 
     my @p12 = ($l1->[2], $l1->[3]); 
     my @p21 = ($l2->[0], $l2->[1]); 
     my @p22 = ($l2->[2], $l2->[3]); 
     return is_same_point(@p11, @p21) || 
       is_same_point(@p12, @p21) || 
       is_same_point(@p11, @p22) || 
       is_same_point(@p12, @p22); 
} 

sub is_same_point { 
     my ($x1, $y1, $x2, $y2) = (@_); 
     return $x1 == $x2 && $y1 == $y2; 
}

來源

2013-03-30 07:06:28 perreal

路徑跟蹤算法

回答

相關問題