2
$\begingroup$

I originally asked this here but I am struggling to take the concepts, particularly "Circumcenter", discussed there and apply it in my context. So here it is in my context...

I have a small robot that can "see" (via a camera) a partial arc (from a birds-eye view)

Therefore I know the height and the width of the square and therefore the width and height of the arc, I am sure there must be a way of approximating the circles centre?

What would be the quickest (not necessarily the most accurate) way of helping my robot find the centre.

In my head these are the steps of the problem:

  1. Break up the arc into evenly spaced vectors ?
  2. Work out the angle between the vectors
  3. Use this information to complete the circle ?
  4. Work out radius of circle
  5. Find the center of the circle

Basically I would love some input on this problem because I think i know

  1. ?
  2. Dot Product
  3. ?
  4. Add up the lengths of all the vectors to get circumference and then divide by pi, then divide by 2 (or divide by Tau : ) )
  5. I think this is where circumcentre comes in

Basically I feel I have some pieces of the puzzle but I am not sure how they fit together.

I am currently using python with OpenCV and you may have guessed, I am not great at understanding math unless its expressed in algebraic formula or code.

Here are some illustrive pictures to reference: enter image description hereenter image description here

$\endgroup$
3
$\begingroup$

First you need to understand the math, then you need to know how to program it.

So let's begin with the math. This is high school material, so I go through it quickly.

The math

Any two points you take on a circle make a line (of course). The line bisector of that line passes through the center of the circle. If you have two of such line bisectors that are not parallel, they collide at the center of the circle.

The reason that this happens is quite trivial, but if you don't know it, just accept it at this point.

Theory

That said, the line segments don't need to be far apart for their line bisectors to collide at the center of the circle. They could cross each other or they could share a point as one of their ends. In short, any pair of lines are ok as long as they are not parallel. Sharing one end point and having the other end point different can ensure that this is the case.

The programming

To do the programming, first you need three points on the circle (arc).

These three points don't need to be spaced out evenly. The more points you have and the farther they are from each other can increase your precision. Let's stick to three points at the moment.

How can you find three points? That's quite simple. Run three horizontal lines through your image and record where you cross the arc. There would be at least three collisions, but there could also be more.

Choosing points on the arc

Now choose three as you like, preferably the two farthest points and one that is closest to the middle. Then find their bisectors and see where they collide.

enter image description here

And that's it! You have your center.

As a bonus, if you find more points and have the time, you can increase your precision by calculating more candidate points for the center and simply average them. That would give you a smaller computation error. In the figure below, that would be the average of the points identified by the arrows:

enter image description here

Note that these points should have theoretically coincided, but due to computational error are a bit offset.

$\endgroup$
  • $\begingroup$ Fantastic explanation, i had recently come across the chord stuff but this is a reallly brilliant summary that adresses all my concerns with the method, and the horizontal line stuff is so much simpler then what i had in mind! Thanks $\endgroup$ – chrispepper1989 Dec 1 '14 at 8:04
  • $\begingroup$ @chrispepper1989, no problem. You could also throw in some vertical lines if you feel up it ;) $\endgroup$ – Shahbaz Dec 1 '14 at 10:08
0
$\begingroup$

I would recommend the following steps:

  1. Get slope of the arc (say m1,m2) at 2 random points on the arc (say p1,p2)
  2. Get slopes orthogonal to m1,m2 using m1*m1_oth = -1
  3. Use new slopes and point p1,p2 to get 2 lines
  4. Point of intersection of the lines is your center.

I believe this should not be computationally intensive. Haven't tried it though.

$\endgroup$
  • $\begingroup$ Is the kind of thing you meant? youtube.com/watch?v=YOJbWo41gU0 $\endgroup$ – chrispepper1989 Nov 28 '14 at 12:31
  • $\begingroup$ @chrispepper1989 yeah, similar to this. Getting the perpendicular bisector is an overkill. Just find point of intersection of the thes line perpendicular to the tangents at any two points on the arc. $\endgroup$ – sleeping_dragon Nov 29 '14 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.