Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

Author Topic: algorithms: which method or operator must i use??  (Read 8481 times)

• New Member
• Posts: 12
algorithms: which method or operator must i use??
« on: May 15, 2021, 08:52:02 pm »
hello,

problem: i have some circles. you think them as pulleys, and i want turn around a vee belt them. so, how can i detect the tangent points that all circles rotate regularly. please see attachment.

i've tried to use internal and/or external tangent points of two circles, but it doesnt work properly.

thank you

winni

• Hero Member
• Posts: 2419
Re: algorithms: which method or operator must i use??
« Reply #1 on: May 15, 2021, 09:46:20 pm »
Hi!

Use the angle from the Center and center of a cirle.
Compute the length between those 2 points.
Add or subtract the radius of the circle.
There you are at the tangential point.

Winni

VTwin

• Hero Member
• Posts: 1035
• Former Turbo Pascal 3 user
Re: algorithms: which method or operator must i use??
« Reply #2 on: May 15, 2021, 10:47:42 pm »
Interesting. Each adjacent pulley's tangent will have the same slope.

There must be more information on the input values.

Is this a homework assignment?
“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.0
macOS 10.13.6: Lazarus 2.0.12 (64 bit Cocoa)
Ubuntu 18.04.3: Lazarus 2.0.12 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.0.12 (64 bit on VBox)

winni

• Hero Member
• Posts: 2419
Re: algorithms: which method or operator must i use??
« Reply #3 on: May 15, 2021, 10:49:47 pm »
Hi!

Here is a first solution with a canvas and integer coordinates.

It should help you as a start base.

Winni

winni

• Hero Member
• Posts: 2419
Re: algorithms: which method or operator must i use??
« Reply #4 on: May 15, 2021, 11:03:54 pm »
@Vtwin

This is homework.

For a real live computing you must first know:

* Is the "rope" on the next roll outside or inside
* You need the angle between  circle n and circle n+1
* then you can decide at which angle leaves roll n and start at roll n+1 - the tangential points left and right
* for the difference between the  two tangential points you have to compute a circle segment for the "rope"

Sound more like technical engeneering for bginners ...

Winni

l

VTwin

• Hero Member
• Posts: 1035
• Former Turbo Pascal 3 user
Re: algorithms: which method or operator must i use??
« Reply #5 on: May 15, 2021, 11:12:37 pm »
Indeed winni. Very nice, that looks like a great start.

As you say, there is more here. The lower left pulleys don't make physical sense. Perhaps the OP can fix this.
“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.0
macOS 10.13.6: Lazarus 2.0.12 (64 bit Cocoa)
Ubuntu 18.04.3: Lazarus 2.0.12 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.0.12 (64 bit on VBox)

speter

• Full Member
• Posts: 213
Re: algorithms: which method or operator must i use??
« Reply #6 on: May 16, 2021, 02:17:37 am »
Calculate the centre of the whole; then to work out whether the "rope" goes out or in, "draw a line" between the pullies on either side, if the middle pully is "inside" this line the "rope" will be "inside"...

cheers
S.
I climbed mighty mountains, and saw that they were actually tiny foothills.

Laz 2.0.10 / FPC 3.2.0 / Windows 10 (64bit)

speter

• Full Member
• Posts: 213
Re: algorithms: which method or operator must i use??
« Reply #7 on: May 16, 2021, 02:27:22 am »
Further to my previous post, look at the diagram below.

In the top-left corner, the line between the adjoining pullies crosses the line from the centre - so the "rope" should be outside.

In the bottom-left corner, the line between the adjoining pullies does NOT cross the line from the centre - so the "rope" goes on the inside...

cheers
S.
I climbed mighty mountains, and saw that they were actually tiny foothills.

Laz 2.0.10 / FPC 3.2.0 / Windows 10 (64bit)

• New Member
• Posts: 12
Re: algorithms: which method or operator must i use??
« Reply #8 on: May 16, 2021, 04:34:30 am »
hello again,

1) i want to thank everbody.

2) this is not a homework. this is an kind of experiment on smoothing polylines. recently, i sent an article to CodeProject site https://www.codeproject.com/Articles/5301415/HotPoints-A-New-Method-for-2D-Polyline-Vertex-Smoo so, i'm trying to find another simple methods.

3) about speter's solution.. think that the order of cirles not circular-ish, maybe linear-ish.. so, this is not a general solution, i think.

4) probably we need a new operator, like cross product..

5) i,m gonna working on it..

thanks

• New Member
• Posts: 12
Re: algorithms: which method or operator must i use??
« Reply #9 on: May 16, 2021, 04:49:13 am »
sorry, i,ve forgotten to attach the new picture

• New Member
• Posts: 12
Re: algorithms: which method or operator must i use??
« Reply #10 on: May 17, 2021, 02:41:05 am »
dear guys,

i think, i,ve solved the problem. but.. to be honest, this is not a robust solution, but also it is a workaround..

