Software that makes placemats

[jdaw1]

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½°. 

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

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

Bad.


And 96, one line every 360°÷96 = 3¾°.

Not as bad as some, but not right.


And finally 120, one line every 360°÷120 = 3°. 

This seems to work.

[jdaw1]

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.

[jdaw1]

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.

Using distance to choose what connects would cause red to be connected to red, forcing green to cross.

[PhilW]

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.

[jdaw1]

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?

highly complex.

Not the answer I really wanted. That is, not the answer that I wanted to be true.

[PhilW]

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.

[jdaw1]

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.

[jdaw1]

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.


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


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.

But that hasn’t eliminated all possible problems with tangling.

[PhilW]

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.

[jdaw1]

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

 

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

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

• 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).

[jdaw1]

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

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

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

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

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:

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

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


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


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.

But that hasn’t eliminated all possible problems with tangling.

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.

[jdaw1]

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

[jdaw1]

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.

[jdaw1]

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

[jdaw1]

Blank post so images appear at start of page.

[jdaw1]

Blank post so images appear at start of page.

[jdaw1]

So there are two types of error.

The wrong circles can be joined:


Or the choice of circles is OK, but some within-circle reordering is required, of which the most general case yet seen is:

[jdaw1]

+WaterCountMaxRowLengths done.

Changed again. Parameters were specifying the size, and fitting in as many as possible. It better fits how I use the program to specify some measure of how many (WaterCountNumSideTriangle), and have the program choose the size based on that (though subject to WaterCountSizeMax).

[jdaw1]

Somebody in Belfast (probably Daniel) suggested that there should be one extra page, fixed and unchanging (bar fonts), being a check list for the organiser.

Item to go on checklist include:

• â–¢ Reserve venue.
  â–¢ Glasses: n people × m wines ⇒ at least nm recently cleaned glasses.
  â–¢ Print and bring placemats.
  â–¢ Bring sample jars.
  â–¢ Bring T-corks.
  â–¢ Bring a good corkscrew.
  â–¢ Bring a decanting funnel.
  â–¢ Bring muslin or coffee filter.
  Also:
  â–¢ Invite JDAW.

Presumably the list was to be longer than this what else?

Please could that Belfast person say what else is to go on the list, and please could others comment on the idea.

As items are suggested I’ll edit this post.

[djewesbury]

Somebody in Belfast (probably Daniel) suggested that there should be one extra page, fixed and unchanging (bar fonts), being a check list for the organiser.

Item to go on checklist include:

• â–¡ Invite JDAW
  â–¡ Glasses: n people × m wines ⇒ at least nm glasses, which have been recently cleaned.
  â–¡ Room hire.
  â–¡ Print and bring placemats.

Presumably the list was to be longer than this what else?

Please could that Belfast person say what else is to go on the list, and please could others comment on the idea.

As items are suggested I’ll edit this post.

I think it was Derek. Interestingly I had just written glasses = people x ports when you edited your post.

Perhaps
â–¡ Bring 'All-Eventualities Port Kit': sample jars / T-corks / good corkscrew / decanting funnel / muslin

[DRT]

I think it was Derek.

Guilty.

[jdaw1]

List updated.

Though echoing the suggestion, I’m not convinced by it. Often it isn’t the organiser who prints the placemats. And often enough the person who prints the placemats doesn’t really look at them until set-up time, that is, until it is too late. So I’m not (yet) convinced of the merits of the extra page.

[Glenn E.]

+1

I doubt I would use the feature as printing placemats is one of the items on my list.

Sent from my Galaxy Nexus using Tapatalk 2

[PhilW]

Though echoing the suggestion, I’m not convinced by it. Often it isn’t the organiser who prints the placemats. And often enough the person who prints the placemats doesn’t really look at them until set-up time, that is, until it is too late. So I’m not (yet) convinced of the merits of the extra page.

I probably wouldn't use this on the placemat sheets, as I'd rarely create and certainly never print without having done all the other tasks. However, such a list could be a useful sticky post somewhere (In Organising tastings sub-forum, probably), both as reminder-checklist but perhaps especially for someone who hasn't organised a tasting before?

[jdaw1]

A variant. Open the bell stickies, and observe that on each page of sticky labels (pages at the end) that there is a little note that can be opened. That note doesn’t print. Should there be, top-left of first page, such a sticky note, that opens to a list of things to consider remembering?

