in reply to Sorting by geographical proximity / clumping groups of items based on X and Y

Here's an off the wall idea, though I'm a long ways from trying to code it. Anyway, I'll start babbling and let someone else refine this, if it is worth it.

Think of it visually, like a dark room, and each complaint is a a candle. The radience from each candle dwindles as per inverse square law. If two candles are near each other, then they would have a bright area between them. All you need to do is find the brightest place and go there.

How does this work in code? I'm not sure, but a matrix might be usefull. For every complaint, increment the value of nearby geographical points inversely proportional to the distance from the complaint.

When all complaints are plotted, look for the highest value in the matrix, send a tech there.

Remove up to X complaints within a radius of Y, and recompute. repeat as necessary.

The granularity of the matrix could be adjusted as needed. The "luminosity" of complaints will also need tweaking.

Update:
here's some code, but it doesn't quite do what I want. points on the grid next to a complaint are too "hot". Maybe it should be a more linear dropoff? 

my @complaints = (
                   {
                     'complaint_id' => 'a123',
                     'x'            => '45.2',
                     'y'            => '39.7'
                   },
                   {
                     'complaint_id' => 'b456',
                     'x'            => '46.5',
                     'y'            => '41.2'
                   },
                   {
                     'complaint_id' => 'c789',
                     'x'            => '11.9',
                     'y'            => '29.8'
                   },
                   {
                     'complaint_id' => 'd863',
                     'x'            => '95.3',
                     'y'            => '17.2'
                   },
                   {
                     'complaint_id' => 'e635',
                     'x'            => '65.5',
                     'y'            => '33.3'
                   },
                 ) ;



my @highlight = (0.0,0.0);
my $highvalue = 0.0;


foreach $testpoint (@complaints) {
    for ($i = 0.0; $i < 100.0; $i += 1.0) {
        for ($j = 0.0; $j < 100.0; $j+= 1.0) {
            $dsqrd = ((($testpoint->{'x'} - $i)**2 + ($testpoint->{'y'
+} - $j)**2));
            $points[$i][$j] += $dsqrd ? (1000 / ($dsqrd * 4 * 3.14)) :
+ 0 ;
            if ($points[$i][$j] > $highvalue) {
                @highlight = ($i,$j);
                $highvalue = $points[$i][$j];
            }
        }
    }
}

print "\n\n $highlight[0], $highlight[1] has value $highvalue\n";

[download]

Replies are listed 'Best First'.
Re: Use Inverse Square Law
by Notromda (Pilgrim) on Jul 18, 2002 at 18:09 UTC
    I've played with it a little more - I made the luminosity taper off as 1/d instead of 1/4*pi*d**2. Also, I added a loop to remove visited nodes.

    Even when I re-initialize the points array to 0, it still says to run off and fix one job before going to a job with three complaints. I think this has to do with a compliant coordinate that is really close to a grid point as oppsed to others that are not so close to a line. I'm testing it with a more granular grid. First thing I realized is a 1000 by 1000 grid takes a lot more time to compute. :P

    After trying that experiment, I learned that it plucked off points one at a time... not what I was expecting.

    I'm almost sure there's a better equation for calculating this... :)

    Here's the code that provides an interesting result for the given test set: 

    
my $service_radius=15;
my $numpoints=8;
my @complaints = (
                   {
                     'complaint_id' => 'a123',
                     'x'            => '45.2',
                     'y'            => '39.7'
                   },
                   {
                     'complaint_id' => 'b456',
                     'x'            => '46.5',
                     'y'            => '41.2'
                   },
                   {
                     'complaint_id' => 'c789',
                     'x'            => '47.5',
                     'y'            => '38.8'
                   },
                   {
                     'complaint_id' => 'd863',
                     'x'            => '95.3',
                     'y'            => '17.2'
                   },
                   {
                     'complaint_id' => 'e635',
                     'x'            => '10.5',
                     'y'            => '89.3'
                   },
                   {
                     'complaint_id' => 'f635',
                     'x'            => '12.5',
                     'y'            => '1.3'
                   },
                   {
                     'complaint_id' => 'g635',
                     'x'            => '14.5',
                     'y'            => '15.3'
                   },
                   {
                     'complaint_id' => 'h635',
                     'x'            => '4.5',
                     'y'            => '20.3'
                   },
                 ) ;





while ($numpoints > 0) {

my @highlight = (0.0,0.0);
my $highvalue = 0.0;
my @points;

    for ($i = 0.0; $i < 100.0; $i += 1.0) {
        for ($j = 0.0; $j < 100.0; $j+= 1.0) {
            $points[$i][$j] = 0 ;
        }
    }
    
foreach $testpoint (@complaints) {
    next if not defined $testpoint;
    print "Plotting " . $testpoint->{'complaint_id'} . "\n";
    for ($i = 0.0; $i < 100.0; $i += 1.0) {
        for ($j = 0.0; $j < 100.0; $j+= 1.0) {
            $dsqrd = ((($testpoint->{'x'} - $i)**2 + ($testpoint->{'y'
+} - $j)**2));
            $points[$i][$j] += $dsqrd ? (1 / sqrt ($dsqrd)) : 0 ;
            if ($points[$i][$j] > $highvalue) {
                @highlight = ($i,$j);
                $highvalue = $points[$i][$j];
            }
        }
    }
}

print "$highlight[0], $highlight[1] has value $highvalue\n";

foreach $testpoint (@complaints) {
    next if not defined $testpoint;
    if (sqrt (($testpoint->{'x'} - $highlight[0])**2 + ($testpoint->{'
+y'} - $highlight[1])**2) < $service_radius) {
        print "removing " . $testpoint->{'complaint_id'} . " coordinat
+es $testpoint->{'x'} , $testpoint->{'y'}\n";
        $testpoint = undef;
        $numpoints--;
    }
}
print "\n\n";
} #end while

    [download]
[reply]
[d/l]

In Section Seekers of Perl Wisdom