Software that makes placemats

Organise events to meet up and drink Port.
PhilW
Dow 1980
Posts: 2696
Joined: 14:22 Wed 15 Dec 2010
Location: Near Cambridge, UK

Re: Software that makes placemats

Post by PhilW » 12:26 Fri 28 Jun 2013

jdaw1 wrote:Broader question: what should be the default? That leads to a question about our behaviour.
...
I’m half-preferring acknowledging that we tend to do the second behaviour, so should have the second arrangement. Thoughts?
I think there is a good argument for at least facilitating the latter behaviour; If A3 printers were more common, I think we would more frequently be printing the glasses pages on A3 and then tasting note pages on A4 - in some ways this is equivalent to you scenario with card i.e. glasses printed on different paper (type vs size) than the tasting not pages. In this case it would be simpler (assuming possible) to specify the paper size for the glasses pages separately to the paper size for the rest, while still producing a single PDF with ordering as per #2; from this the glass pages and tasting note pages can then be more simply printed in two simple separate batches as pages 1..n and tasting notes as n+1..end rather than being interspersed.

However, the more common use is still likely to be A4-only, both due to lack of commonly available A3 printers and also convenience. In this case, I find that having the pages interspersed actually helps separating each persons set of pages while arranging positions at the table during setup. I would therefore suggest keeping this as the default behaviour, but add a simple switch at the start of the code, perhaps /PageOrderingAllGlassesFirst 0 which would allow someone to simply enable the non-interspersed ordering by setting to 1 if desired (I didn't immediately understand your proposed /PageOrderingNonDecanterLabelGlasses use, hence my alternate suggestion).

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 12:35 Fri 28 Jun 2013

If the paper sizes are different then, currently, the software sorts by paper size in the outermost loop (well, unless over-ruled byPageOrdering!). All of which seems to be what you have requested.

Also PageOrderingNonDecanterLabelGlasses already exists, being used, for example, if a tasting is over multiple sessions. (See badly-written § of manual.)

PhilW
Dow 1980
Posts: 2696
Joined: 14:22 Wed 15 Dec 2010
Location: Near Cambridge, UK

Re: Software that makes placemats

Post by PhilW » 12:48 Fri 28 Jun 2013

jdaw1 wrote:If the paper sizes are different then, currently, the software sorts by paper size in the outermost loop (well, unless over-ruled byPageOrdering!). All of which seems to be what you have requested.

Also PageOrderingNonDecanterLabelGlasses already exists, being used, for example, if a tasting is over multiple sessions. (See badly-written § of manual.)
ok; in which case my response is simplified to suggesting provision of the option for #1 or #2 controlled by a simply named user controllable parameter, and expressing a (minor) preference for #2 (as current) as the default.

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 20:27 Fri 28 Jun 2013

[url=http://fortheloveofport.com/ftlopforum/viewtopic.php?p=87904#p87904]Here[/url] Glenn E. wrote:I prefer the alternative. I just find it easier to have all of the placemats together and all of the TN sheets together.

PhilW
Dow 1980
Posts: 2696
Joined: 14:22 Wed 15 Dec 2010
Location: Near Cambridge, UK

Re: Software that makes placemats

Post by PhilW » 10:33 Sat 29 Jun 2013

jdaw1 wrote:
[url=http://fortheloveofport.com/ftlopforum/viewtopic.php?p=87904#p87904]Here[/url] Glenn E. wrote:I prefer the alternative. I just find it easier to have all of the placemats together and all of the TN sheets together.
We have a difference of opinion; neither unusual nor problematic.
suggesting provision of the option for #1 or #2 controlled by a simply named user controllable parameter
Whichever method is determined as default, can we please have a simple clear parameter to allow straightforward selection of the other method for if/when preferred?

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 11:34 Sat 29 Jun 2013

PhilW wrote:Whichever method is determined as default, can we please have a simple clear parameter to allow straightforward selection of the other method for if/when preferred?
There are parameters giving quite detailed control over the page order. Generally, for one-session tastings, the default is good. That starts with the page types that have page-ordering 1: glasses, TNs, vote recorders; the cork displays; and the pre-pours. These are sorted by paper size. Then glasses and TNs, sorted by NameNum (i.e., by person), and within that, innermostly, Glasses sheets in order, then TNs in sheet order. Then the vote recorders; then the cork displays; and then the pre-pours.

Next, with default page ordering 100, the place names (coming late to facilitate early folding); then with default page-order 200 the decanter labels, which need cutting and gluing; then (300) the stocky labels, as even if the same paper size, they do need a change of printer supplies.

But everything is flexible. So changing the page-ordering for the non-decanter-label glasses, PageOrderingNonDecanterLabelGlasses (an array the same length as GlassesOnSheets) to have 0s rather than 1s would make non-decanter-label glasses appear before anything else.

(Note the slight interaction with the paper-size sorting. If the glasses and TNs have the same page-order, they interleave. But the cork displays, for example, don’t interleave.)

PhilW
Dow 1980
Posts: 2696
Joined: 14:22 Wed 15 Dec 2010
Location: Near Cambridge, UK

Re: Software that makes placemats

Post by PhilW » 14:30 Sat 29 Jun 2013

The name PageOrderingNonDecanterLabelGlasses is either confusing, or I need to RTFM... "non-decanter-label glasses" as opposed to, presumably "decanter-label glasses"?

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 15:11 Sat 29 Jun 2013

PhilW wrote:as opposed to, presumably "decanter-label glasses"?
Well, yes. The decanter-label sheets, are just glasses sheets, without painting the Circlearrays, nor the water boxes, nor other inapposite decoration. The decanter labels are a variant of the glasses pages, rather than being a fully different page type.

E.g., see the first and penultimate pages of the placemats used on 26th and 27th Dec 2007.

Edit: now you’ve mentioned it, I suppose that I could do some renaming of parameters and whatnot to ‘pretend’ that the page types are different. That wouldn’t be too painful.

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 11:48 Fri 19 Jul 2013

Rays: algorithm help please

For Chris Doty’s most recent tasting in his ThirstyThirdThursdays series, I made the placemats. /Rays was deffed to true.

For the first go (well, the first of the goes relevant for these purposes), the parameter RaysLinesPerGlass was at its default value of 48, so one line every 360°÷48 = 7½°. 
Image
To the right of glass ii this looks good. But between ii and v this is a dog’s breakfast, with two problems visible.
• There are too many long-ish straight lines connecting ii and v.
• There is also a tangle, with a straight line coming straight out of v and colliding with ii, naughtily crossing lines. Yuck.


So I tried /RaysLinesPerGlass 60 def, so one line every 360°÷60 = 6°. 
Image
Much better, and this was the value used in the actual placemats.


Also, to feed the mind, here’s 72, one line every 360°÷72 = 5°. 
Image
Bad.


And 96, one line every 360°÷96 = 3¾°.
Image
Not as bad as some, but not right.


And finally 120, one line every 360°÷120 = 3°. 
Image
This seems to work.

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 11:48 Fri 19 Jul 2013

Any algorithm requiring such fiddling is a bad algorithm. To feed the mind, it works approximately as follows:

• Make a list of ends, so a list of length RaysLinesPerGlass × number of glasses on the page.

• Next make a list of intersections including all three types: 
— The ends have a start point and start direction. So for some pairs of ends on different glasses, they intersect.
— Also compute the first intersection between an ‘end’ and a circle;
— And between ‘end’ and edge.

• Sort list of intersections by distance (to edge or circle) or length (end to intersection to other end).

• Go down this list, starting at the shortest. For the shortest intersection with both ends unpainted, paint, and mark ends as painted.

• Painting is a straight line to circle or edge; or a cubic Bézier, the ends being the ends, both middle controls being the intersection.


This doesn’t work. For two touching circles, lines might intersect, or might touch the other circle before intersecting. And there can be a spare end, that in seeking a partner crosses other lines.

So this entire algorithm is to be discarded. Please suggest better. What is wanted is an algorithm that works in the general cases, rather than in a hodgepodge sub-set of those.

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 13:02 Fri 19 Jul 2013

An obvious improvement is to stop worrying about intersections. Two near-arbitrary ends can be connected. E.g., compute dist = distance between ends. Then the bézier’s middle two control points can be dist÷2 away from the two ends, travelling the obvious direction away from the circle. 

But, in the general case, distance is the wrong way to choose what to connect to what. E.g., see the following very small example with just two circles, each of which has two lines coming out, and the page being edgelessly infinite.
Image
Using distance to choose what connects would cause red to be connected to red, forcing green to cross.

PhilW
Dow 1980
Posts: 2696
Joined: 14:22 Wed 15 Dec 2010
Location: Near Cambridge, UK

Re: Software that makes placemats

Post by PhilW » 13:04 Fri 19 Jul 2013

jdaw1 wrote:Any algorithm requiring such fiddling is a bad algorithm.
My gut (not Dow 66) suggests that specification that for your current algorithm, using any of the diamond packing styles, RaysLinesPerGlass must be a multiple of 60 to ensure no problem.

I would attempt to re-state your problem as being to: find a solution (for the general case) for any number of circles in any position, to connect RaysLinesPerGlass points on each circle to any other point (except on one on it's own circle?) by a path without any path crossing another path and without traversing the inside of any circle, and then (optionally) allowing line deviation/spacing for space-filling is highly complex.

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 13:08 Fri 19 Jul 2013

PhilW wrote:My gut (not Dow 66) suggests that specification that for your current algorithm, using any of the diamond packing styles, RaysLinesPerGlass must be a multiple of 60 to ensure no problem.
For every possible aspect ratio? Really?
PhilW wrote:highly complex.
Not the answer I really wanted. That is, not the answer that I wanted to be true.

PhilW
Dow 1980
Posts: 2696
Joined: 14:22 Wed 15 Dec 2010
Location: Near Cambridge, UK

Re: Software that makes placemats

Post by PhilW » 13:11 Fri 19 Jul 2013

But, in the general case, distance is the wrong way to choose what to connect to what.
Agreed, though it seems a reasonable initial starting point. On selecting all subsequent lines, you could (theoretically) perform validation checks, such as to ensure that for any new enclosed areas formed bounded in part by the new line, that the total number of points enclosed by the existing lines and the new line are (a) even and (b) no more than 50% of those points are on any one circle; but this would seem to be becoming over-complex.

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 09:27 Mon 22 Jul 2013

Thank you. Being forced to describe the problem helped a lot, as did the subsequent discussion. I now have an algorithm explanation to follow later.

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 18:38 Mon 22 Jul 2013

The new algorithm works as follows.

• Create an array of ends of rays, of length NumRayEnds. This array is to hold multiple fields, including X and Y (start point), dX and dY (start direction), Angle (also start direction), and the glass number from which originating. Another field is an array of distances to other ray ends, each of which is of length NumRayEnds.

• Populate the distances, being a task O(n²). The definition of distance is slightly intricate. Compute the distance from start to start as the crow flies. The knot points will be half this crow distance from each end, of course in the direction implied by the relevant dX and dY. The ‘distance’ is deemed to be the sum of the distances between the knot points (the interesting bit of which is the central section, between the two interior know points).

• Create another field, sorted distances, pointing to the former array. (So for ray end i, let the first element of the sorted array be j, then the closest array end to i is j.)

• If i is also the closest array end to j, mark this pair as to be painted. (It probably will be painted.) Mark both i and j as painted, and repeat searching for new i and j that are the closest unpainted ends to each other.

• Repeat search till exhausted.

• It might be that j is closed to i, k closest to j, and i closest to k. So repeat the above, with a tolerance: if j closest to i, and i within Tolerance of being closest to j, repeat painting trick.

• Double tolerance, repeat. Repeat.

• Various i-j lines have been marked to be painted. That can still have intersections.
Image

• So take all the lines connecting circles ii and v (WLOG). Compute the angles measured from the line connecting the centres of the circles; cut all the lines; separately sort the two lists of angles; re-connect. That detangles the two-circle problems.
Image

So the earlier problem of lines not intersecting has gone. And some of the tangled lines have been de-tangled particularly those of the form shown in the small counter-example above, repeated below.
jdaw1 wrote:Image
But that hasn’t eliminated all possible problems with tangling.
Image

PhilW
Dow 1980
Posts: 2696
Joined: 14:22 Wed 15 Dec 2010
Location: Near Cambridge, UK

Re: Software that makes placemats

Post by PhilW » 09:33 Tue 23 Jul 2013

Clarification needed on bullets 2/3/4 please (first half of 2 is fine; second half of two, and subsequent/consequent actions in 3/4 not understood).

In no way attempting to derail the current new method, I did have some further thoughts on possible alternate method; not fully formed, but elaborated below in case it includes/provokes any further useful ideas. Possible method:
(1) Consider the C circles as points (centre locations only) initially, with N points per circle required.
(2) Conceptually, fully interconnect all points directly, allowing page-edge wrapping.
(3) For each circle-circle connection, consider whether use of circles rather than points would mean there were no path between the circles; if so, remove that link. This would conceptually leave a partially direct connected map, with each circle likely to have at least three, but likely more connections. These are effectively a list of the non-crossing paths available, so now we have to simply define the "width" of those paths, i.e. the number of lines (roughly in parallel) joining the edges of each circle to another.
(4) For each circle, now assign a "width" to each line; this I haven't fully though through. An initial approach would be to start with the circle with the lowest number of circle-circle connections, and evenly assign N/num_connects to each one. Then iterate for each other circle with lowest number of currently undefined widths, until all are assigned.
(5) Now create circles with points. Connect first shortest path, and then assign all other connections based on widths rotationally. Repeat for all other circles.

Am not sure whether that is clear enough without either a lot more explanation or some pictures which I don't have time for right now; decided to post anyway in case provokes thought.

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 15:52 Tue 23 Jul 2013

PhilW wrote:Clarification needed on bullets 2/3/4 please (first half of 2 is fine; second half of two, and subsequent/consequent actions in 3/4 not understood).
 
jdaw1 wrote:• Populate the distances, being a task O(n²). The definition of distance is slightly intricate. Compute the distance from start to start as the crow flies. The knot points will be half this crow distance from each end, of course in the direction implied by the relevant dX and dY. The ‘distance’ is deemed to be the sum of the distances between the knot points (the interesting bit of which is the central section, between the two interior know points).
The length of a cubic Bézier has no analytic form. And I don’t really care: what’s wanted is a sensible ranking. A cubic Bézier has four knot points, here labelled 0 1 2 3: the two ends, and two internal points. At knot 0 the direction of the curve is towards 1, and likewise at 3 towards 2.

So:
— Compute as-crow-flies 0-to-3.
— Knot point 1 must be directly away from the circle on which knot 0 sits. That specifies direction. Make the distance half the crow-flies distance.
— Likewise knot point 2 from 3.
— Deem distance to be sum of distances between knot points. Only 1-to-2 is non-trivial to calculate.
jdaw1 wrote:• Create another field, sorted distances, pointing to the former array. (So for ray end i, let the first element of the sorted array be j, then the closest array end to i is j.)
In effect we have a square grid of distances. Now create another array of arrays, called Sorted, and let’s consider Sorted(i). Populate this with 0, 1, 2, 3, !. Now sort it, such that Distance(i)(Sorted(i)(0)) ‰¤ Distance(i)(Sorted(i)(1)) ‰¤ Distance(i)(Sorted(i)(2)) ‰¤ !. So if j = Sorted(i)(0), then j is closest to i.
jdaw1 wrote:• If i is also the closest array end to j, mark this pair as to be painted. (It probably will be painted.) Mark both i and j as painted, and repeat searching for new i and j that are the closest unpainted ends to each other.
If the closest unpainted to i is j, and the closest unpainted to j is i, mark i”“j as to be painted (even if it might not be actually painted because of the later detangling).

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 16:12 Tue 23 Jul 2013

PhilW wrote:(2) Conceptually, fully interconnect all points directly, allowing page-edge wrapping.
A port tasting on a torus?! Somebody, once, printed the placemats double-sided, but a torus is even sillier.
PhilW wrote:(1) Consider the C circles as points (centre locations only) initially, with N points per circle required.
!
(3) For each circle-circle connection, consider whether use of circles rather than points would mean there were no path between the circles; if so, remove that link. This would conceptually leave a partially direct connected map, with each circle likely to have at least three, but likely more connections. These are effectively a list of the non-crossing paths available, so now we have to simply define the "width" of those paths, i.e. the number of lines (roughly in parallel) joining the edges of each circle to another.
I’m having a complete failure of understanding.
PhilW wrote:(4) For each circle, now assign a "width" to each line; this I haven't fully though through. An initial approach would be to start with the circle with the lowest number of circle-circle connections, and evenly assign N/num_connects to each one. Then iterate for each other circle with lowest number of currently undefined widths, until all are assigned.
Are you estimating the lead eigenvector of the circle-connection matrix? Err, why? And is the edge one place or many?
PhilW wrote:(5) Now create circles with points. Connect first shortest path, and then assign all other connections based on widths rotationally. Repeat for all other circles.
Are the circles the glasses circles in which case I don’t understand or not in which case I still don’t understand?

PhilW
Dow 1980
Posts: 2696
Joined: 14:22 Wed 15 Dec 2010
Location: Near Cambridge, UK

Re: Software that makes placemats

Post by PhilW » 08:54 Wed 24 Jul 2013

Thank you for the clarifications above; I now understand your proposed method. Ignore my suggested approach for now, until I have time to draw a few diagrams, or attend an offline and can wave my hands and/or draw on a napkin. Also, while what I am trying to propose would prevent tangling from occurring in the first place, if we can resolve tangling in your approach then mine is not required.

Going back to your description:
jdaw1 wrote:• It might be that j is closed to i, k closest to j, and i closest to k. So repeat the above, with a tolerance: if j closest to i, and i within Tolerance of being closest to j, repeat painting trick..
Is this possible, excepting the case of three equidistant locations?
jdaw1 wrote:• Various i-j lines have been marked to be painted. That can still have intersections.
Image

• So take all the lines connecting circles ii and v (WLOG). Compute the angles measured from the line connecting the centres of the circles; cut all the lines; separately sort the two lists of angles; re-connect. That detangles the two-circle problems.
Image

So the earlier problem of lines not intersecting has gone. And some of the tangled lines have been de-tangled particularly those of the form shown in the small counter-example above, repeated below.
jdaw1 wrote:Image
But that hasn’t eliminated all possible problems with tangling.
Image
I think your approach can be extended to perform the rest of the detangling:
(a) Determine initial list of all lines to be painted as per your method
(b) For each pair of circles in turn, consider every pair of lines which both have one end on each of these circles:
- Determine if the lines cross, and if so then perform detangle
(c) Now, for the whole page, consider every pair of lines in turn
- Determine whether the pair of lines crosses; if so, perform detangle on that pair
(d) If any detangling was performed, repeat (c) until done with no detangling required

Two additional notes on the above:
(i) To determine if the lines are tangled (in the full page case, where the lines are not connected to the same pair of circles at both ends) it will be necessary to account for quartic use in the path; using direct lines from end-knot-knot-end might be sufficient.
(ii) When detangling, if the two lines under consideration both have one end on the same circle, it is then the other points which must be swapped, irrespective of distance; otherwise after disconnection the reconnection should be based on nearest pair of free ends first.

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 11:32 Wed 24 Jul 2013

I have just realised how to generate interesting and varied misbehaviours: /Arch, and /PostsAndLintel. Examples below, /Arch on left, /PostsAndLintel on right.

Image Image

Image Image

Image Image

Image Image

Image Image

Image Image

Image Image

Image Image

Image Image

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 12:16 Wed 24 Jul 2013

A few posts back, in summarising the algorithm, I omitted to mention that after painting all curves, remaining unpainted ends are drawn to the edge because I thought they’d be in the corner.

Also, the testing whether curves intersect circles is showing an occasional imperfection. The code tests at t = 0.01, â…›, ¼, â…œ, ½, ⅝, ¾, â…ž, and 0.99. Perhaps the sixteenths could be added, which would be easy. The alternative is, for each curve, for each circle, if the bounding boxes of circle and knot points overlap, take the hexic polynomial of distance squared, differentiate once, solve that quintic numerically for 0 < t < 1, and substitute back in to the hexic.

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 13:06 Sat 27 Jul 2013

Some minor fixes implemented. Some bigger problems remain. These examples shown with RaysLinesToPaperEdge being true, and the margin marked with a grey box.

Image Image

Image Image

Image Image

Image Image

Image Image

Image Image

Image Image

Image Image

Image Image

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 21:59 Sat 27 Jul 2013

Blank post so images appear at start of page.

User avatar
jdaw1
Cockburn 1900
Posts: 20476
Joined: 15:03 Thu 21 Jun 2007
Location: London
Contact:

Re: Software that makes placemats

Post by jdaw1 » 22:00 Sat 27 Jul 2013

Blank post so images appear at start of page.

Post Reply