Checking if a point is on an arc, defined by two vectors

deluksic

So, i have a point in the coordinate system, and an arc defined by two vectors of equal length starting in the same point. The arc is always smaller than 180. How would i check if the point is on the arc? (the point is always on the circle, just need to check if it is in between these two vectors)


By deluksic at 2012-05-29

Vorde

Using trig, try and figure out the angle it makes with the x axis (usually where 0 degrees is located), then show that that angle is between the two angles that each vector makes with the x axis.

deluksic

Ok, trig would do, but can't you test x and y values of vectors and the point? I tried now drawing lines horizontally and vertically in the tips of both vectors. That would give me something to start with, now i need to test which lines outline the surface i need...

Oh, and i need this for a computer program so i need it to be fast :)

EDIT: now i see i could just draw line trough tips of these vectors and test whether the point is above or below the line

Bohrok

Couldn't you just check if the vector whose head is the given point has the same length as the other two vectors?

The_Duck

You could avoid any trigonometry by finding the equation of the line that goes through the tips of v1 and v2. Then check to see whether the origin is on the same side of the line as the point of interest. If the origin lies on the opposite side of the line from the point, then the point lies in the arc between v1 and v2.

Edit: I missed your edit above which is basically this, but note that you can't just check whether the point lies above or below the line. For a different configuration of v1 and v2, points in the arc will lie above the line, not below it. You should check whether the point lies on the same side of the line as the origin.

deluksic

Thank you very much, yes, this is what i was looking for :D (never would've tought of the origin.. )

M Quack

Take v_3 = (v_1 + v_2) and normalize it u_3 = v_3/ |v_3|.

The angle the test vector makes with u_3 has to be smaller than the angle v_1 (and v_2) make with u_3.

The dot product of v_1 and u_3 is

v_1 . u_3 = |v_1| cos α

The dot product of your test vector and u_3 is

v . u_3 = |v| cos β

If |β| < |α|, i.e. cos β > cos α then your test vector is in the right sector.

This should be rather fast.

deluksic

Hmm, interesting idea, i'll give it a try because lines give me problems when x's of vectors are the same then im dividing by 0

M Quack

You could look at my solution as an implementation of the line check....

deluksic

Just curious, what happens when v1=-v2? by adding those two i get v3(0,0)

Vargo

Here is a simple test. A,B,X

X lies inside the lesser arc AB if angle AXB is obtuse. X lies inside the greater arc AB if angle AXB is acute.

See Euclid Book III Prop 20:
http://aleph0.clarku.edu/~djoyce/jav...propIII20.html

M Quack

Then the angle between v_! and v_2 is 180 deg and to know which way you have to go (which arc is the "good" one) you need to know which vector is the beginning and which is the end - instead of just taking the sum (same result if you switch v_1 and v_2!!), you need to build a vector that bisects the angle. If you do that, then the method will work for any angle, as the angle with the bisecting vector will always be less than 180 deg. (if it is 180 deg, then you are accepting the whole circle).

Vargo

In terms of dot products, you just need to check whether (A-X) dot (B-X) is positive (acute angle) or negative (obtuse angle).

M Quack

Nice and elegant, but it has the same problem:If A and B are exactly opposite each other the angle AXB is always 90 deg, i.e. the dot product is zero. At least you don't get a division by zero error as you don't have to normalize vectors.

deluksic

I went around it by making few checks ;) now it works :D

yes and i am accepting the whole circle, actually it is usefull to me as i'm making a game where i need arcs AND circles, now i have both in one! awesome!