Software that makes placemats

Organise events to meet up and drink Port.
User avatar
jdaw1
Taylor 1900
Posts: 19816
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
Taylor 1900
Posts: 19816
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
Taylor 1900
Posts: 19816
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: 2510
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
Taylor 1900
Posts: 19816
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: 2510
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
Taylor 1900
Posts: 19816
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
Taylor 1900
Posts: 19816
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: 2510
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
Taylor 1900
Posts: 19816
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
Taylor 1900
Posts: 19816
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: 2510
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
Taylor 1900
Posts: 19816
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
Taylor 1900
Posts: 19816
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
Taylor 1900
Posts: 19816
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
Taylor 1900
Posts: 19816
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
Taylor 1900
Posts: 19816
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.

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

Re: Software that makes placemats

Post by jdaw1 » 22:00 Sat 27 Jul 2013

So there are two types of error.

The wrong circles can be joined:
Image

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

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

Re: Software that makes placemats

Post by jdaw1 » 12:53 Fri 16 Aug 2013

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

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

Re: Software that makes placemats

Post by jdaw1 » 21:42 Sat 09 Nov 2013

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.

User avatar
djewesbury
Graham’s 1970
Posts: 8153
Joined: 20:01 Mon 31 Dec 2012
Location: Belfast
Contact:

Re: Software that makes placemats

Post by djewesbury » 21:56 Sat 09 Nov 2013

jdaw1 wrote: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
Daniel J.
delete.. delete.. *sigh*.. delete...

User avatar
DRT
Fonseca 1966
Posts: 15020
Joined: 23:51 Wed 20 Jun 2007
Location: Chesterfield, UK
Contact:

Re: Software that makes placemats

Post by DRT » 22:41 Sat 09 Nov 2013

djewesbury wrote:I think it was Derek.
Guilty.
"The first duty of Port is to be red"

Ernest H. Cockburn

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

Re: Software that makes placemats

Post by jdaw1 » 23:23 Sat 09 Nov 2013

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.
Quinta do Vesuvio 1994
Posts: 3349
Joined: 22:27 Wed 09 Jul 2008
Location: Seattle, WA, USA

Re: Software that makes placemats

Post by Glenn E. » 00:55 Sun 10 Nov 2013

+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
Glenn Elliott

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

Re: Software that makes placemats

Post by PhilW » 09:42 Sun 10 Nov 2013

jdaw1 wrote: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?

Post Reply