Just how to examine if a factor is inside the convex hull of 2 circles?

Following my previous question, I'm asking yourself just how I can establish if a factor is within the convex hull of 2 circles (a boolean value). There's no worry screening if the factor remains in either of both circles, yet it can additionally be "in between" them and also I do not recognize just how to examine for that.

Seeing Wolfram MathWorld's write-up on Circle-Circle Tangeants, it appears that an inequation that examines if the factor gets on the inner side both exterior circle tangeants would certainly suffice, yet I'm worried my addressing abilities are also away to be able to transform the tangeant formulas right into a suitable inequality.

I'm specifying the convex hull of 2 circles making use of both facilities and also distances.

2019-05-04 18:54:12
Source Share
Answers: 2

You can first compute the four points of tangency, after that make use of the Point in Polygon algorithm to establish if your factor is inside the quadrilateral (this is thinking you have a shows relevant trouble)

Otherwise, as soon as you have actually located the 4 tangent factors, you can create 4 lines and also get 4 synchronised inequalities.

2019-05-08 04:40:48

The remedy to this trouble is without a doubt to examine whether the factor remains in among the circles or in the isosceles trapezoid established by the factors were circles touch the tangent lines. Nonetheless, without some treatment the formulas get unpleasant.

Allow's start with a circle at (x1', y1') of distance r1', a circle at (x2', y2') with distance r2', and also a factor (x', y') to examine. We might think that r1' goes to the very least r2'. By changing adhered to by turning adhered to by scaling this can be changed right into a less complex instance : a circle at (0,0) of distance r1, a circle at (1,0) of distance r2, and also a factor (x, y) to examine. We have : r1 =r1'/ D, r2 =r2'/ D,





and also $\alpha$ is the angle where (x2'- x1', y2'- y1') exists. (In C, there's a function atan2 that takes both works with of a factor and also offers the angle. In mathematics, atan does not actually compare factors symmetrical wrt (0,0).)

  1. If the factor remains in among the circles claim YES, or else proceed.
  2. If r1 =r2 after that return (0 < x < 1 and also |y | < r1), or else proceed. (At this factor the distinction in between distance Dr =r1-r2 is purely in between 0 and also 1.)
  3. If x < r1 Dr, claim NO.
  4. If x > 1 + r2 Dr, claim NO.
  5. If $x\Delta r + |y|\sqrt{1-{\Delta r}^2}>r_1$, claim NO.
  6. Claim YES.

There's just one point I made use of, actually, particularly that particular triangulars are comparable. Attract the tangent that touches both circles 'over'. Allow's claim that it converges the large circle at A = (x1, y1), the tiny circle at B = (x2, y2), and also the straight axis at C = (d,0). Allow's additionally write D = (0,0) and also E = (x1,0) and also F = (1,0) and also G = (x2,0). The comparable triangulars are ADC, AED, BFC, and also BGD. From ADC comparable to BFC you locate d = r1/Dr. From ADC comparable to AED you locate x1 = r1 Dr and also from BFD comparable to BGD you locate x2 - 1 = r2 Dr.

To examine that a factor gets on the appropriate side of a line write its formula as ax+ by+ c =0 and also change equal rights by inequality. (It's excellent to bear in mind that the vector $(a,b)^T$ is vertical to the line which the formula can be taken specifying all vectors/points whose scalar/dot item with a dealt with vector $(a,b)^T$ offers the constant c.)

Let me recognize if I screwed up once more :P

This is the old solution, which is incorrect as aimed by the first comment listed below. It begins with the very same makeovers (without offering information) yet after that it makes use of some line that is plainly not tangent to the circles.

Claim the first circle has the facility at (0,0) (otherwise, change the number) with distance r_1, and also the 2nd at (1,0) (otherwise, revolve the number and also range) with distance r_2. If your factor is (x, y) and also is not in among both circles, after that x have to be in between 0 and also 1 and also |y | has to go to the majority of r_1+ (r_2-r_1) x.

2019-05-08 03:31:47