Форум Flasher.ru - Равномерная расстановка точек в произвольной фигуре

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

Равномерная расстановка точек в произвольной фигуре

Всем привет, с наступающим!

В общем, задумал я одну демку сделать. Смысл такой — есть последовательность кадров, черно-белых. В каждом кадре нарисовано пятно. При воспроизведении видно, как форма пятна "трансформируется". Далее я хочу расставить поверх пятна в каждом кадре некоторое фиксированное количество точек (предположим сто) таким образом, чтобы они равномерно заполнили площадь фигуры (пятна). На следующем кадре мне необходимо сделать то же самое, но с учетом того, чтобы соответствующие точки переместились в соответствующее место нового пятна. Грубо говоря, чтобы точка номер 45 не прыгала с одного угла пятна на другое при небольшом изменении формы пятна.

Пока что я вижу решение задачи таким: смотрим габариты пятна в текущем кадре, получаем прямоугольную область. Рассчитав размер точки исходя из площади пятна (делим площадь габаритной области на количество точек — получаем площадь габаритов для точки), мы располагаем точки во всегда одинаковом порядке — слева направо, сверху вниз. На этом момента получаются уже не точки даже, а полноценные окружности. Далее включаем механизм столкновения точек между собой и ограничения по форме пятна. То есть для столкновения между собой довольно тривиальный механизм будет использован, а вот для constrain по форме пятна уже придется шаманить с битмапдатами. И прогоняем такой код раз 200, например.

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

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

Есть у кого-нибудь идеи по этому поводу? Я больше чем уверен, что такая задача не нова и наверняка есть какие-нибудь более лаконичные и разумные решения.

Да, кстати. В итоге я хочу получить просто равномерный фиксированный по количеству набор точек на экране, которые перемещаются "сохраняя" форму оригинального пятна. Этакая интерполяция кадров, в общем.

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

Цитата:

Сообщение от DaFive (Сообщение 1110904)

О: http://www.flasher.ru/forum/blog.php?b=613
Не?

Нет конечно :)

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

Код AS3:

angle = Math.atan2 (point.y, point.x)

point.x -= Math.cos (angle) * point.length / state_x;

point.y -= Math.sin (angle) * point.length / state_y;

меняя state_x и state_y получил вот такую хрень:

Untitled-1.swf (1.8 Кб)

Спасибо за ответы, буду пробовать.

Пока что получилось вот так:

fill_image_with_points.swf (12.0 Кб)

Проверял идентичность результатов с помощью принтскрина и пэйнта, — вроде всегда встают в одно и то же положение.

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

Hauts,
Сколько примерно итераций?

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

Другой тест показывает, что соответственное перемещение не получится с моим подходом.

Хм, даже и не знаю, как это решить.

fill_image_with_points_2.swf (12.4 Кб)

Разместить горстку точек в центр фигуры и решать их в каждой итерации как частицы с одинаковым зарядом.

Zebestov, можно подробнее?

Как я понимаю, я примерно так и тестирую, размещаю все точки по небольшой окружности (чтобы расталкивать их можно было dx!=0 && dy!=0) в центре габаритной области, потом распихиваю их. Как только первая картинка отработала, я ее немного поворачиваю и скалирую, отрисовываю в бд заново и заново размещаю точки у центра, но уже, соответственно, у центра новой габаритной области.

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

Подробнее нужно углубиться, я этим не занимался вплотную.

Цитата:

Сообщение от Hauts (Сообщение 1110928)

Некоторые хорошо "съезжают" в нужном направлении, некоторые много "путешествуют".

После размещения точек перенумеруйте их слева-направо сверху-вниз.

Хм. Вариант, да.

Так же попробую пронумеровать от центра.

Alatar, если у меня нет у точки какого-либо свойства, отвечающего за индекс (да и по-сути, мне его и не нужно), имеет ли смысл два раза сортировать массив сначала по y точек, потом по x? Получится ли правильная нумерация? Или я туплю?:)

Зачем два раза сортировать? Все сортируется за один раз.

Можно намёк? Ато я не гуру как бы, мне сложно так сходу сориентироваться, к сожалению :(

Код AS3:

function sort(a:Object, b:Object):Number

{

    if (a.x < b.x)

    {

        return 1;

    }

    else if (a.x > b.x)

    {

        return -1;

    }

 

    return a.y - b.y;

}

Добавлено через 9 минут
Или еще проще:

Код AS3:

Array.sortOn (["x", "y"], Array.NUMERIC);

Понял, спасибо большое, намотал на ус :)

Буду тестировать.

Попробовал. Получается так себе. Очевидно, что смещение точек зачастую нерациональное, не такое, как хотелось бы.

Код AS3:

package

