假设我有一个形状,看起来像这样:
__ __
|__|__|
有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]
]
所有这些线都连接在一起。我如何确定这些特定的线(所有的线)是连接的,因为有其他的线没有连接。
基本上我想不出什么东西能得到所有的行。
如果有人能在概念上或代码上给我指出正确的方向,我将不胜感激。
一个朴素的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;
}