yet another, in this version, there are 2 confusing issues.. it runs for only circles that have equal radii. and, in the middle of calculating, the radii of next one's radii has to greater than current one's radii. i dont know why.. perhaps it is a mystery

please see the attachment..

you're welcome valuable suggestions everytime..

thank you

y.ivanov

• Full Member
• Posts: 132
Re: algorithms: which method or operator must i use??
« Reply #11 on: May 17, 2021, 03:30:48 pm »
Just an idea (see the picture):
In short, the idea is to reject intersecting tangents since they're making concaves instead of bulges.
• You can start with first three circles A, B, C and calculate their inner and outer tangents (8 line segments)
• Check which tangents of B,C doesn't intersects with tangents from A,B. In the picture these are the green ones
• Then you have 2 candidate tangents (green ones).
• Take the circles B,C,D (D is next one)
• Calculate 4 tangents from C to D
• Intersect 2 tangents from B to C with 4 tangents from C to D. Reject those which intersect
• Now you should have just one tangent (from greens) left for B,C and two for C,D. Draw the green one
• Take C for B, D for C and next circle for D. two tangents for C,D now are for B,C
• Repeat from 3.2 until tangent is drawn between starting two circles (on picture: A,B, one of the black segments)

There is a cases in which there is no intersecting tangents, as on the second picture, but then I think you can just take two of them (one inner and one outer as the black ones on the first picture) and continue.

VTwin

• Hero Member
• Posts: 1035
• Former Turbo Pascal 3 user
Re: algorithms: which method or operator must i use??
« Reply #12 on: May 18, 2021, 11:55:42 pm »
I have not dug deeply into your code, but appreciate the very nice working program.

If I understand correctly, _2CExtTangents calculates the "external similitude center".
This will be undefined if the circles have the same radius. In your code the "eps" prevents a divide by zero. Perhaps this is the reason for the required +1.

This is still puzzling however, if I change +1 to -1 it fails, as it does using random radii.

As a side note, it should only be required to call "Randomize" once, probably in FormCreate.

« Last Edit: May 19, 2021, 12:05:36 am by VTwin »
“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.0
macOS 10.13.6: Lazarus 2.0.12 (64 bit Cocoa)
Ubuntu 18.04.3: Lazarus 2.0.12 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.0.12 (64 bit on VBox)

BobDog

• Jr. Member
• Posts: 78
Re: algorithms: which method or operator must i use??
« Reply #13 on: May 19, 2021, 12:48:50 pm »