{

        import flash.display.Bitmap;

        import flash.display.BitmapData;

        import flash.display.Graphics;

        import flash.display.Sprite;

        import flash.display.StageScaleMode;

        import flash.events.Event;

        import flash.events.MouseEvent;

        import flash.geom.Point;

        import flash.geom.Rectangle;

 

        /**

         * ...

         * @author Hauts

         */

        public class Main extends Sprite

        {

                [Embed(source="../lib/image.png")]

                private var _imageClass:Class;

                private var _image:Bitmap;

                private var _bimapData:BitmapData;

                private var _debugDrawClip:Sprite;

                private var _imageContainer:Sprite;

                private var _results:Array;

 

                public function Main():void

                {

                        if (stage)

                                init();

                        else

                                addEventListener(Event.ADDED_TO_STAGE, init);

                }

 

                private function init(e:Event = null):void

                {

                        removeEventListener(Event.ADDED_TO_STAGE, init);

                        // entry point

 

                        stage.scaleMode = StageScaleMode.NO_SCALE

 

                        _results = [];

 

                        _image = new _imageClass() as Bitmap

                        _image.smoothing = true;

                        _imageContainer = new Sprite();

                        addChild(_imageContainer)

                        _imageContainer.addChild(_image);

 

                        _debugDrawClip = new Sprite();

                        addChild(_debugDrawClip)

 

                        stage.addEventListener(MouseEvent.CLICK, clickHandler);

 

                        nextTest()

                }

 

                private function clickHandler(e:MouseEvent):void

                {

                        nextTest()

                }

 

                private function nextTest():void

                {

                        _image.rotation = (Math.random() - 0.5) * 3

                        _image.scaleX = 0.9 + Math.random() * 0.1

                        _bimapData = new BitmapData(_imageContainer.width, _imageContainer.height, false, 0xFFFFFFFF);

                        _bimapData.draw(_imageContainer)

 

                        var points:Array = generateCoords(_bimapData, 25);

                        _results.push(points);

 

                        drawPoints(_debugDrawClip.graphics, points);

 

                        if (_results.length > 1)

                        {

                                drawWays(_debugDrawClip.graphics)

                        }

                }

 

                private function drawWays(gr:Graphics):void

                {

                        if (_results.length > 1)

                        {

                                var curPoints:Array = _results[_results.length - 1]

                                var prevPoints:Array = _results[_results.length - 2]

                                var totalPoints:int = curPoints.length;

                                for (var k:int = 0; k < totalPoints; k++)

                                {

                                        gr.moveTo(prevPoints[k].x, prevPoints[k].y)

                                        gr.lineStyle(1, 0x00FF00);

                                        gr.lineTo(curPoints[k].x, curPoints[k].y)

                                }

                        }

                }

 

                private function drawPoints(gr:Graphics, points:Array):void

                {

                        var totalPoints:int = points.length;

                        gr.clear();

                        gr.beginFill(0xFF0000);

                        var k:int

                        for (k = 0; k < totalPoints; k++)

                        {

                                gr.drawCircle(points[k].x, points[k].y, 3);

                        }

                        gr.endFill();

                }

 

                private function generateCoords(bitmapData:BitmapData, totalPoints:int = 100):Array

                {

                        var activeRect:Rectangle = bitmapData.getColorBoundsRect(0xFFFFFFFF, 0xFF000000, true);

                        var points:Array = [];

                        var rectSize:Number = activeRect.width * activeRect.height

                        var spacePerPoint:Number = rectSize / totalPoints;

                        var pointRadius:Number = Math.sqrt(spacePerPoint) / 2;

                        var k:int

                        var j:int

                        var p1:Point

                        var p2:Point

                        var newPoint:Point

                        for (k = 0; k < totalPoints; k++)

                        {

                                newPoint = new Point();

                                newPoint.x = activeRect.left + activeRect.width / 2 + Math.cos(k / totalPoints * Math.PI * 2);

                                newPoint.y = activeRect.top + activeRect.height / 2 + Math.sin(k / totalPoints * Math.PI * 2);

                                points.push(newPoint)

                        }

                        for (var i:Number = pointRadius; i >= 0; i -= 0.01)

                        {

                                for (k = 0; k < totalPoints; k++)

                                {

                                        p1 = points[k];

                                        for (j = 0; j < totalPoints; j++)

                                        {

                                                if (k != j)

                                                {

                                                        p2 = points[j] as Point;

 

                                                        var dx:Number = p1.x - p2.x;

                                                        var dy:Number = p1.y - p2.y;

 

                                                        var distance:Number = Math.sqrt(dx * dx + dy * dy);

                                                        var depth:Number = i * 2 - distance

                                                        if (depth > 0)

                                                        {

                                                                solveIntersection(bitmapData, p1, p2, (depth * dx / distance), (depth * dy / distance))

                                                        }

                                                }

                                        }

                                }

                        }

                        points.sortOn(["x", "y"], Array.NUMERIC);

                        return points;

                }

 

                private function solveIntersection(bitmapData:BitmapData, p1:Point, p2:Point, offsetX:Number, offsetY:Number):void

                {

                        p1.x += offsetX / 2;

                        p1.y += offsetY / 2;

                        p2.x -= offsetX / 2;

                        p2.y -= offsetY / 2;

                        if (bitmapData.getPixel(p1.x, p1.y) == 0xFFFFFF)

                        {

                                p1.x -= offsetX

                                p1.y -= offsetY

                        }

                        if (bitmapData.getPixel(p2.x, p2.y) == 0xFFFFFF)

                        {

                                p2.x += offsetX

                                p2.y += offsetY

                        }

                }

        }

}

Клик по флэшке — отрисует новые точки.

fill_image_with_points_3.swf (12.3 Кб)

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

И да, возможно я просто криво написал код.

Есть еще идеи? Подскажите :)

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

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

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

Добавлено через 10 минут
По сути твоя задача это морфинг одного объекта в другой. Все реализации "красивого" морфинга, что я видел делались вручную. Т.е. берется одна фигура из определенного количества точек и вручную передвигая точки из нее получается другая фигура. В итоге, заранее известно какая точка из одной фигуры будет соответствовать точке на другой.

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

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

http://napephys.com/samples.html#swf...uctibleTerrain

Вот типа такого.

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

А каким образом задан контур? Это функция или набор точек?

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

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

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

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

Дополнение:
А как такой вариант? Просканить битмапу и создать массив координат заполненных пикселей, при генерации распределения, выбираем случайную ячейку в массиве и вставляем точку в полученные координаты. По сути, это частный случай варианта про наложение сетки.

semenyakinVS, если ко мне вопрос, то у меня нет контуров. Есть просто картинки. На данный момент — просто пятна черные.

vizgl, спасибо, дельный совет, буду пробовать.