Friday, November 16, 2018

You are not logged in.

## #1 2018-07-11 11:36:15 am

kerflooey
Member
Registered: 2011-07-07
Posts: 155

### 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!

Offline

## #2 2018-07-11 04:56:33 pm

Marc Anthony
Member
From:: Dallas, TX
Registered: 2006-04-27
Posts: 841

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

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.

Offline

## #3 2018-07-12 10:10:12 am

kerflooey
Member
Registered: 2011-07-07
Posts: 155

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

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!

Offline

## #4 2018-07-12 04:28:40 pm

Nigel Garvey
Moderator
From:: Warwickshire, England
Registered: 2002-11-20
Posts: 4720

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

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.

#### Applescript:

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

-- 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:

#### Applescript:

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

-- 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

Last edited by Nigel Garvey (2018-07-12 04:29:52 pm)

NG

Offline

## #5 2018-07-13 09:23:50 am

kerflooey
Member
Registered: 2011-07-07
Posts: 155

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

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!

Offline

## #6 2018-07-14 11:12:40 am

Marc Anthony
Member
From:: Dallas, TX
Registered: 2006-04-27
Posts: 841

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

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.

#### Applescript:

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

Last edited by Marc Anthony (2018-07-14 07:12:55 pm)

Offline

## #7 2018-07-16 09:32:55 am

kerflooey
Member
Registered: 2011-07-07
Posts: 155

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

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

Offline