Friday, November 16, 2018

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

Applescript:

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

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

 

Board footer

Powered by FluxBB

RSS (new topics) RSS (active topics)