Geometric Ordering Algorithm for Boxes from Top to Bottom, L to R?

Hi:

People are giving me documents with pages of boxes on them to fill with bits of text, in order, from top to bottom then left to right, on a loose grid. By “loose,” I mean, for example, the boxes are not precisely sized or aligned, either vertically or horizontally. So the top of what is considered the top row’s second box could be slightly higher than the other boxes in the row, and/or slightly to the right of other boxes in its column, etc.

This means that although I can easily visually see what order the boxes are in, and I can sort from T to B/L to R according to their geometric bounds, I can’t figure out how to calculate the placement order due to the non-exact alignments.

I hope that describes the problem well enough. Does anyone know how to solve the placement order problem by means of bounds measurements only? I don’t know if it’s logically possible, or even what terms to google for this kind of problem. My goal is to get a list of every box to fill in the document, in the correct order.

My only idea right now is to force all the vertical measurements into estimated rows (or “bands” or “groups”) like A, B, C, etc., and then sort by page number, “band” and the horizontal measurement (X). Quick pseudocode:
-Sort a page’s boxes by Y measurement
-Go to first bounds

  • Label it Row A
    -Store Y measurement
    -Go to next bounds.
    -If its Y is within .5" up or down, label it Row A, else increment its label to Row B
    -repeat until end

Then sorting by Page number, Row and X measurement should yield the correct placement order.

Any guidance or search/math terms much appreciated!

Hi. Whether it’s possible depends on how much disorder there is, especially if some objects impinge upon others. It could be tedious to solve programmatically and requires arbitrary tolerances. If the shifts are minimal, you could possibly select a row and just realign it and distribute the spacing. The way I’ve handled this problem in the past is to manually cut the items and paste them in place in reverse, which enforces the correct creation order and allows for label placement.

Hi: These boxes don’t impinge on each other, and they’re approximately lined up (for example, the tops and sides are within 1/2 inch of each other in the loose rows and columns). They don’t need to be (and shouldn’t be) aligned or re-aligned. Additionally, the loose “grids” can be missing cells (so there is no box in some positions) and be any shape, eg, 2x2, 3x4, 4x4, etc.

I just have to figure out a way to determine the order that they be filled. I’m tending to think that there is no automatic way to calculate this without making assumptions and that I’ll have to concoct a step-thru comparing procedure to add a forced Top “row” value to each item and then do a stable sort by page number, the added “row” value, and the Left values.

Thanks for your suggestions on this strange little problem!

Hi.

As Marc says, it depends on how much disorder there is. But if all the boxes are at least partially within the rows and columns they’re supposed to be in, and don’t overlap adjacent rows or columns, it’s fairly easy to get a list of them sorted by ‘bounds’. I’ve no idea what app your boxes come from, but the script below uses the bounds of items in an icon-view Finder window to illustrate the method. (It requires this sort as a library script.) You’d just replace the Finder code with the equivalent code for getting the boxes and their bounds from a page in your application.

use AppleScript version "2.3.1" -- Mac OS 10.9 (Mavericks) or later.
use scripting additions

-- This script uses my Custom Iterative Dual-pivot Quicksort <https://macscripter.net/viewtopic.php?pid=192496#p192496>,
-- assumed to have been saved with the name "Custom Iterative Dual-pivot Quicksort.scpt" in ~/Library/Script Libraries/.
use sorter : script "Custom Iterative Dual-pivot Quicksort"

-- Get a list of the items to be sorted (here the items in an icon-view Finder window) and a list of their 'bounds'.
tell application "Finder"
	tell items of target of front Finder window
		set {theItems, theBoundsLists} to {it, bounds}
	end tell
end tell


-- Sort customiser.
-- Bounds list 'a' should go after bounds list 'b' if a's top comes after (below) b's bottom or, failing that, a's bottom comes after b's top (same line) and a's left comes after b's right.
script byBounds
	on isGreater(a, b)
		set {aLeft, aTop, aRight, aBottom} to a
		set {bLeft, bTop, bRight, bBottom} to b
		
		return (aTop comes after bBottom) or ((aBottom comes after bTop) and (aLeft comes after bRight))
	end isGreater
end script

-- Sort items 1 thru -1 of the bounds list using the above customiser, rearranging the list of original items in parallel.
tell sorter to sort(theBoundsLists, 1, -1, {comparer:byBounds, slave:{theItems}})
return theItems

If you needed to include the page numbers in the sort, that could be done too. You could perhaps combine the bounds and page numbers into a list of records (eg. {{pageNumber:1, |bounds|:{522, 199, 586, 263}}, … } ) and sort like this:

use AppleScript version "2.3.1" -- Mac OS 10.9 (Mavericks) or later.
use scripting additions

-- This script uses my Custom Iterative Dual-pivot Quicksort <https://macscripter.net/viewtopic.php?pid=192496#p192496>,
-- assumed to have been saved with the name "Custom Iterative Dual-pivot Quicksort.scpt" in ~/Library/Script Libraries/.
use sorter : script "Custom Iterative Dual-pivot Quicksort"

