PHP: как сгруппировать близкие по значению элементы массива?

Question

[Андрей Енькин]

Есть массив вида:

Array
(
    [0] => Array
        (
            [posY] => 5
            [posX] => 48.75
            [id] => 36
        )

    [1] => Array
        (
            [posY] => 5
            [posX] => 52.5
            [id] => 35
        )

    [2] => Array
        (
            [posY] => 5.5
            [posX] => 18.75
            [id] => 46
        )

    [3] => Array
        (
            [posY] => 7.5
            [posX] => 52.5
            [id] => 29
        )

    [4] => Array
        (
            [posY] => 15
            [posX] => 45
            [id] => 49
        )

    [5] => Array
        (
            [posY] => 16
            [posX] => 75
            [id] => 15
        )
)

Нужно сгруппировать элементы массива по условию: posX && posY в группе отличаются каждая друг от друга не более чем на +\- какое-то значение.
Это координаты по X и Y.
Другими словами, элементы с близкими обеими координатами нужно объединить в группу. Степень близости для каждой координаты задаем отдельно (Х +\- 5, Y +\- 10 , например)

На выходе нужно получить массив:

Array 
(
    [1] => Array
        (
            [0] => Array
                (
                    [posY] => 5
                    [posX] => 48.75
                    [id] => 36
                )
        )

    [2] => Array
        (
            [0] => Array
                (
                    [posY] => 5
                    [posX] => 52.5
                    [id] => 35
                )

            [1] => Array
                (
                    [posY] => 5.5
                    [posX] => 18.75
                    [id] => 46
                )

            [2] => Array
                (
                    [posY] => 7.5
                    [posX] => 52.5
                    [id] => 29
                )
        )

    [3] => Array
        ( 
            [0] => Array
                (
                    [posY] => 15
                    [posX] => 45
                    [id] => 49
                )

             [1] => Array
                (
                    [posY] => 16
                    [posX] => 75
                    [id] => 15
                ) 
        )
)

Делать через фиксированное число групп с предопределенными диапазонами нельзя, нужно именно проверять по критерию близости и объединять по нему в группу.

УПД: поясню задачу. Есть двухмерная схема. Есть объекты с координатами. Х - производная от размера. У - производная от глубины заныривания объекта. Мне нужно сгруппировать объекты, которые ныряют на одинаковую глубину и похожего размера, в группы.


Помогите алгоритмом?
Спасибо!

Answer 1

[Mrrl]

Непонятная задача.
Во-первых, решений может быть много. Например, пусть границы - abs(dx) <= 5, abs(dy) <= 5. Точки A=(0,0), B=(4,4), C=(7,7). Тогда решением будет и {A,B},{C} и {A},{B,C}. Из них правильно какое-то одно, или оба?
А если точки A=(0,0), B=(4,4), C=(7,7), D=(11,11)? Годится ли решение {A},{B,C},{D}? В нём больше групп, чем в {A,B},{C,D}, но центральная группа плотнее.
И наконец, является ли условие "posX && posY в группе отличаются каждая друг от друга не более чем на +\- какое-то значение" единственным? Если да - достаточно создать N групп, по одному элементу в каждой. Условие будет выполнено. А если нет - попытайтесь объяснить, почему конкретно это решение не годится. Сформулировать условие, которое нарушено. Может быть, тогда станет понятнее, что же это за задача. А пока это лишь пожелание "сделайте мне красиво".

А если задача не формализована - ищите слово "кластеризация". Про неё много интересного написано.

Comments

[Андрей Енькин]

Спасибо за мысли. Мне подойдет любой из перечисленных вариантов. Сделал по мотивам апдейт вопроса с пояснением задачи.

[Mrrl]

Простейший вариант: берёте любой элемент. Сортируете остальные по расстоянию до него (расстояние считается как max(abs(x1-x2)/max_dx,abs(y1-y2)/max_dy) ). Просматриваете элементы по порядку, и смотрите, какие можно добавить в группу, исходно состоящую из выбранного элемента. Когда таких не осталось - первая группа сформирована, выдаёте её и исключаете попавшие в неё элементы из массива. Повторяете, пока массив не кончился.
Можно начать с пары элементов, расстояние между которыми минимально. Тогда будет больше шансов на плотные группы.

Answer 2

[xmoonlight]

deltaX=abs(posX0-posX1)
deltaY=abs(posY0-posY1)
далее - приведите функции к Вашему коду согласно структуре.

Comments

[Андрей Енькин]

Спасибо, но это если по одной координате группировать и элементы отсортированы по ней. Порог по Х=5, по У=10, например. а(12,80), b(45,79), с(14,78) . Как сгруппировать a и с, если deltaX = abc(45-14) > порога?

[xmoonlight]

Андрей Енькин: почему 45-14 то? a и c: deltaX=abs(12-14)