Though proposing this variant, my enthusiasm is only slight (though slightly more than for a extra whole page). However, it has the merit of being very easy to do.

[DRT]

This suggestion came about as a result of Daniel failing to remember to order glasses at a new venue. Both parts of that scenario are very rare events. Whilst pleading guilty to being the one who made the suggestion I must confess that my enthusiasm for it is very low.

Perhaps we should simply add a check list to this thread?

[djewesbury]

I agree with Derek. Having a checklist available somewhere is handy. Including on the placemats is unnecessary.

[jdaw1]

Perhaps we should simply add a check list to this thread?

Done.

[djewesbury]

Sorry. I suggest that

â–¢ Glasses: n people × m wines ⇒ at least n × m recently cleaned glasses

is insufficiently clear. Spares are needed for stink, breakages and bonus bottles. Perhaps a fraction of n × m can be found that is a correct number of spares?

[jdaw1]

insufficiently clear. Spares are needed

â–¢ Glasses: n people × m wines ⇒ at least n × m recently cleaned glasses, plus spares.

[jdaw1]

At Daniel’s request, www.jdawiseman.com/papers/placemat/page ... dvice.html has been updated. It now includes the following chart.

All page sizes are assumed to have margins of 30 points ! ≈ 0.42″ ≈ 10.6 mm. On the chart colours are pages sizes (  A4 in dark blue  ,  A3 in light blue  ,  US Letter = 8½″×11″ in red  ,  US Legal = 8½″×14″ in brown  , and  US Ledger = 11″×17″ in orange  ). The various marker shapes are the classes of elements of PermittedPackingStyles. The thick lines show the largest for each page size, these being reached or almost reached by the default value of PermittedPackingStyles. The thin lines are the values for /PostsAndLintel, assuming that the flag /CentralGlasses is at the default of 0.

Making the chart uncovered some obscure bugs, so was worth doing. (Well, uncovering the bugs in my code was worth doing. Uncovering those in Excel was fruitless pain.)

Comment welcomed.

[jdaw1]

Despite a minimal amount of waste, having 2 sets to each sticker sheet (with a blank column) means that certain people do not have to juggle two individual (and fiddly) strips of stickers during the tasting. For some reason i adopted Ray's stickers last year and had to deal with this - was not ideal. If the blank column could be the middle column, that would be perfect in terms of a quick "chop and distribute". Obviously disregard if it requires a lot of code.

How should this be parameterised?

As a reminder, the current StickyLabels parameters are:

Code: Select all

/StickyLabelsNumCopies 0 def
/StickyLabelsTypes [0 1] def

/StickyLabelsPaperType {[/A4 /A4] StickyLabelsTypeThis get} def
/StickyLabelsByNameWhichReplaceCirclearrays {StickyLabelsWithPagePortraitNumRows StickyLabelsWithPagePortraitNumCols mul 24 gt} def
/StickyLabelsWithPagePortraitNumRows {[4 13] StickyLabelsTypeThis get} def
/StickyLabelsWithPagePortraitNumCols {[2 5] StickyLabelsTypeThis get} def
/StickyLabelsWithPagePortraitGapL 12 def
/StickyLabelsWithPagePortraitGapR 12 def
/StickyLabelsWithPagePortraitGapT {[36 31] StickyLabelsTypeThis get} def
/StickyLabelsWithPagePortraitGapB {[36 31] StickyLabelsTypeThis get} def
/StickyLabelsWithPagePortraitGapBetweenRows 0 def
/StickyLabelsWithPagePortraitGapBetweenCols 8 def
/StickyLabelsOrientationAutomatic true def  % of labels, not of paper. Boolean.
/StickyLabelsOrientation /Landscape def  % of labels, not of paper. /Landscape /Portrait. Ignored if StickyLabelsOrientationAutomatic.
/StickyLabelsColumnsChangeFaster {[true false] StickyLabelsTypeThis get} def
/StickyLabelsFirstPageStartPosition 0 def
/StickyLabelsPaddingWithPagePortraitTB {[12 6] StickyLabelsTypeThis get} def
/StickyLabelsPaddingWithPagePortraitRL {[6 3] StickyLabelsTypeThis get} def
/StickyLabelsReverseOrder false def
/StickyLabelsRemoveDuplicatesByWithinTitles true def
/StickyLabelsSortByWithinTitles true def

