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?