| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > критерий равномерного заполнения |
| Автор: DoberZ 9.1.2008, 22:05 |
| есть прямоугольник (задача плоская), и есть несколько реализаций (предположим, случайных) разбрасывания N точек внутри этого прямоугольника, прочём число N велико (сотни-тысячи) в некоторых реализациях точки расположены равномерно и плотно по всему прямоугольнику, в других сконцентрированы в виде сгустков, при этом есть крупные участки прямоугольника не заполнены точками... требуется для каждой реализации поставить в соответствие число (исходя из известных координат точек), отражающее вот эту самую плотность и равномерность заполнения прямоугольника то есть требуется постоить алгоритмический критерий плотности заполнения... |
| Автор: Akina 9.1.2008, 23:50 |
| Ну в простейшем варианте это укрупнение - скажем разбиение прямоугольника на приблизительно K = SQRT(N) равновеликих областей, подсчет количества точек по областям и построение гистограммы плотности распределения количества точек. В принципе при условии, что разбрасывание действительно случайно, результаты должны получаться вполне адекватные. Количество областей может выбираться как исходя из приблизительно равного количества "кусков" по каждой из осей, так и исходя из максимальной близости каждой такой прямоугольной области к квадрату. Теоретически ты должен получать статистическое распределение. А смещение максимума от среднего и ширина дадут тебе ойценку отклонения от равномерности. Можно будет даже с достаточно приличной вероятностью посчитать количество центров вброса точек, если оно будет не более SQRT(K). Возможен другой вариант - просчитывается К таких областей, выбираемых случайно, опять-таки с построением-обработкой гистограммы, эдакий Монте-Карло. Но для тысяч точек это, пожалуй, фиговато... вот кабы сотни тысяч... |
| Автор: DoberZ 10.1.2008, 01:11 |
| а как на основе распределения получить число, характеризующее плотность заполнения? и ещё два замечания 1. управлять положением точек в реализации нельзя. поэтому я говорю, что координаты случайные. а вот про равномерное распределение - не ручаюсь... но не это важно... 2. в одномерном случае таким критерием может служить максимальное расстояние между соседними точками. чем оно меньше, тем заполнение отрезка плотнее. очевидно, что в двумерном случае такой критерии неприменим. |
| Автор: Akina 10.1.2008, 11:01 | ||||||
А что такое "число, характеризующее плотность заполнения"???
Нет.
А что такое "плотнее"??? |
| Автор: stab 10.1.2008, 12:08 |
| если прямоугольник имеет дискретный шаг, то можно говорить о натуральной плотности. если нет, придётся вводить некую собственную дискретную сетку адекватную для задачи. тогда для каждой ячейки плотность будет количество точек в области делённое на общее число точек. глобальная плотность будет мат. ожиданием плотностей этих подобластей, а их дисперсия равномерностью. такое моё мнение.  |
| Автор: Akina 10.1.2008, 12:41 |
| И я о том же... основная проблема - именно выбор адекватной сетки. |
| Автор: DoberZ 13.1.2008, 00:39 | ||
Если в прямоугольнике нет больших областей, не заполненых точками - считаем, что точки расположены плотно. Чем больше такие "пустые" области - тем менее плотно он заполнен. А вот как формально описать этот критерий одним числом на основе координат точек - в этом и вопрос... |
| Автор: stab 14.1.2008, 19:12 |
| из условий задачи толком не ясно как решать, общий метод тут уже обрисовали. осталось выяснить выражаются ли координаты в целых числах и могут ли несколько точек иметь одни и те же координаты. |
| Автор: DoberZ 14.1.2008, 21:12 |
| в общем случае координаты точек - вещественные, но если надо - можно округлить (только не очень сильно) совпадение координат двух и более точек не исключено на сегодня придумал такие варианты решения: 1. прямоугольник делится на элементарные треугольники (не содержащие внутри ни одной точки) методом тринагуляции Делоне (кстати, спасибо, в этом разделе форума вычитал про него) затем считаются площади всех треугольников, из них находится максимальная. она и принимается критерием "равномерности" - чем она меньше - тем плотнее лежат точки 2. то же самое, но критерием является максимальная сторона треугольника из тех же соображений. Теперь поясню, зачем это надо. В N точках плоскости внутри квадрата проводятся измерения некоторого двумерного поля. Требуется сделать двумерное преобразование Фурье этого поля на основе этих измерений. Видимо, придётся приводить к мелкой однородной сетке. Специфика задачи такова, что задавать координаты точек измерения не представляется возможным - но есть несколько вариантов расположения этих точек внутри этого прямоугольника. Нужно выбрать тот вариант, который обеспечит наилучшую разрешающую способность при преобразовании Фурье, а также даст наименьшую элайзинговую ошибку. Как я считаю, для выполнения первого из этих условий требуется заполнить ВЕСЬ прямоугольник, а для второго заполнить его МАКСИМАЛЬНО ПЛОТНО. Может, будут ещё какие идеи, или критерии, помогающие оценить и уменьшить ошибку? |
| Автор: stab 14.1.2008, 23:26 |
| может лучше интерполяцию\экстраполяцию сделать, получим непрерыную функцию двух переменных, потом и загонять её в фурье. |
| Автор: Akina 15.1.2008, 00:26 | ||
Насколько значения этого поля "гладкие"? |
| Автор: DoberZ 15.1.2008, 03:23 |
| Поле негладкое в том смысле, что энергетический спектр этого поля (двумерный волновой) хоть и убывает начиная с некоторых значений волновых чисел, но ни при каких значениях волновых чисел не равен нулю - присутствуют с разной долей любые компоненты. Это, в частности, означает, что, по теореме Котельникова-Найквиста ошибок не избежать ни при каком шаге дискретизации. Однако даже здравый смысл подсказывает, что при "уплотнении" измерительной решётки ошибка дискретизации и спектрального анализа должна уменьшаться. А вот что характеризует степень "уплотнения" с точки зрения минимизации ошибок - в этот и вопрос... Что же касается интерполяции - приведение к мелкой равномерной сетке, о котором я писал в предыдущем посте, и есть частный случай интерполяции. Однако, интерполируя реализации с большей "плотностью точек", я ожидаю уменьшения ошибок и расширения диапазона правдоподобных волновых чисел. Так как же формально оценить эту "плотность точек" на основе их координат? |
| Автор: stab 15.1.2008, 14:55 | ||||
уплотнение имеет смысл, когда есть достоверные (или достоверные с некоторой известной вероятностью) данные о том, что содержится в отсутствующих точках. у вас же, я так понял, очень изрезанное\шумоподобное поле, т.е. интерполировать значения с заранее заданной предельной ошибкой в неизвестных точках невозможно. в данном случае, сетку наоборот надо укрупнять, чтобы получить более-менее достоверные отсчёты, причём сильно укрупнять. но это не даст никакой интересной спектральной характеристики. единственное, что приходит в голову - попытаться выделить кластеры с хорошей насыщенностью отсчётами, например такие, что максимальное расстояние между "смежными" точками не превышает значение некоторой функции от "диаметра" кластера. затем, сделать дискретизацию кластера по сетке с шагом равным максимальному расстоянию между "смежными" точками кластера. после чего изучать частотные характеристики, при этом забив на высокие и низкие частоты. понятно, что, в контексте всей исследуемой области, ни о каком достоверном спектре в диапазоне низких не может идти речи.
плотность оценивается не из координат, а из количества точек в некоторой области (n / (w * h)). собственно о чём тут и шёл разговор в первых комментариях. кстати, почему точки так загадочно расположены? |
| Автор: DoberZ 15.1.2008, 22:13 | ||
| я обескуражен... весь смысл рассуждений - именно в анализе Фурье... Причём достоверная полоса и точность как раз должны быть максимальными, и, кроме того, их необходимо оценить... Поле действительно шумоподобное, но с высокой достоверостью известно, что шум - скорее розовый, а не белый... только имеются в виду не частота, а двумерный волновой вектор... точки расположены так, потому, что измерения, собственно, уже проведены несколько раз с разным расположением точек...
ну а количество точек в некоторой области зависит от их координат. только какие области брать? и как именно оценить общую "плотность" исходя из плотности отдельных областей? брать среднюю плотность? минимальную? что больше коррелирует с ошибкой при интерполировании и преобразовании Фурье? |
