Выражение для оценки равномерности расстановки 2 видов точек

[Gomez]

Есть два вида точек на плоскости: добывающие скважины и нагнетательные скважины.
Т.е. у каждой точки есть три свойства: координата Х, координата Y и тип (принимающий два значения).

Нужно какое-то выражение (целевая функция), которое оценивает степень равномерности расстановки точек на плоскости (в заданной области), и имеет максимум при наиболее равномерной расстановке точек. При этом нужно, чтобы каждую нагнетательную скважину окружало по возможности одинаковое количество добывающих скважин, а не так, что в одной области оказывались только добывающие, а в другой - только нагнетательные скважины.

В идеале максимум целевой функции (при заданном количестве точек в соотношении типов 3 к 1) должна давать при расположении как на картинке:



Искомое выражение будет использоваться как целевая функция в генетическом алгоритме, который будет расставлять скважины в области. Помимо равномерности, есть и другие условия (свойства пласта), с которыми то всё более менее ясно, но первая часть задачи состоит в том, чтобы предполагая полностью однородный пласт получать равномерную расстановку.

Первое, что я сделал, чтобы получить просто равномерную расстановку одного вида точек - это считать сумму обратных квадратов расстояний от каждой точки для всех других. Если брать её со знаком минус, то расстановка получается достаточно равномерной для максимума этой функции и устойчиво находится (при любой начальной расстановке), однако уже здесь возникает проблема, что все точки стремятся к краям области, и в центре их оказывается меньше, у краёв:



Если же рассматривать уже второй вид точек, то к тому значению целевой функции, что я описал выше, я прибавлял следующее. Я считал расстояние от каждой нагнетательной скважины до ближайшей добывающей, а дальше считал среднее отклонение расстояний до остальных трёх (или другого числа) самых ближайших добывающих скважин от расстояния до ближайшей скважины и брал его со знаком минус (сумма по всем нагнетательным скважинам). И этот метод немного работает, но решения даёт совершенно неустойчивые (т.е. самые разнообразные) и далёкие от того, что ожидаешь, а также начинает нарушаться равномерность.



Чтобы исключить смещение скважин к краям и отталкивание их от центра я попытался использовать в качестве целевой функции сумму расстояний от i-й скважины до ближайшей соседней. При этом выразил его так, что обо возрастало нелинейно, а затухающе (и имело предел):

$Value=R/(R+b)$
где R - расстояние до ближайшей скважины, а b - положительная постоянная.

Такой подход также приводит к неверным решениям (по всей видимости из-за неустойчивости):

[DeBill]

Gomez в сообщении #1138399 писал(а):

В идеале

Ну и прекрасно! Возьмите прямо эту картинку (гексагональная решетка, да?), отмасштабируйте - чтоб заданное число черно-белых точек было - и всуньте в свою область...

Gomez в сообщении #1138399 писал(а):

все точки стремятся к краям области,

Ну конечно! Ведь в центре у точек соседей много, а на краю - мало.
Добавьте в целевую функцию штраф (обратный квадрат расстояния до каждой из границ - верт. и гориз. - с коэф-том. Его надо подбирать, но, думаю, надо 2. Или полтора? )
Для двух видов: странно, что вааще что-то получилось. Я бы на месте программы, расставил бы хорошо белые, а черные - их меньше - засунул бы прямо в белые...(за это то штрафа нет, не правда ли?).
А почему бы не использовать в точности такую же штрафную ф-ю (сумму обратных квадратов расстояний, со знаком минус, отдельно - по черным, по белым, и по парам черный-белый, мобыть, с разными весами, и со штрафом за близость к краям, описанным выше?)

[Pphantom]

DeBill в сообщении #1138507 писал(а):

Добавьте в целевую функцию штраф (обратный квадрат расстояния до каждой из границ - верт. и гориз. - с коэф-том. Его надо подбирать, но, думаю, надо 2. Или полтора? )

Возможно, проще будет рассматривать расстановку на торе: "склеив" у области верх с низом, а правый край - с левым.

[MeV]

Задача очень близка к технологии печати серого фона из черных точек: blue noise pattern
Там масса всего опробовано в этой области. Например:
http://www.hpl.hp.com/research/isl/halftoning/publications/DitheringWithBlue.pdf

Т.е. задача сводится к генерации двумерного массива точек со свойствами синего шума. Общее количество точек равно требуемому общему количеству скважин. Затем поверх накладывается другой массив с общим количеством точек равного только одному типу скважин. Далее для каждой точки из второго массива находится ближайшая точка из первого. Таким образом первый массив разбивается на совокупность двух видов точек.

[dimkadimon]

Перепробовал несколько функций. Вроде что то подходящее нашел но она не очень красивая. Для каждой точки я нахожу расстояние до ближайшей точки такого же типа (А) и расстояние до ближайшей точки другого типа (B). Для функции беру $10A+B$ с каждой точки. Расстояние считаю через manhattan: $d(a,b)=|a.x-b.x|+|a.y-b.y|$. Вот пример решения: