0

I am currently in need of locating an algorithm that will determine if a point is to the right or left of an arc. This is an extension of the following algorithm to include arcs:

 // isLeft(): tests if a point is Left|On|Right of an infinite line.
//    Input:  three points P0, P1, and P2
//    Return: >0 for P2 left of the line through P0 and P1
//            =0 for P2  on the line
//            <0 for P2  right of the line
//    See: Algorithm 1 "Area of Triangles and Polygons"
inline int
isLeft( Point P0, Point P1, Point P2 )
{
    return ( (P1.x - P0.x) * (P2.y - P0.y)
            - (P2.x -  P0.x) * (P1.y - P0.y) );
}
//===================================================================

This code was retrieved from the site: http://geomalgorithms.com/a03-_inclusion.html

And this is used for the winding number algorithm. My goal is to expand this algorithm to include arcs and not just lines.

It is not quite like this post here: How to determine whether a point (X,Y) is contained within an arc section of a circle (i.e. a Pie slice)?

In the post mentioned, the author is trying to determine if the point lies within the central angle of the arc. Mine is slightly different in the sense that a point can be beyond the radius but the arc still contains the point in question.

I created a picture of what I am attempting to describe. Please note that I am not a drawer in any way. Anyways, the arc in question is green. I created two parallel lines that intersect the arc at the start and end nodes respectively. These lines are colored red. Please forgive my drawing skills. Even though the red lines in the drawing may appear to not be parallel, they are suppose to be parallel. The drawing is just for reference. I am defining in this post that the lines are parallel. This post here supersedes whatever is in the drawing. This means that even if the drawing does not indicate that the lines are parallel to each other, they are in fact suppose to be parallel to each other since I have stated this in the post. I need assistance in coming up with an algorithm that will determine if a point lies within the blue area. Note that the red lines can extend infinitely. For the sake of discussion, I ended the lines at an arbitrary point to color in the blue area.

If the point lies within the blue area, I consider this as the arc containing the point. As a side note, I am coding this algorithm in C++ (hence the c++ tag)

The type of arc I'm talking about is a circle's arc with a start and end node, an arc angle, and a circle center point and radius.

Edit:

The two answers by Yves and MBo contain better pictures at what I am attempting to explain. Please refer to these pictures. MBo contains the better of the pictures.

As Yves has described, I am attempting to test if a point lies within a semi infinite slab delimited by the arc and two parallel lines. These lines intersect the start and end node. Refer to MBo drawing for a clearer picture. Yves first drawing is also a clear picture. I am testing if the point lies in the shaded region.

I am using the terms left and right as a perspective. I apologize that I did not clearly explain this the first time I created the post. Imagine that you are traveling on this arc in a counter clock wise motion. The first node would be the right most node and the end node would be the left most node. From the perspective of the traveler, a point that is contained by this arc (or the semi-infinite slab) would be to the left of the arc. Any points to the right would be outside of the arc.

