Help - Working with Coordinate Lists

I’m trying to work with a given list of 10 two-item lists, or a list of coordinates if you will. For instance:

set list1 to {{0, 0}, {-1, 0}, {-2, 0}, {-2, -1}, {-1, -1}, {0, -1}, {0, -2}, {-1, -2}, {-2, -2}, {-3, -2}}

If you plot these with the Cartesian system, you get this:

What I want a script to be able to do is create the following from the previous list, or another given list of adjacent coordinates:

set list 2 to {{{-2, 0}, {-1, 0}, {0, 0}}, {{-2, -1}, {-1, -1}, {0, -1}}, {{-3, -2}, {-2, -2}, {-1, -2}, {0, -2}}}

list2 contains the same coordinates as list1 except they are categorized by their Y value, in descending order, then again by their X value in ascending order.

So I want the script to find the coordinate with the largest Y value, then put it and all coordinates with the same Y value in a list, ordered from their smallest X value to their largest X value. Then the script finds the next highest Y value and repeats the process. At the end, the script puts all those lists into one overarching list, in descending Y value order.

I made a stab at this but I couldn’t do it. Here’s what I got, but it doesn’t work. If anyone has any ideas or tips, I would be exceedingly grateful.

--A list of 10 adjacent X/Y coordinates
set list1 to {{0, 0}, {-1, 0}, {-2, 0}, {-2, -1}, {-1, -1}, {0, -1}, {0, -2}, {-1, -2}, {-2, -2}, {-3, -2}}

--placeholder for largest item 2 (Y value) among the coordinates in list1
set yMargin to ""

--For new lists
set list2 to {}
set list3 to {}

--returns a new list made from the fromList, excluding items it finds in the toList
on updateListItems(fromList, toList)
	set newList to {}
	repeat with i in fromList
		if i is not toList then
			copy i to end of newList
		end if
	end repeat
	return newList
end updateListItems

--sets yMargin to the highest item 2 (Y value) of the items in list1
repeat with i in list1
	set yValue to (item 2 of i)
	if yMargin is "" then
		set yMargin to yValue
	else if yValue is greater than yMargin then
		set yMargin to yValue
	end if
end repeat

--all coordinates in list1 whose item 2 is equal to yMargin are copied into list2
repeat with i in list1
	if (item 2 of i) is yMargin then
		copy i to end of list2
	end if
end repeat

--all items that are now in list2 are deleted from list1
set list1 to updateListItems(list1, list2)

--reorders items in list2 by putting them into list3 in order of smallest X value to largest X value
repeat (count list2) times
	
	--the smallest item 1 (X value) among the coordinates in list2
	set xMargin to ""
	
	repeat with i in list2
		set xValue to (item 1 of i)
		
		if xMargin is "" then
			set xMargin to xValue
			set leastX to i
		else if xValue is less than xMargin then
			set xMargin to xValue
			set leastX to i
		end if
		
	end repeat
	
	copy leastX to end of list3
	--remove items copied to list3 from list2
	set list2 to updateListItems(list2, list3)
end repeat

return list3

Model: MacBook Pro 15"
AppleScript: AppleScript 2.3.1
Browser: Safari 537.74.9
Operating System: Mac OS X (10.8)

Hi.

Here’s one approach: sort the coordinates into the required order, then group them into equal-Y lists.