-- Get a list of the items to be sorted (here the items in an icon-view Finder window), a list of their 'bounds', and a list of their page numbers.
tell application "Finder"
	tell items of target of front Finder window
		set {theItems, theBounds, thePageNumbers} to {it, bounds, {1, 4, 3, 5, 2, 1, 2, 3, 4, 5}} -- Page numbers obviously hard coded for this demo.
	end tell
end tell
-- Combine the page numbers and bounds into a list of records, each record containing an item's page number and bounds.
set pageNumbersAndBounds to {}
repeat with i from 1 to (count theItems)
	set end of pageNumbersAndBounds to {pageNumber:(item i of thePageNumbers), |bounds|:(item i of theBounds)}
end repeat


-- Sort customiser.
-- Record 'a' should go after record 'b' if (they have the same page number and a's top bound comes after (below) b's bottom or, failing that, a's bottom bound comes after b's top (same line) and a's left comes after b's right) or if a's page number come's after b's page number.
script byPageNumberAndBounds
	on isGreater(a, b)
		set aPage to a's pageNumber
		set bPage to b's pageNumber
		if (aPage = bPage) then
			set {aLeft, aTop, aRight, aBottom} to a's |bounds|
			set {bLeft, bTop, bRight, bBottom} to b's |bounds|
			return (aTop comes after bBottom) or ((aBottom comes after bTop) and (aLeft comes after bRight))
		else
			return (aPage comes after bPage)
		end if
	end isGreater
end script

-- Sort items 1 thru -1 of the list of records using the above customiser, rearranging the list of original items in parallel.
tell sorter to sort(pageNumbersAndBounds, 1, -1, {comparer:byPageNumberAndBounds, slave:{theItems}})
return theItems

Thanks Nigel! I will see if I can get your script combo to work. This is for InDesign boxes so I’ll have to change the order of the L, T, R, B from that of the Finder, but that should pose no problem. I was able to successfully use Filemaker as an intermediary/helper, but it will be nice if I can get everything done in Applescript! Thanks again!

I haven’t tested Nigel’s code; some implementation of his method could possibly be more efficient. My solution tests as working in an otherwise blank document set to inches. It may need adjustments to avoid unintended targets in a populated document, and it might not work as expected with other units, given the .5" tolerance. You didn’t specify if any reference point is more aligned than others; I’ve used the upper left. There’s no error trapping for violations of the column/row space.

tell application "Adobe InDesign CS3"'s document 1
	#approximate planar coordinates to tolerance
	set allBounds to text frames's geometric bounds
	set newTopLeft to {}
	repeat with anItem in allBounds
		set newTopLeft's end to {my halfRound(anItem's item 1), my halfRound(anItem's item 2)}
	end repeat
	newTopLeft
	
	#identify all potential columns and rows
	set {columnLocus, rowLocus} to {{}, {}}
	repeat with anItem in newTopLeft
		tell anItem's item 1 to if rowLocus does not contain it then set rowLocus's end to it --Y
		tell anItem's item 2 to if columnLocus does not contain it then set columnLocus's end to it --X
	end repeat
	set {columnLocus, rowLocus} to {my sort(columnLocus), my sort(rowLocus)}
	
	#label targets
	repeat with counter from 1 to count newTopLeft
		tell text frame counter
			repeat with ColCounter from 1 to count columnLocus
				if newTopLeft's item counter's item 2 = columnLocus's item ColCounter as real then
					set label to "Column: " & ColCounter
				end if
			end repeat
			repeat with rowCounter from 1 to count rowLocus
				if newTopLeft's item counter's item 1 = rowLocus's item rowCounter as real then
					set label to label & return & "Row: " & rowCounter
				end if
			end repeat
			set label to label & return & counter --index
		end tell
	end repeat
	
	#establish correct traversal order
	set flowOrder to {}
	set sortedFlow to my sort(rectangles's label)
	repeat with counter from 3 to ((count rectangles) * 3) by 3
		set flowOrder's end to sortedFlow's item counter --index
	end repeat
	
	--for demonstration ONLY; disable after testing
	activate
	repeat with x in flowOrder
		select text frame (x as number)
		delay 1
	end repeat
	
end tell



on sort(theList)
	set AppleScript's text item delimiters to linefeed
	(do shell script "echo " & (theList as text)'s quoted form & " | sort -g")'s paragraphs
end sort

on halfRound(Num)--code concept appropriated from user cwtnospam
	set divisor to 2
	set integerPart to (round Num rounding down)
	set decimalPart to (round ((Num - integerPart) * divisor)) / divisor
	integerPart + decimalPart
end halfRound

–edited for credit for halfRound handler and reduced unnecessary sorts by moving out of traversal loop

Thanks Marc Anthony. This looks like at will work too. Nice!