How Others Do It #1

Each programmer has an unique style and aims for different things: readability, reusability, speed, length, etc.

A How Others Do It thread features a problem that participants will solve in their own way.

Note that this is not a contest, the main point of the thread is that we can learn from others and discover different ways to solve the same problem.

If you want to take part, please make sure to include your code (at least all the relevant parts) that solves the presented problem.

Suggested by: Draco18s

Topic: Sorting a collection of objects based on distance from a known point.

Instructions:

1) Assume that a point p is constant (i.e. does not change during code execution)
2) Assume that the array of objects objectArray contains objects with an x and y property
3) Assume you have an O(1) sort function available to operate on any list or array type passed

The goal of the exercise is not to optimize the sort itself, but rather to see how you lay out the structure prior to sorting.

Assume you have an O(1) sort function available to operate on any list or array type passed

Wow – pretty sick sort function. :D

Reserved for my answer later.

I’ll answer this when I get time… but I am wondering, what exactly do you want? Do you want us to just find the distance from the point, and then sort the data in our own way? Is that it basically?

Another question: Can the objects inside of objectArray include an extra property (d)?
Mostly to see if we can simply sort on that or we’d need to create an extra list / figure out another way.

E:

public static function sortByDistance(p:Point,o:Array):void{
	const
		x:Number=p.x,
		y:Number=p.y,
		e:int=o.length,
		d:Vector.<Pair>=new Vector.<Pair>(e);
	var
		v:DisplayObject,
		i:int=e;
	while(--i>-1)
		v=o[i],
		d[i]=new Pair(((x-v.x)*(x-v.x))+((y-v.y)*(y-v.y)),v);
	magicallySort(d,"d");
	i=e;
	while(--i>-1)
		o[i]=d[i].v;
}

• v type can be changed to whatever the contents of objectArray are.
• Pair is a class with property d and v (the object).

public static function sortByDist(p:Point, a:Array):Array {
	var temp:Array = new Array(a.length); // Create a new areay
	for (var i:int = 0; i < a.length; i++ ) {
		temp[i] = { d:Math.sqrt(((p.x - a[i].x) * (p.x - a[i].x)) + ((p.y - a[i].y) * (p.y - a[i].y))), obj:a[i]}; // Populate the array with Objects containing the object and the distance
	}
	
	sort(temp, "d"); // Sort array using our fancy sort function
	
	for (i = 0; i < temp.length; i++) {
		temp[i] = temp[i].obj; //reassign the indexes to be the original objects
	}
	
	return temp;
}

Amidoinitrite?

Whipped this up in a couple minutes. Probably nowhere near as efficient as it could be.

Interesting- I’ll definitely do this.

E: There we go.

import flash.geom.Point;
public static const MAIN_POINT:Point = new Point( 300, 400 ); // Point
private var pointList:Vector.<Point> = new Vector.<Point> // Points in here.

for ( var i:int = 0; i < pointList.length; ++i )
{
	var distList:Vector.<Number> = new Vector.<Number>();
	var dist:Number = Math.pow( pointList[ i ].x - MAIN_POINT.x, 2 ) + Math.pow( pointList[ i ].y - MAIN_POINT.y, 2 );
	
	distList.push(dist);
}
sort(distList);

Originally posted by MoonlaughMaster:

public static function sortByDist(p:Point, a:Array):Array {
	var temp:Array = new Array(a.length); // Create a new areay
	for (var i:int = 0; i < a.length; i++ ) {
		temp[i] = { d:Math.sqrt(((p.x - a[i].x) * (p.x - a[i].x)) + ((p.y - a[i].y) * (p.y - a[i].y))), obj:a[i]}; // Populate the array with Objects containing the object and the distance
	}
	
	sort(temp, "d"); // Sort array using our fancy sort function
	
	for (i = 0; i < temp.length; i++) {
		temp[i] = temp[i].obj; //reassign the indexes to be the original objects
	}
	
	return temp;
}

Amidoinitrite?

Whipped this up in a couple minutes. Probably nowhere near as efficient as it could be.

i was expecting someone to make such a mistake; you don’t have to sqrt it :)