-- A customisable sort handler.
on CustomInsertionSort(theList, l, r, customiser)
	script o
		property comparer : me
		property slave : me
		property lst : theList
		
		on isrt(l, r)
			set u to item l of o's lst
			repeat with j from (l + 1) to r
				set v to item j of o's lst
				if (comparer's isGreater(u, v)) then
					set here to l
					set item j of o's lst to u
					repeat with i from (j - 2) to l by -1
						tell item i of o's lst
							if (comparer's isGreater(it, v)) then
								set item (i + 1) of o's lst to it
							else
								set here to i + 1
								exit repeat
							end if
						end tell
					end repeat
					set item here of o's lst to v
					slave's shift(here, j)
				else
					set u to v
				end if
			end repeat
		end isrt
		
		on isGreater(a, b)
			(a > b)
		end isGreater
		
		on shift(a, b)
		end shift
	end script
	
	set listLen to (count theList)
	if (listLen > 1) then
		if (l < 0) then set l to listLen + l + 1
		if (r < 0) then set r to listLen + r + 1
		if (l > r) then set {l, r} to {r, l}
		
		if (customiser's class is record) then set {comparer:o's comparer, slave:o's slave} to (customiser & {comparer:o, slave:o})
		
		o's isrt(l, r)
	end if
	
	return -- nothing.
end CustomInsertionSort

-- A "plug-in" to customise the sort handler's comparisons.
-- This one causes coordinate pairs to be reverse-sorted on Y with forward subsorts on X.
-- Pair a is "greater than" (ie. should go after) pair b if (a's Y = b's Y and a's X > b's X) or (b's Y > a's Y).
script YdescXasc
	on isGreater(a, b)
		set {Xa, Ya} to a
		set {Xb, Yb} to b
		if (Ya = Yb) then return (Xa > Xb)
		return (Yb > Ya)
	end isGreater
end script


set list1 to {{0, 0}, {-1, 0}, {-2, 0}, {-2, -1}, {-1, -1}, {0, -1}, {0, -2}, {-1, -2}, {-2, -2}, {-3, -2}}

-- Sort a copy of list1, the coordinate pairs sorted Y descending with ascending subsorts on x.
copy list1 to list1Sorted
CustomInsertionSort(list1Sorted, 1, -1, {comparer:YdescXasc})

-- Create list2 with the now-ordered coordinates grouped into lists with equal Ys.
set list2 to {}
set end of list2 to {beginning of list1Sorted}
set currentY to end of end of result
repeat with i from 2 to (count list1Sorted)
	set theseCoords to item i of list1Sorted
	set thisY to end of theseCoords
	if (thisY = currentY) then
		set end of end of list2 to theseCoords
	else
		set end of list2 to {theseCoords}
		set currentY to thisY
	end if
end repeat

list2
--> {{{-2, 0}, {-1, 0}, {0, 0}}, {{-2, -1}, {-1, -1}, {0, -1}}, {{-3, -2}, {-2, -2}, {-1, -2}, {0, -2}}}

Thank you so much. That is a fantastic script. I just wish I could really understand how it works. haha. Just goes to show how much more there is to Applescript than what I know. Again, thanks a million.

For your purposes, you don’t need to understand the sort handler’s internal workings ” only everything else in the script. :wink: But I should perhaps have explained these two lines:

The sort actually arranges the items in the list passed to it, so it’s set to work on a duplicate here in case you still need the original in its original order.

The parameters mean: “Sort items 1 thru -1 of list1Sorted, using the isGreater() handler in the script object YdescXasc to compare them.” The last parameter’s a record in order to be able to differentiate between a script object with a comparison handler and another kind which the sort can also use.

The isGreater() handler in this case tells the sort that one Y coordinate is greater than the other if in fact it’s the other way round, which is how the reverse sort is obtained. If the two Ys are the same, it’s the normal comparison of the two X’s which determines which pair of coordinates is the “greater”.

Hi, Nigel. Since they’re so different, I’ll share my sorting method. I haven’t compared them at all for efficiency, but mine is shorter and perhaps easier to follow.


set theList to {{0, 0}, {-1, 0}, {-2, 0}, {-2, -1}, {-1, -1}, {0, -1}, {0, -2}, {-1, -2}, {-2, -2}, {-3, -2}}
sort(sort(theList, 1, "ascending"), 2, "descending")

(*
Although the example lists are in pairs, the handler can work with any quantity, dependent on the positionIndex.

This example features two handler calls: the passed list (including the returned value of the first call”"theInstances"), the sort position within the list, and the numeric course.
*)

-----------------------------------------------------------------------------------------------------------------------------------------------

on sort(target, positionIndex, direction)
	--BOOKEND (finds extreme ranges and limits to unique integers)
	set Maximal to 0
	set Minimal to 0
	set permissible to {}
	repeat with numbr from 1 to count target
		tell target's item numbr's item positionIndex
			if permissible does not contain it then set permissible's end to it
			if it > Maximal then set Maximal to it
			if it < Minimal then set Minimal to it
		end tell
	end repeat
	(*
	example first pass result: 
	minimal = -3
	maximal = 0
	permissible =  {0, -1, -2, -3} --apparent order is only coincidental to this example; it has yet to be arranged
	*)
	
	--ARRANGE (puts permitted values into numeric order)
	set newOrder to {}
	repeat with numbr from Minimal to Maximal --highly disparate ranges (gargantuan numbers) may retard this, because iteration 
		if numbr is in permissible then set newOrder's end to numbr --expands the range between endpoints
	end repeat
	if not direction = "ascending" then set newOrder to newOrder's reverse --accomodates course changes
	(*
	on 1st run, newOrder = {-3, -2, -1, 0}
	*)
	
	--INSTANTIATE (cross-references numbers in the reordered list against the original, realizing them into an instance list)
	set theInstances to {}
	repeat with numbr from 1 to count newOrder
		repeat with value from 1 to count target
			if target's item value's item positionIndex is newOrder's item numbr then set theInstances's end to target's item value
		end repeat
	end repeat
	theInstances --example first pass result: {{-3, -2}, {-2, 0}, {-2, -1}, {-2, -2}, {-1, 0}, {-1, -1}, {-1, -2}, {0, 0}, {0, -1}, {0, -2}}
end sort

edited for commenting

Hi Marc.

I don’t recognise your algorithm, but it certainly does the job here. On my machine, using my own script timer, it sorts the given list in 1.0E-3 seconds (about a thousandth of a second), which isn’t very much. Mine, including the preceding ‘copy’ line, times in at 0.0 seconds (too short to measure), which is only slightly less. :wink:

Yours is obviously hard-coded to sort lists of lists on items with numerical values and the efficiency of the “arrange” section depends on those values being close together. If, for instance, you append a coordinate {1000000, -1000000} to the end of theList, my sort still takes 0.0 seconds (including the preceding ‘copy’) whereas yours now takes 8.831 seconds, on average.

Mine’s hard to understand because I’ve simply pulled it out of my library of sorts and it contains quite a lot of code which isn’t directly relevant to the immediate problem. Its core (the contained isrt() handler) is an insertion sort, which is an ideal algorithm with short lists. This customisable version doesn’t compare list items itself, but passes them to the isGreater() handler in the supplied script object (YdescXasc in my script), which uses its own criteria to determine whether or not the item on the left should go after the item on the right. The same sort code can thus handle practically anything, given a suitable comparison plug-in. If no such script object’s supplied, the sort uses its own built-in isGreater() handler to do straight comparisons of the items. The calls to a shift() handler are for sorting other lists in parallel and aren’t relevant here.