It took a few seconds to understand this. But yes, it is a problem. Thanks for bringing it to my attention.

Whether the problem occurs depends on what order the points get plotted.

Now the question is, is there a way of sorting the input to ensure that closer points get plotted before those further away (which would prevent it from occuring)? And what effect would sorting the input have upon the performance?

An alternative fix would be to use some kind of AndOr or Xor mode when plotting; or perhaps something with the alpha channel, but I haven't thought that through yet.

I'll need to think about it for a while. Have any potential fixes crossed your mind?

Now the question is, is there a way of sorting the input to ensure that closer points get plotted before those further away (which would prevent it from occuring)?

I don't think that can be solved just presorting the input.

I'll need to think about it for a while. Have any potential fixes crossed your mind?

Yes, I think that it can be done with the following changes:
1. draw circles of radius 0.5*$scale instead of $scale
2. to check if a point is inside one (or several) of the already drawn clusters you have to find with ones lay below its circle. As an approximation, you can check its center and 8 or 16 points distributed on the circle border.
3. when a point touches several clusters, select one and flood the others with its color

salva. I've fixed the problem.

The solution I've chosen is to make two passes of the data. During the first pass, I draw each of the circle at scale (as before), but then reset the central pixel back to whatever color (background or previously draw circle color) was there before. The second pass operates exactly as it did previously. Because during the second pass, all the 'circles of influence' have already been drawn once, there is no ordering issue. By unsetting the central pixel during the first pass, it will only be colored if a subsequent circle overlays it.

The effect is most clearly demonstrated by 'ficker comparing' between the two images produced when you run the modifed code below. (Performance wise, the code now processes the OPs original 300_000 point scenario, finding (for example) 127000 points in 93000 groups in under 2 minutes.)

I suggest the following commandline options as giving the clearest demonstration:

perl -slw 604750.pl -POINTS=100 -SCALER=800 -DELTA=100

What you will see is that in the image: 604790all.png, all the circles are plotted. Any circles whos central pixel is colored, are grouped. Those where the central pixel is white are not part of any group.

In the second image 694790grouped.png, just the grouped circles are draw in outline. By flicker comparing the two images, (I believe that) you can clearly see that the algorithm is now operating correctly.

I'd really value your confirmation (or otherwise)?

#! perl -slw
use strict;
use Data::Dump qw[ pp ];
use List::Util qw[ reduce sum ];
use GD;

#use constant {
#    WHITE => 16777215,
#    MinX => 10.318842, MaxX => 14.124424,
#    MinY => 21.097507, MaxY => 24.912207,
#};
#use constant {
    WHITE => 16777215,
    MinX => 0, MaxX => 1,
    MinY => 0, MaxY => 1,
};

use constant {
    SpanX => MaxX - MinX, SpanY => MaxY - MinY,
};

sub rgb2n{ unpack 'N', pack 'CCCC', 0, @_ }
sub n2rgb{ unpack 'xCCC', pack 'N', $_[0] }

our $POINTS ||= 300_000;
our $SCALER ||= 1000;
our $DELTA  ||= 20;

my @points = map [ MinX + rand( SpanX ), MinY + rand( SpanY ) ], 1 .. 
+$POINTS;

## Normalise to our grid, scale by 1000 and integerise
my @scaled = map [
    int( ( $_->[ 0 ] - MinX ) * $SCALER ),
    int( ( $_->[ 1 ] - MinY ) * $SCALER ),
], @points;

my( $sizeX, $sizeY ) = ( int( SpanX * $SCALER ), int( SpanY * $SCALER 
+) );
my $img = GD::Image->new( $sizeX, $sizeY , 1 );
$img->filledRectangle( 0, 0, $sizeX, $sizeY, rgb2n( 255, 255, 255 ) );


for my $i ( 0 .. $#scaled ) {
    my $color = $img->getPixel( @{ $scaled[ $i ] } );
    $img->filledEllipse( @{ $scaled[ $i ] }, $DELTA, $DELTA, $i );
    $img->setPixel( @{ $scaled[ $i ] }, $color );
}

my %groups;
for my $i ( 0 .. $#scaled ) {
    my $color = $img->getPixel( @{ $scaled[ $i ] } );
    if( $color != WHITE ) {
        push @{ $groups{ $color } }, $i;
    }
    else {
        $color = $i;
    }
    $img->ellipse( @{ $scaled[ $i ] }, $DELTA, $DELTA, $i );
}

printf "Found %d groups containing a total of %d points\n",
    scalar keys( %groups), sum( map scalar @$_, values %groups );

open IMG, '>:raw', '694790all.png' or die $!;
print IMG $img->png;
close IMG;
system 1, '694790all.png';

undef $img;

open OUT, '>', '694790.groups' or die $!;
for my $key ( sort { $a <=> $b } keys %groups ) {
    print OUT "[ @{ $points[ $_ ] } ]" for $key, @{ $groups{ $key } };
    print OUT "------";
}
close OUT;

$img = GD::Image->new( $sizeX, $sizeY , 1 );
$img->filledRectangle( 0, 0, $sizeX, $sizeY, rgb2n( 255, 255, 255 ) );

for my $key ( sort { $a <=> $b } keys %groups ) {
    for my $point ( $scaled[ $key ], @scaled[ @{ $groups{ $key } } ]  
+) {
        $img->setPixel( @{ $point }, $key );
        $img->ellipse( @{ $point }, $DELTA, $DELTA, $key );
    }
}

open IMG, '>:raw', '694790grouped.png' or die $!;
print IMG $img->png;
close IMG;
system 1, '694790grouped.png';
[download]

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

I think I've come up with a potential fix, though I need to sleep before I will have the tuits to code it.

The mechanism I envisage is to plot the circles larger than scale. This will cause points that are further away than the specified limit to be grouped artificially. You then replot just the points in each group, at the correct scaling, on a clean canvas using alpha-blending, to eliminate the false hits.

The first pass will reduce the problem to a few small, isolated groups making the second pass only need to deal with a few points at a time, so the slowdown shouldn't be significant.

I'll try to post a corrected solution later.