[PhilW]

How should this be parameterised?

I'm going to have to read the manual to understand the current parameters... One simple suggestion could be:

/StickyLabelPadWithBlank true def % true, false
/StickyLabelPadLen 12 def
/StickyLabelPadAfter odd def % odd, even, all, none

This would allow addition of padding after label set 1,3,5 etc (middle columns on 5-column sheets) or after 2,4,6 (right column on 5-column sheets).

[jdaw1]

Hmm. How about a boolean StickyLabelNewPageAfter, intended to contain arbitrary code?

[jdaw1]

Hmm. How about a boolean StickyLabelNewPageAfter, intended to contain arbitrary code?

That suggests StickyLabelNewColOrRowAfter, which doesn’t quite allow a blank row or column. Hmm. Maybe an integer StickyLabelColOrRowEndings, 0 being do nothing, 1 starting a new one, 2 starting a new one with a skip, etc. That works, but is uglier than pretty. Hmm.

And forcing the parameter to contain code, probably complicated, limits usage to me. Yuck.

[PhilW]

How about /StickyLabelsAllowAcrossPages which when defined as true works as currently, but when false you calculate how many attendees' labels will fit on one page, and then pads the rest? Padding could be after, or equally spaced between (the latter woul provide for RAYC's request.

[jdaw1]

How about /StickyLabelsAllowAcrossPages

Oooh, missus, very good. And /StickyLabelsAllowAcrossColumsnOrRows.

Edit: both would have to be ignored when things are too big. When things have to flow past a column/row/page, it must make an effort to minimise the number of undesirable breaks. Perhaps better expressed with opposite booleans, !Eschew! rather than !Allow!.

[jdaw1]

Done, as StickyLabelsAvoidAcrossColumnsOrRows and StickyLabelsAvoidAcrossPages, both of which are ignored unless StickyLabelsByNameWhichReplaceCirclearrays is true.

[jdaw1]

(I tried to add a comment (‟Oeneophiles desirous of the placemats might like to know that they were made using the free program at http://www.jdawiseman.com/placemat.html”) but it wouldn’t let me create an account except via Facebook. So I couldn’t.)

[djewesbury]

You have a twitter account. You can sign in with that as well. Or shall I?

[jdaw1]

You have a twitter account. You can sign in with that as well. Or shall I?

I dislike cross-sign-in. So I tried to create an account, which seemed to require FB, which in turn seems to require all your private information, and the right to do anything with it (also disliked). If you can and are willing to cope, please do so.

[djewesbury]

Ah yes. I see what you mean. Having logged in via Twitter, asking me for my Facebook account details seems unnecessary.

[jdaw1]

Roy Hersh has drawn my attention to the ‟competition” at winefolly.com/tutorial/wine-placemats/.

Different, and not without merit, but I prefer mine. Comments welcomed.

[djewesbury]

Roy Hersh has drawn my attention to the ‟competition” at winefolly.com/tutorial/wine-placemats/.

Different, and not without merit, but I prefer mine. Comments welcomed.

Fussy and didactic. Also, how can you read what's under the glass? Maybe for beginners or a taught class but otherwise not liked.

[Glenn E.]

Meh. Might be useful for a beginner's class on wine tasting, but far too fussy for the kinds of tastings that we hold.

[DRT]

JDAW's placemats win hands-down.

[djewesbury]

Apart from anything else, how are you supposed to write in all those spaces on the placemats Roy sent, once you have glasses in the way..?

[jdaw1]

Horses for courses. For somebody rather shy and uncertain, wanting to have a small informal event with a few friends perceived as non-expert, it could provide structure and thereby confidence. For our needs, and in particular our scale of tastings, not so much.

What I found surprising is that they are available in only 8½″×11″, not A4. Yes, Americans can be rather parochial a side-effect of living in a big country but a wine person should know that there is a rest of the world, and it uses A4.

the placemats Roy sent

Roy didn’t really send them; he drew my attention to some made by a third party, not obviously endorsing or criticising.

[jdaw1]

I did like the rating system, which could be added to my TN pages (perhaps for only some people?):

but in extracting this detail from the page noticed the grey speckles. What are they for? To make the paper less white, so one is less able so see the colour of the wine?

The branding is also a bit OTT: I see seven mentions of WineFolly.