路径跟踪算法

Question

说我有一个形状，看起来像这样：

__ __ 
|__|__| 

有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] 
] 

所有这些线连接。我怎么能确定这些特定的行（所有这些）连接，因为有其他线路没有连接。

基本上我找不出任何可以得到所有线条的东西。

如果任何人都可以在正确的方向指向我的概念或代码明智，将不胜感激。

Answer 1

一个天真的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; 
}