philm
  • 797
  • 1
  • 8
  • 29
  • 2
    What kind of arc is this, exactly? Is it a typical arc, as found along the circumference of a circle? – Alexander Jan 02 '18 at 03:47
  • 1
    You probably need a better drawing – Passer By Jan 02 '18 at 03:53
  • 3
    _"I created two parallel lines that are tangent to the arc at the start and end nodes."_ The red lines does not look to be tangential to the arc at all. – pingul Jan 02 '18 at 04:05
  • @pingul I noticed that too. Nor are they the perpendicular to the tangent, or they wouldn't be parallel and would in fact meet at the center of the circle that the arc was taken from. I think it's best to ignore the word "tangent" and assume an arbitrary polygon with one side being an arc. – Mark Ransom Jan 02 '18 at 04:15
  • 1
    An algorithm is an algorithm, it should not be language specific. – David Jan 02 '18 at 04:28
  • 2
    It's really unclear what you're asking. 1) _left/right_ seems meaningless. How do you interpret that with an apex at 0 deg, 45 deg, 90 deg, 180 deg etc.? 2) Your image does not clarify anything. How do you determine the gradient of each of your red lines? _What you've drawn is **not** a tangent; I think you misunderstand the term._ 3) Until you can properly define your requirement, there's no way to determine whether a given algorithm is "correct". – Disillusioned Jan 02 '18 at 04:43
  • Added in additional details for clarity – philm Jan 02 '18 at 05:25
  • Also, this is a regular arc that can be found on any circle. This is not a B-spline or a Biezer curve or a Nurbs curve or whatever, this is a simple arc with a star and end node, an arc angle, and a center point and radius – philm Jan 02 '18 at 05:27
  • 1
    philm, I think you are misunderstanding our focus on the tangential lines. If you wish the lines to be parallel _and_ tangential (and, the arc is a proper "circle" arc as you state in the update), the only possibility is to have a half circle touched by two infinitely long planes. If this is indeed the case, the problem is much less general than what you have described. My guess is that you need to remove one of the requirements (probably the tangential one). – pingul Jan 02 '18 at 05:31
  • I had thought the tangent question could possibly be resolved by taking 2 lines perpendicular to the _tangent through the apex_; where each of these lines intersect the end points of the arc (_but that has its own problems_). The "left/right" question would still be nonsense. You say you're trying to expand on an algorithm for a line between 2 points. So consider a line parallel to the x-axis. A point could be above/below the line, but left/right is meaningless; _until you examine the implementation..._ (cont.) – Disillusioned Jan 02 '18 at 06:29
  • (cont.) The code provided shows that algorithm considers the _direction_ of the line, and assumes it continues infinitely according to the equation that defines the line. I.e. if you swap P0 and P1, then left/right changes. The logical equivalent for your algorithm seems to be: _left/right of an arc continuing according to the same formula_. But you've described this as a "normal circle arc". As as result left/right would effectively be _inside/outside_ the circle depending on whether left is in or not! – Disillusioned Jan 02 '18 at 06:38
  • In a nutshell everything hinges on how you extend the arc from the endpoints. Until you figure out what you want and can clearly define it: you ***do not have*** a question! There are **many** options. E.g. 1) Simply a line through the endpoints (i.e. the arc is a speed-bump interruption of a normal line). 2) Tangential at the end-points. Depending on how much of the circle the arc describes, the lines could be parallel, **OR** wide angled and ever expanding **OR** at an angle that's closing at some point within the arc. 3) Force parallel lines as per my earlier comment. – Disillusioned Jan 02 '18 at 06:48
  • PS: Stop trying to make excuses for your drawing based on you "not being a drawer in any way". The problem has nothing to do with artistic ability and everything to do with the fact that you haven't yet thought through the problem enough to properly describe what you want. Once ***you*** have a _clear understanding_ of the problem, you will be able to draw something that might look like a dogs breakfast, but will be suitably annotated to make your question clear. – Disillusioned Jan 02 '18 at 06:59
  • Couldn't you just check if the point is to the right of the left arc line, and to the left of the right arc line? – Retired Ninja Jan 02 '18 at 10:59
  • @RetiredNinja It's one thing to _say_ "just check if...." but think it through: 1) What is left and what is right? e.g. for an approximately horizontal arc; is a point above the arc left or right? 2) Take a large sheet of paper; draw an arc somewhere; consider ***all possible points*** on the sheet; do you have a clear definition of left/right of the arc for every point? 3) Repeat 2 with arcs of different sizes, positions and orientations. .... _The point is the question provides none of the clarification required and as a result any answer would be unverifiable_. – Disillusioned Jan 02 '18 at 12:08
  • Ok I updated the explanation of the post using the wording in the 2 answers here. I believe that this will clear up any confusion. I do not have any issue explaining my post or adding details. Please let me know what else I can add that will clear up any confusion. – philm Jan 02 '18 at 15:20

2 Answers2

3

Hint:

If your final goal is to implement the widing number algorithm, what you are asking is to test if the point lies inside a semi-infinite slab delimited by two parallel lines (say horizontal, such that Yb < Y < Ye) and the arc.

The equation of the circle reads (X - Xc)² + (Y - Yc)² = R², from which you draw the condition X < Xc + √(R²-(Y - Yc)²). For convenience, you can split all arcs so that they only meet an horizontal once.

enter image description here

In other configurations, you will have to consider the intersections on the other side, X < Xc - √(R²-(Y - Yc)²), but I leave you the complete discussion. enter image description here

  • Yes, this is what I have been trying to explain. I think that I will update my post to reflect what you have written here – philm Jan 02 '18 at 14:26
2

Let you have arc center C, radius R, ends A and B.

If I understand your wishes correctly:

If point P and center C lies in the same semi-plane against AB line:
check whether projection of point P onto AB line lies in the limits of AB segment
else (if point P and center C are in different semi-planes):
check that distance from P to C does not exceed R

if Sign(CrossProduct(P-A,B-A))  =   Sign(CrossProduct(C-A,B-A))
    Result =  DotProduct(P-A, B-A) / DotProduct(B-A, B-A)  in range 0..1
else
    Result =  DotProduct(P-C, P-C) <= R^2

For example, sign conditions is true for points K and H and result is true for H. Sign condition is false for I and J, result is true for point J

enter image description here

MBo
  • 77,366
  • 5
  • 53
  • 86
  • This looks great, for point H, if the point is still in the shaded area but much further away from point C (greater then R), I take it that point H will still be true? – philm Jan 02 '18 at 15:07
  • Yes, I consider infinite semi-band. – MBo Jan 02 '18 at 15:13
  • Ok, also, what is the sign function? I am not quite familiar with that one? – philm Jan 02 '18 at 15:21
  • For example, +1 for positive value, 0 for zero, -1 for negative value – MBo Jan 02 '18 at 15:23
  • Ok I see, and in the second line, is the algorithm testing to see if the result is between 0 and 1? – philm Jan 02 '18 at 15:26
  • Yes (X>=0.0) && (X<=1.0) – MBo Jan 02 '18 at 15:27
  • OK great so to confirm, since I am working in 2D space, it looks like the result of the cross product is the dot product – philm Jan 02 '18 at 17:45
  • No, cross and dot product are different operations. – MBo Jan 02 '18 at 18:06
  • Oh ok, I see it now. Sorry, it is very close to the dot product operation but it is slighly different – philm Jan 02 '18 at 18:21
  • Just as a small update, I created the algorithm as specified and everything appears to be working. I am going to do some more involved testing in a later and update this as the solution if everything checks out! – philm Jan 02 '18 at 19:18
  • I have ran tests and verified that this algorithm is working! Thank you so much for all of your help! – philm Jan 03 '18 at 02:08