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

[Zebestov]

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

[Hauts]

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

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

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

[Zebestov]

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

[alatar]

Сообщение от Hauts

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

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

[Hauts]

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

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

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

[alatar]

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

[Hauts]

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

[alatar]

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 минут
Или еще проще:

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

[Hauts]

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

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

[Hauts]

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

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 Кб)

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

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

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