math/algorithm to find a rectangle and a circle in a picture

[sharikon]

wow, im impressed you actually read all that thanks !

To start I'm just looking at your rectangle case. One particularly nasty case for your algorithm is a perfect diamond, with the red and purple points placed in such a way that the blue and green overlap each other. Your algorithm would detect a square instead of a diamond. I say this is particularly nasty, because you could try a "fix" where you check to make sure none of the green dots are colinear with pairs of blue dots.

it wont be a perfect diamond... i'm doing this for something specific...
i have an iphone , and im playing pool there, and i wanted to see if i can write something that will help me "cheat" in it, for my program to show me where should i hit the ball to get it in to the pocket. for me to create something like that would be a great challenge. now its more for the challenge of making it work then to really have it for the pure ability to "cheat".
i have a webcam above the iphone and i'm analyzing the frames.
the iphone is rectangle, and yes ofcourse i can place it in such way that i wont have to really deal with rotated rectangle. but again , this developed into a challenge and the "how cool it would be if it will trace the iphone rectangle screen on my computer screen with a webcam" factor.

I don't think this algorithm can be easily saved. There are too many edge cases. Once you reach a side, can you scan around to see how that side is tilted? If so you could use only 1 red and 1 purple point, perhaps even making them the same point, scan in all 4 directions out from that point, and at the worst I think you'd only hit 3 out of 4 sides of the rectangle. Finding the 4th would take one more scan.

i actually started in my mind with exactly what your suggesting, but the webcam gives me 30 fps, and i knew that scanning this way will be slower, so i tried to think of quicker ways, and the only solution is math.

do you still think i should try the scan method ?

For the circle, your algorithm will work fine--unless the ellipse can be rotated. You could probably do it with one fewer scan and more math. Any 3 points on a circle give enough information to find the equation of that circle (slog through the algebra if you want to prove it rigorously), which gives you the radius without having to scan from the center. You should be able to do the same with the ellipse.

the circle is actually the balls , so it wont be rotated elliptical shape...

[jemidiah]

I would imagine that, after colliding with a black spot, scanning around to determine the slope of the line you hit wouldn't take too long for your computer. You could always ignore most of the frames; 30 is probably overkill, depending on exactly what you want to do.

The only other fool-proof solution I can think of is to scan along a larger number of lines, using more complex reasoning that doesn't seem worth it.

[sharikon]

ok , i'll try both, see how it goes, but little later, i dont have time now...

thanks for responding!!

i'll keep u informed and post the full project when im done