Image Line Trace Math Help Hard To Explain

Question

Hi all, sorry for the confusing title, its really hard for me to explain what i want. So i created this image :)

Ok so the two RED dots are points on an image. The distance between them isnt important.

What I want to do is, Using the coordinates for the two dots, work out the angle of the space between them (as shown by the black line between the red dots)

Then once the angle is found, on the last red dot, create two points which cross the angle of the first line. Then from that, scan a Half semicircle and get the coordinates of every pixel of the image that the orange line passes.

I dnot know if this makes any sense to you lot so i drew another picture:

As you can see in the second picture, my idea is applied to a line drawn on a black canavs. The two red dots are the starting coordinates then at the end of the two dots, a less then half semicircle is created. The part that is orange shows the pixels of the image that should be recorded.

I have no clue how to start this, so if anyone has any ideas on how i can or on what i need to do, any help is much appreciated :)

EDIT. I have created this image in the hopes that it will make what i am trying to do clearer :)

Again sorry if this is confusing anyone as I really dont know how to explain it.

Answer 1

Hmm... I think I get what you're tying to do, but comment if I'm wrong.

I believe the blue dots aren't really needed. What I think you're suggesting is to simply scan around a point (red dot) in a circle, locate points of intersection to that circle and determine the angle of that intersection vs the angle a second point (the other red dot).

I presume you know how to calculate the angle between the two red dots, that's pretty simple.

There are a number of ways to calculate the intersection with the circle, the brute force method would be to apply an iterative formula like:

x = r * sin(t)
y = r * cos(t)

centered around your first red dot, where r is your scan radius.

Applying the formula to your pixel grid, you should be able to determine which pixels are solutions for both equations.

There should be at least 2 points that intersect your circle, I believe it should be fairly simple to eliminate the unnecessary ones (depending on the properties of the line you're tracing).

Now you can calculate the angle of that intersect point and your central red dot. Use that angle and the previously calculated angle between red dots to get what I believe you want.

EDIT: From an implementation standpoint, if your bitmap is sparse enough, it would be much more efficient algorithmically to put all the pixel coordinates in an array, ordered in some continuous fashion. This would make it much simpler to search for the corresponding pixel at a certain radius from your current pixel.

Answer 2

OK, so the opening angle is constant, and the transverse line is there only for construction. Good.

---

You want to use the Bresenham circle to select the points to be scanned.

First figure the end points. For that you do a little vector math like this

• Let (x, y) be the coordinate of the second red dot, R be the radius you with to scan at (you haven't specified this, but I assume that you know what it is), and theta be the angle of the line segment from the horizontal. (If you need help figuring theta, just say)
• The endpoints are (X_i, Y_i) for i in [+,-]. Where

 

X_+ = x + R*cos(theta + 70)  // angles expressed in degrees for ease here, 
Y_+ = y + R*sin(theta + 70)  // your language probably expects radians 
X_- = x + R*cos(theta - 70)  
Y_- = y + R*sin(theta - 70)  

Note that theta should run the whole circle (0--360 degrees or 0-2\pi radians).

Then you use the circle algorithm to pick pixels (which would be colored if you were drawing, but are copied in this case) which you put into an array in order. And Bjorn Strongingthearm's your uncle.

Answer 3

Just to clarify:

• You have two points A & B, and you need to draw an arc
• The arc should be a quarter circle (aka 'half a semicircle')
• The first point A is to be the centre / point of rotation for an arc
• The line defined by A & B should intersect the arc at its midpoint

Let's define the coordinates of point A as (Ax, Ay). Let's define the distance between A & B as r (the radius of our circle/arc)

So using basic formula for a circle, a point (x, y) will be on the circle when

(x-Ax)^2 + (y-Ay)^2 = r^2

Now you just need to limit this set to those points that are within your required quarter circle. I would suggest the easiest way to do this is to include points within a certain distance of the midpoint of the arc.

To do this, first work out the midpoint of the arc. Let point B be defined by (Bx, By), and then define point C as the midpoint of the arc (Cx, Cy)

Cx = Ax + (Ax-Bx)
Cy = Ay + (Ay-By)

Now, for any point on the arc, draw a chord (a line between two points on a circle) from that point (x, y) to the midpoint of the arc.

The length of this line can be calculated by the radius of the circle and the angle between the two radii. The formula for length of a chord is 2r.sin(a/2), where r is the radius and a is the angle between the radii. We want 45 degrees either side of the midpoint, so the maximum chord length is

2r.sin(45/2)

So points within 2r.sin(45/2) of our point (Cx, Cy) will be close enough to draw a quarter circle. Your result is

Any coordinate (x, y) such that
(x-Ax)^2 + (y-Ay)^2 = r^2
(x-Cx)^2 + (y-Cy)^2 <= (2r.sin(45/2))^2

Good fun!