Search code examples
mathgeometrycomputational-geometry

direction of connection between points v1, v2 on a circle, with obstacles (blocking interval [s, e])

i know the title seems bad - please feel free to specify. I can not come up with a better title.

All points are stated in polar coordinates relative to the circle center. Two points (v1, v2, s, e) lay on a circle edge. As shown in the image, s & e are the pink points, s = blocked_arc_start_angle, e = blocked_arc_end_angle.

enter image description here

Problem:
How do i check which direction on the circle is not blocked? With direction i mean clockwise (CW, math negative) or counter clockwise (CCW, math positive).

all angles are normalized and have a range of [-PI, PI]

I tried a lot of if-else case checks but due to the range of atan2 i have problems. Is there a easy simple way?
Any ideas?
regards!

I am still looking for a better solution!!! nobady likes many if-else calls...* Ugly Answer:
I thought about all cases which can occur, you can easily split by imagining the rage of the angle space:

1st case - obstacle/blocked arc/interval is not overlapping:
-Pi                                  PI
|-------------S::::::::E-------------|

2nd case - obstacle/blocked arc/interval is overlapping:
-Pi                                  PI
|::::E--------------------------S::::|

and so on...
important: check in before hand if a point lays inside the blocked interval: 

# no point is inside of a blocked arc
if m.point_inside_arc(v1.location, arc) or m.point_inside_arc(v2.location, arc):
    return False

Here is some pseudo code. Hopefully this helps some one.

if arc.start_angle < arc.end_angle:
    if angle_v1 < angle_v2 < arc.start_angle or arc.end_angle < angle_v1 < angle_v2:
        # |----V1---V2----S::::::::E----(V1---V2)----|
        math_negative = False
    elif angle_v2 < angle_v1 < arc.start_angle or arc.end_angle < angle_v2 < angle_v1:
        # |----V2---V1----S::::::::E----(V2---V1)----|
        math_positive = False
    elif angle_v1 < arc.start_angle and arc.end_angle < angle_v2:
        # |----V1---------S::::::::E---------V2----|
        math_positive = False
    elif angle_v2 < arc.start_angle and arc.end_angle < angle_v1:
        # |----V2---------S::::::::E---------V1----|
        math_negative = False
else:
    # |::::E-------------------------S::::|
    if angle_v1 < angle_v2:
       math_negative = False
    else:
       math_positive = False
Solution

  • Let c to be the center of the circle. Then if you calculate:

    dot = DotProduct( p1 - c, p2 - c )

    All points v for which both conditions are true:

    DotProduct( v - c, p1 - c ) > dot
DotProduct( v - c, p2 - c ) > dot

    will be in the blocked area

    In order to know the direction you can use also dot product. As dot product is the cos of the angle between vectors (supposing both vectors are unitary), you can calculate for each point p1 and p2 the angle alpha:

    cos( alpha ) = DotProduct( vector( 1, 0 ), ( p1 - c ).normalized );

    After getting alpha, you must use the value of component y of ( p1 - c ).

    If it is negative, then add 180 degrees to alpha.