Erk… gotta reformat this sometime…
private var inList:Vector<Points>;

inList = new Vector<Points>;

public function sort(inX:Number, inY:Number)

{
var tempList:Vector.<Number> = new Vector.<Number>();

for (var a:int = 0; a < inList.length; a++)
{
tempList.push(((inX - inList[a].x)(inX - inList[a].x)) + ((inY - inList[a].y)(inY - inList[a].y)));
}

//Do sorting after this point. Make sure to move points in both lists with the swapping methods.
//Also remember the tempList contains squares, not real values.
}

Originally posted by qwerberberber:

Originally posted by MoonlaughMaster:

public static function sortByDist(p:Point, a:Array):Array {
	var temp:Array = new Array(a.length); // Create a new areay
	for (var i:int = 0; i < a.length; i++ ) {
		temp[i] = { d:Math.sqrt(((p.x - a[i].x) * (p.x - a[i].x)) + ((p.y - a[i].y) * (p.y - a[i].y))), obj:a[i]}; // Populate the array with Objects containing the object and the distance
	}
	
	sort(temp, "d"); // Sort array using our fancy sort function
	
	for (i = 0; i < temp.length; i++) {
		temp[i] = temp[i].obj; //reassign the indexes to be the original objects
	}
	
	return temp;
}

Amidoinitrite?

Whipped this up in a couple minutes. Probably nowhere near as efficient as it could be.

i was expecting someone to make such a mistake; you don’t have to sqrt it :)

That’s very true. I pulled it directly from my utils class in which it does have to be a pretty number, so that’s why it’s there.

Sorry- Why is no square root needed?

Because for a and b two real, positive numbers, if a > b then sqrt(a) > sqrt(b). Since you’re not interested in the value of the distance but only in the ordering of distances, you don’t need to compute the actual distance, its square is enough.

		public function orderAround(center:Point, dots:Array):void
		{
			var dist:Array = new Array(dots.length);
			var i:int = 0;
			var dx:Number;
			var dy:Number;
			while (i < dist.length)
			{
				dx = dots[i].x - center.x;
				dy = dots[i].y - center.y;
				dist[i] = [i, dx * dx + dy * dy];
				i++;
			}
			GodSort(dist, 1); // Magically sort the Array of Arrays dist 
					// based on the value at index 1 of each of its elements.
			i = 0;
			while (i < dist.length)
			{
				dist[i] = dots[dist[i, 0]];
				i++;
			}
			dots = dist;
		}

I’m not sure what else there is to add, I’d have done it roughly the same way.

But in terms of the sorting, what are the faster ways it could be done?
The simplest I could come up with on the spot would need 1/2 (list.length)^2 interactions:
search list, find lowest distance, push to array
search list -1, find lowest distance, push to array
search list -2 ……

Originally posted by feartehstickman:

The simplest I could come up with on the spot would need 1/2 (list.length)^2 interactions:
search list, find lowest distance, push to array
search list -1, find lowest distance, push to array
search list -2 ……

There are plenty of sorting algorithms. Many are better than n².
This is not topic of this thread.

Originally posted by BobTheCoolGuy:

Assume you have an O(1) sort function available to operate on any list or array type passed

Wow – pretty sick sort function. :D

The point is to assume a perfectly optimized sort function. The goal is to set up the datastructure to sort, not actually write a sort function. So I have people assume that a super-optimal sort function exists.

Originally posted by Senekis93:

Another question: Can the objects inside of objectArray include an extra property (d)?
Mostly to see if we can simply sort on that or we’d need to create an extra list / figure out another way.

The original objects on stage cannot, but any temporary object you set up to pass to the sort function can.
MoonlaughMaster appears to have done it that way, as have I in the past.

sortByDistance :: Point -> [Point] -> [Point]
sortByDistance (x0,y0) = sortBy (compare `on` \(x,y) -> (x-x0)^2 * (y-y0)^2)

Haskell I know, but I do think the functional style is clearer here.

Originally posted by Draco18s:

The original objects on stage cannot, but any temporary object you set up to pass to the sort function can.

Ok. Edited my previous post.