note
Eimi Metamorphoumai
I suspect that there's probably a way to optimize the algorithm, but I really can't think of what it would be. However, there are numerous little changes that might help your performance a bit (though probably nothing too dramatic.
<ul>
<li> Why are <c>$points</c> and <c>$neighborEdges</c> hashrefs mapping integers (as strings) to values? It seems like it would be much more natural to make them simply arrayrefs (or just arrays). Then you wouldn't need <c>neighboorCNT</c>. So then instead of
<code>
for (my $n=1;$n<=$neighboorCNT;$n++) {
if ($neighborEdges->{$n}) {
</code>
you get
<code>
for my $n (@$neighborEdges){
</code>
and when instead of using <c>$neighborEdges->{$n}</c> you'd just use <c>$n</c>. That would save a lot of hash accesses.
<li>Very minor point, but it looks like you don't actually care about the real distance between points. Instead, you care about relative distances. So you can store the square of the distances (by not doing the sqrt) and get the same results.
<li>Since <c>Determinant</c> is called so many times, I wonder whether you'd get any improvement over rewriting it without the temporary variables.
<code>
sub Determinant {
return ($_[0]*$_[3] - $_[2]*$_[1]);
}
</code>
<li>I'd probably try rethinking SegmentIntersection. Here's an unbenchmarked (and untested) version that tries to save on some of the divisions, save calls you don't need, etc. Basically, if <c>$d</c> is zero, we don't even need <c>$n1</c> or <c>$n2</c>. For the inequalities, instead of dividing by <c>$d</c> again and again, we can multiply both sides of the inequality by <c>$d</c> (and flip the inequality if $d is less than zero).
<code>
sub SegmentIntersection {
my @points = @{$_[0]};
my @p1 = @{$points[0]}; # p1,p2 = segment 1
my @p2 = @{$points[1]};
my @p3 = @{$points[2]}; # p3,p4 = segment 2
my @p4 = @{$points[3]};
my $d = Determinant(($p2[0]-$p1[0]),($p3[0]-$p4[0]),
($p2[1]-$p1[1]),($p3[1]-$p4[1]));
if (abs($d) < $delta) {
return 0; # parallel
}
my $n1 = Determinant(($p3[0]-$p1[0]),($p3[0]-$p4[0]),
($p3[1]-$p1[1]),($p3[1]-$p4[1]));
my $n2 = Determinant(($p2[0]-$p1[0]),($p3[0]-$p1[0]),
($p2[1]-$p1[1]),($p3[1]-$p1[1]));
if ($d > 0){
return $n1 < $d && $n2 < $d && $n1 > 0 && $n2 > 0;
} else {
return $n1 > $d && $n2 > $d && $n1 < 0 && $n2 < 0;
}
}
</code>
</ul>
All small things, but they might help a little.
480481
480481