Recent

Author Topic: [Answered] algorithms: which method or operator must i use??  (Read 10464 times)

ADMGNS

  • New Member
  • *
  • Posts: 30
  • keep it simple and smart
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
« Last Edit: October 14, 2021, 04:38:45 pm by ADMGNS »

winni

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


Think about this:

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: 1215
  • 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.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

winni

  • Hero Member
  • *****
  • Posts: 3197
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: 3197
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: 1215
  • 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.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

speter

  • Sr. Member
  • ****
  • Posts: 345
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. :)

speter

  • Sr. Member
  • ****
  • Posts: 345
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. :)

ADMGNS

  • New Member
  • *
  • Posts: 30
  • keep it simple and smart
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

ADMGNS

  • New Member
  • *
  • Posts: 30
  • keep it simple and smart
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


ADMGNS

  • New Member
  • *
  • Posts: 30
  • keep it simple and smart
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


alpine

  • Hero Member
  • *****
  • Posts: 1038
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.

"I'm sorry Dave, I'm afraid I can't do that."
—HAL 9000

VTwin

  • Hero Member
  • *****
  • Posts: 1215
  • 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.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

BobDog

  • Sr. Member
  • ****
  • Posts: 394
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');
  201.   readln;
  202.   closegraph;
  203.  
  204. end.

MarkMLl

  • Hero Member
  • *****
  • Posts: 6676
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
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

 

TinyPortal © 2005-2018