Array and loop management

Question

Here I have written simple program but I have little issue in managing it.

I have 6 points, for each point I want to calculate distance to other points.

code:

<?php
$a_points = array(
    array(0, -1),
    array(-2, 3),
    array(4, 0),
    array(3, 1),
    array(5, 2),
    array(0, 1),
);
$k = 0;
$a_sum_dists = array();
$sum = array();
foreach ($a_points as $i => $pt1) {
    list($x1, $y1) = $pt1;
    //$sum = 0;
    foreach ($a_points as $j => $pt2) {
        if ($j == $i) continue;
        list($x2, $y2) = $pt2;
        $sum[$k] = pow($x2- $x1, 2) + pow($y2- $y1, 2);
        $k++;
    }
    //$a_sum_dists[$i] = $sum;
}

?>

What I want:

for each point, get distance to all other points. Then print point which is at min distance. If more then one such points, print all
Now we have min distance points for each point. So now prints points which appears most frequently as a min distance. If more then one such points, print all

To get the distance, you also need to take square root there. sqrt(pow($x2- $x1, 2) + pow($y2- $y1, 2)), also I believe if you want to know the points used for specific sums a counter is not the best way. — PurkkaKoodari
– PurkkaKoodari, Commented Feb 24, 2014 at 7:53
@Pietu1998: thanks but if I skip using sqrt, even purpose of getting closest points can be preserved. If i am not wrong — user2129623
– user2129623, Commented Feb 24, 2014 at 9:50

hindmost · Accepted Answer · 2014-02-24 11:51:47Z

3

Now when you've specified algorithm in detail, I can suggest implementation for it:

$a_all_ids = array_keys($a_points);
$a_neibor_ids = array();
foreach ($a_points as $i => $pt1) {
    list($x1, $y1) = $pt1;
    $a_dists = array();
    foreach ($a_points as $j => $pt2) {
        if ($j == $i) continue;
        list($x2, $y2) = $pt2;
        $a_dists[$j] = pow($x2- $x1, 2) + pow($y2- $y1, 2);
    }
    $min_dist = min($a_dists);
    $a_neibor_ids = array_merge(
        $a_neibor_ids,
        array_keys(array_filter($a_dists, function ($v) use ($min_dist) {
            return $v == $min_dist;
        }))
        );
}

$a_counts = array_count_values($a_neibor_ids);
$max_count = max($a_counts);

$a_result_points = array_intersect_key(
    $a_points, 
    array_filter($a_counts, function ($v) use ($max_count) {
        return $v == $max_count;
    })
);

Notations:

$a_dists - distances from the current point to the rest points.
$a_neibor_ids - for each point we find its nearest point(s). $a_neibor_ids is union of all such points (including duplicates).
$a_counts - numbers of occurences of each value from $a_neibor_ids.

Demo

edited Feb 24, 2014 at 11:51

answered Feb 24, 2014 at 9:05

hindmost

7,1713 gold badges33 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

user2129623 Over a year ago

thanks a ton. Can you please add comments in code?? in ideone? little complex php DS.

hindmost Over a year ago

Added some explanation

user2129623 Over a year ago

can you please suggest name for this algo? want your opinion

hindmost Over a year ago

Something like "most frequent neighbor" or "most frequent nearest point" algo

Ja͢ck · Accepted Answer · 2014-02-24 12:28:47Z

1

A straightforward implementation of what you have described is:

$points = [
    [0, -1],
    [-2, 3],
    [4, 0],
    [3, 1],
    [5, 2],
    [0, 1],
];

$max_closest = [];

foreach ($points as $i => list($ax, $ay)) {
        $min_dist = INF;
        $dists = [];

        foreach ($points as $j => list($bx, $by)) {
                if ($i == $j) {
                        continue;
                }
                $dists[$j] = $sq_dist = ($bx - $ax) * ($bx - $ax) + ($by - $ay) * ($by - $ay);

                if ($sq_dist < $min_dist) {
                        $min_dist = $sq_dist;
                }
        }

        // select closest points
        foreach (array_keys($dists, $min_dist, true) as $key) {
                print_r($points[$key]); // print point

                // keep track of points that were closest
                if (isset($max_closest[$key])) {
                        ++$max_closest[$key];
                } else {
                        $max_closest[$key] = 1;
                }
        }
}

rsort($max_closest);

foreach (array_keys($max_closest, $max_closest[0], true) as $key) {
        print_r($points[$key]); // print point
}

answered Feb 24, 2014 at 12:28

Ja͢ck

174k39 gold badges269 silver badges317 bronze badges

1 Comment

Ja͢ck Over a year ago

@Programming_crazy Oh, you need 5.5 to use foreach($array as list($foo, $bar) :) see 3v4l.org/2Z7cj

Collectives™ on Stack Overflow

Array and loop management

2 Answers 2

4 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related