CODEWITHSUNDEEP
algorithmcomputational-geometry
John Scofield
John Scofield

Reputation: 3

Come up with a method to find the smallest circle that covers two points with its center in x axis

Give two planar points p1=(a1,b1) and 􏰛p2=(a2,b2)􏰗 and a line y=0, design an algorithm to find the smallest circle that covers both points such that its center (x􏰖􏰍, 0)􏰗 lies on 􏰏y=􏰝0. There is no time or space requirement.

Although this problem seems simple, but I think it's kinda tricky to solve. Could you give some help? Thanks!

Upvotes: 0

Views: 182

Answers (1)

DrKoch
DrKoch

Reputation: 9782

If both points should lie on the circumfence of the circle:

  • find midpoint of [p1, p2]: midpoint := ((a1+a2)/2, (b1+b2)/2))
  • find line perpendicular to [p1, p2] in midpoint
  • find intersection of this line with x axis
  • this intersection is the midpoint of your circle

Edit

If both points should be part of the "filled" circle:

Find the x values of both points: a1, b1

If the center (found above) is within [(a1,0), (b1,0)] then you have the smallest circle

if the center found above is < a1 then move it to (a1,0)

if the center is > b1 then move it to (b1,0)

Upvotes: 1

Related Questions