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

в некоторых реализациях точки расположены равномерно и плотно по всему прямоугольнику, в других сконцентрированы в виде сгустков, при этом есть крупные участки прямоугольника не заполнены точками... 

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

то есть требуется постоить алгоритмический критерий плотности заполнения... 

Ну в простейшем варианте это укрупнение - скажем разбиение прямоугольника на приблизительно K = SQRT(N) равновеликих областей, подсчет количества точек по областям и построение гистограммы плотности распределения количества точек. В принципе при условии, что разбрасывание действительно случайно, результаты должны получаться вполне адекватные. Количество областей может выбираться как исходя из приблизительно равного количества "кусков" по каждой из осей, так и исходя из максимальной близости каждой такой прямоугольной области к квадрату. Теоретически ты должен получать статистическое распределение. А смещение максимума от среднего и ширина дадут тебе ойценку отклонения от равномерности. Можно будет даже с достаточно приличной вероятностью посчитать количество центров вброса точек, если оно будет не более SQRT(K).

Возможен другой вариант - просчитывается К таких областей, выбираемых случайно, опять-таки с построением-обработкой гистограммы, эдакий Монте-Карло. Но для тысяч точек это, пожалуй, фиговато... вот кабы сотни тысяч...

а как на основе распределения получить число, характеризующее плотность заполнения?

и ещё два замечания
1. управлять положением точек в реализации нельзя. поэтому я говорю, что координаты случайные. а вот про равномерное распределение - не ручаюсь... но не это важно...
2. в одномерном случае таким критерием может служить максимальное расстояние между соседними точками. чем оно меньше, тем заполнение отрезка плотнее. очевидно, что в двумерном случае такой критерии неприменим.

А что такое "число, характеризующее плотность заполнения"???


Нет.


А что такое "плотнее"???

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

такое моё мнение. 

И я о том же... основная проблема - именно выбор адекватной сетки.

Если в прямоугольнике нет больших областей, не заполненых точками - считаем, что точки расположены плотно. Чем больше такие "пустые" области - тем менее плотно он заполнен. А вот как формально описать этот критерий одним числом на основе координат точек - в этом и вопрос...

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

в общем случае координаты точек - вещественные, но если надо - можно округлить (только не очень сильно)

совпадение координат двух и более точек не исключено

на сегодня придумал такие варианты решения:

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

2. то же самое, но критерием является максимальная сторона треугольника из тех же соображений.

Теперь поясню, зачем это надо. В N точках плоскости внутри квадрата проводятся измерения некоторого двумерного поля. Требуется сделать двумерное преобразование Фурье этого поля на основе этих измерений. Видимо, придётся приводить к мелкой однородной сетке.

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

Как я считаю, для выполнения первого из этих условий требуется заполнить ВЕСЬ прямоугольник, а для второго заполнить его МАКСИМАЛЬНО ПЛОТНО.

Может, будут ещё какие идеи, или критерии, помогающие оценить и уменьшить ошибку?

может лучше интерполяцию\экстраполяцию сделать, получим непрерыную функцию двух переменных, потом и загонять её в фурье.

Насколько значения этого поля "гладкие"? 

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

Что же касается интерполяции - приведение к мелкой равномерной сетке, о котором я писал в предыдущем посте, и есть частный случай интерполяции. Однако, интерполируя реализации с большей "плотностью точек", я ожидаю уменьшения ошибок и расширения диапазона правдоподобных волновых чисел. Так как же формально оценить эту "плотность точек" на основе их координат?

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

в данном случае, сетку наоборот надо укрупнять, чтобы получить более-менее достоверные отсчёты, причём сильно укрупнять. но это не даст никакой интересной спектральной характеристики.

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



плотность оценивается не из координат, а из количества точек в некоторой области (n / (w * h)). собственно о чём тут и шёл разговор в первых комментариях.

кстати, почему точки так загадочно расположены?

я обескуражен... весь смысл рассуждений - именно в анализе Фурье... Причём достоверная полоса и точность как раз должны быть максимальными, и, кроме того, их необходимо оценить...

Поле действительно шумоподобное, но с высокой достоверостью известно, что шум - скорее розовый, а не белый... только имеются в виду не частота, а двумерный волновой вектор...

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


ну а количество точек в некоторой области зависит от их координат. только какие области брать? и как именно оценить общую "плотность" исходя из плотности отдельных областей? брать среднюю плотность? минимальную? что больше коррелирует с ошибкой при интерполировании и преобразовании Фурье?

Это сообщение отредактировал(а) DoberZ - 15.1.2008, 22:21