Using a reference point (centre of screen say), the function tangent returns the line segment (tangent) between circle C and D.
Circle C is the main one, you have options far, near (with reference to the reference point leaving circle C), and same and cross where same=tangent to D on same side as C, cross=cross over sides, as in the demo.
I have automated the cross overs in the demo, normally you might use a case statement to write explicitly your requirements at each circle.
automating the cross overs is good if the circles are reasonably spaced and no circle is too far out (via the random positions).
Code: Pascal  [Select][+][-]
1.
2. program tangents;
3.
4. uses
5.   Math,
6.   graph;
7.
8. type
9.   v2 = object
10.   public
11.     x: double;
12.     y: double;
13.   end;
14.
15. type
16.   Circle = object
17.     ctr: v2;
18.     r: integer;
19.     col: integer;
20.   end;
21.
22. type
23.   linesegment = object
24.     s, f: v2;
25.   end;
26.
27. const
28.   same = 0;
29.   cross = 1;
30.   near = 2;
31.   far = 3;
32.
33. function dot(v1: v2; v3: v2): double;
34. var
35.   d1, d2, v1x, v1y, v2x, v2y: double;
36. begin
37.   d1 := Sqrt(v1.x * v1.x + v1.y * v1.y);
38.   d2 := Sqrt(v3.x * v3.x + v3.y * v3.y);
39.   v1x := v1.x / d1;
40.   v1y := v1.y / d1;
41.   v2x := v3.x / d2;
42.   v2y := v3.y / d2;
43.   exit(v1x * v2x + v1y * v2y);
44. end;
45.
46. function drawline(x: double; y: double; angle: double; length: double): v2;
47. var
48.   z: v2;
49. begin
50.   angle := angle * 0.0174532925199433;  //=4*atn(1)/180
51.   z.x := x + length * Cos(angle);
52.   z.y := y - length * Sin(angle);
53.   exit(z);
54. end;
55.
56. function isleft(L: linesegment; p: v2): integer;
57. begin
58.   exit(-Sign((L.s.x - L.f.x) * (p.y - L.f.y) - (p.x - L.f.x) * (L.s.y - L.f.y)));
59. end;
60.
61. function segmentintersections(L1: linesegment; L2: linesegment): integer;
62. begin
63.   if isleft(L2, L1.s) = isleft(L2, L1.f) then
64.     exit(0);
65.   if isleft(L1, L2.s) = isleft(L1, L2.f) then
66.     exit(0);
67.   exit(1);
68. end;
69.
70. function distance(a: v2; b: v2): double;
71. begin
72.   exit(sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
73. end;
74.
75. function tangent(C: circle; D: circle; flag: integer; position: integer; ref: v2): linesegment;
76. var
77.   z: array[0 .. 8] of linesegment;
78.   n, idx, a, b, i: integer;
79.   dst, dd: double;
80.   X, Y, Y2, v, v3: v2;
81.   CL, VL: linesegment;
82. label
83.   lbl;
84. begin
85.   n := 0;
86.   idx := 0;
87.   i := 0;
88.   dd := 0.0;
89.   dst := 0.0;
90.   if position = near then
91.     dst := 5000.0
92.   else
93.     dst := -5000.0;
94.
95.   for a := 0 to 360 do
96.   begin
97.     for b := 0 to 360 do
98.     begin
99.       v := drawline(C.ctr.x, C.ctr.y, a, C.r);
100.       v3 := drawline(D.ctr.x, D.ctr.y, b, D.r);
101.       X.x := (v.x - v3.x);
102.       X.y := (v.y - v3.y);
103.       Y.x := (c.ctr.x - v.x);
104.       Y.y := (c.ctr.y - v.y);
105.       Y2.x := (D.ctr.x - v3.x);
106.       Y2.y := (D.ctr.y - v3.y);
107.       if (Abs(dot(Y, X)) < 0.01) and (Abs(dot(Y2, X)) < 0.01) then
108.       begin
109.         CL.s := C.ctr;
110.         CL.f := D.ctr;
111.         VL.s := v;
112.         VL.f := v3;
113.         I := segmentintersections(CL, VL);
114.         if I = flag then
115.         begin
116.           dd := distance(v, ref);
117.           if (position = far) and (dst < dd) then
118.           begin
119.             dst := dd;
120.             idx := n;
121.           end;
122.
123.           if (position = near) and (dst >= dd) then
124.           begin
125.             dst := dd;
126.             idx := n;
127.           end;
128.
129.           z[n].s := v;
130.           z[n].f := v3;
131.           n += 1;
132.           goto lbl;
133.         end;//i
134.       end; //abs
135.     end; // a
136.     lbl: ;
137.   end; // b
138.   exit(z[idx]);
139. end;//function
140.
141. var
142.   s: linesegment;
143.   gd, gm: smallint;
144.   c: array of circle;
145.   z, rad, Count, n, nflag, cflag: integer;
146.   ref, d: v2; //reference point as screen centre.
147.
148. begin
149.   {==========  set up graph =========}
150.   gd := D8bit;
151.   gm := m800x600;
152.   InitGraph(gd, gm, '');
153.   if GraphResult <> grok then
154.     halt;
155.   SetTextStyle(SansSerifFont, HorizDir, 2);
156.   {===================================}
157.
158.   ref.x := 400;
159.   ref.y := 300;
160.   Count := 0;
161.   cflag := cross;
162.   nflag := far;
163.   // set up some random circles around the centre
164.   for z := 0 to 360 do
165.     if z mod 30 = 0 then
166.     begin
167.       setlength(c, Count + 1);
168.       rad := 170 + random(120);
169.       d := drawline(ref.x, ref.y, z, rad);
170.       c[Count].ctr.x := d.x;
171.       c[Count].ctr.y := d.y;
172.       c[Count].r := 30;
173.       c[Count].col := Count + 1;
174.       Count += 1;
175.     end;//for z
176.
177.   for n := 0 to high(c) - 1 do // draw the circles
178.   begin
179.     setfillstyle(solidfill, c[n].col);
180.     fillellipse(trunc(c[n].ctr.x), trunc(c[n].ctr.y), c[n].r, c[n].r);
181.   end;
182.
183.   for n := 0 to high(c) - 1 - 1 do    // tangents all the way round
184.   begin
185.
186.     if (n mod 2 = 1) then
187.     begin
188.       nflag := far;
189.       cflag := cross;
190.     end;
191.
192.     if (n mod 2 = 0) then
193.       nflag := near;
194.
195.     s := tangent(c[n], c[n + 1], cflag, nflag, ref);
196.     line(trunc(s.s.x), trunc(s.s.y), trunc(s.f.x), trunc(s.f.y));
197.   end;
198.   s := tangent(c[n + 1], c[0], cross, far, ref);   //last pair
199.   line(trunc(s.s.x), trunc(s.s.y), trunc(s.f.x), trunc(s.f.y));
200.   writeln('DONE . . .  please press return');
202.   closegraph;
203.
204. end.

MarkMLl

• Hero Member
• Posts: 2723
Re: algorithms: which method or operator must i use??
« Reply #14 on: May 19, 2021, 01:53:45 pm »
I've been watching this with interest. It's obviously not applicable to something like a printing press because of the possibilities of grazing contact and that the lines be allowed to cross, and the latter also prevents its being a common-or-garden Convex Hull exercise.

It would fit the bill rather well for the "Sprocket Problem" mentioned in "Cryptonomicon".

MarkMLl
Turbo Pascal v1 on CCP/M-86, multitasking with LAN and graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories