How to draw polyline arc with fixed radius giving three mouse loc(first, second and last) in 2D?

Question

I have got question how to draw arc or part of cricle in OpenGL/Glut giving only one point and current mouse location? In total, the order of the mouse click, is not important.

The answer is below but i have got issuse to proper calculate it.

Gods like admins and rest - could ypu move this topic to on-topic, please?

How it should looks like

Answer 1

Let $\vec{p}_1 = (x_1, y_1)$ be the first point and $\vec{p}_2 = (x_2, y_2)$ the second point of the half-circle arc, and $\vec{p}_0 = (x_0, y_0)$ be the previous point preceding the first point.

If we look from $\vec{p}_1$ towards $\vec{p}_2$, the arc and $\vec{p}_0$ will be on different sides (left or right). If $\vec{p}_0$ and $\vec{p}_1$ are collinear, or there is no $\vec{p}_0$, then you probably want to draw a line instead of an arc.

Since the arc is a half-circle, the center $\vec{c} = (x_c, y_c)$ of that circle is at the midpoint of the two points, and radius $r$ half their distance. However, instead of scalar $r$, it is easier to use vectors $\vec{u} = (x_u, y_u)$ and $\vec{v} = (x_v, y_v)$, as if semi-major axes of an elliptical arc, where $\vec{v}$ is $\vec{u}$ rotated 90°: $$\begin{align} \vec{c} &= \frac{\vec{p}_1 + \vec{p}_2}{2} \\ r &= \left\lVert \vec{p}_2 - \vec{p}_1 \right\rVert \\ \vec{u} &= \frac{\vec{p}_1 - \vec{p}_2}{2} \\ \vec{v} &= \mathbf{R} \vec{u} \end{align} \; , \; \; \mathbf{R} = \begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix}$$ i.e. $$\begin{cases} x_c = \frac{x_1 + x_2}{2} \\ y_c = \frac{y_1 + y_2}{2} \\ r = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} \\ x_u = \frac{x_1 - x_2}{2} \\ y_u = \frac{y_1 - y_2}{2} \\ x_v = y_u = \frac{y_1 - y_2}{2} \\ y_v = -x_u = \frac{x_2 - x_1}{2} \end{cases}$$

The rotation by 90° is clockwise if using a left-handed coordinate system ($x$ increases right, $y$ down). If $\vec{p}_0$ is already clockwise from line from $\vec{p}_1$ to $\vec{p}_2$, we want it counterclockwise. (That just means negating $\vec{v}$, i.e. both $x_v$ and $y_v$ negated.)

Note that OpenGL uses left-handed coordinate system in normalized device coordinates, and most 2D graphics toolkits and file formats use left-handed coordinate systems too. This is why this answer assumes a left-handed coordinate system. Note that typically in mathematics a right-handed coordinate system is assumed (in 2D, $x$ increasing right, and $y$ up, not down as in left-handed).

That check if $\vec{p}_0$ is to clockwise or counterclockwise from $\vec{p}_1$ towards $\vec{p}_2$ is simple, if we use the 2D analog of vector cross product: $$\left( \vec{p}_0 - \vec{p}_1 \right) \times \left( \vec{p}_2 - \vec{p}_1 \right) = x_0 ( y_2 - y_1) + x_1 (y_0 - y_2) + x_2 (y_1 - y_0) \\ \begin{cases} \le 0, & \vec{p}_0 \text{ counterclockwise} \\ = 0, & \vec{p}_0 \text{ collinear} \\ \gt 0, & \vec{p}_0 \text{ clockwise} \end{cases}$$

In other words, if $x_0 ( y_2 - y_1) + x_1 (y_0 - y_2) + x_2 (y_1 - y_0)$ is positive, negate $x_u$ and $x_v$; if zero, draw a line instead of an arc. (If negative, everything is fine.)

Drawing a polyline from $\vec{p}_1$ to $\vec{p}_2 = \vec{p}_1 + 2 \vec{u}$ using $N$ line segments is easy. The $N+1$ points $\vec{a}_0 = \vec{p}_1$ to $\vec{a}_N = \vec{p}_2$ are $$\vec{a}_k = \vec{p}_1 + \left ( 1 + \cos\left(\frac{\pi k}{N}\right) \right ) \vec{u} + \sin \left(\frac{\pi k}{N}\right) \vec{v}, \; k = 0 \ldots N$$ (The $+1$ in the $\cos$ part just moves the center of the arc from $\vec{p}_1$ to $\vec{p}_1+\vec{u}$, where it should be.)

Note that even though I do assume a left-handed coordinate system for the explanation above, this works exactly as-is for right-handed coordinate systems, too: the only thing that changes, is swapping clockwise and counterclockwise in the explanations.

---

Depending on how you implement the above, the $\vec{u}$ or $\vec{v}$ might need to be negated. Here is a verified C function, which does the math correctly:

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

typedef struct {
    float   x;
    float   y;
} vec2f;

static void line_to(const vec2f p)
{
   /* Draw a line from current location to p.
      Implement this yourself. */
}

/* Draw a half-circle arc from p1 to p2,
 * starting in direction (not opposite to) d.
 * Returns the final direction. Uses n segments.
 * Assumes the pen is at p1 already.
*/
vec2f arc_to(const vec2f p1, const vec2f p2, const vec2f d, const int n)
{
    if (n > 1 && (d.x != 0.0f || d.y != 0.0f)) {
        /* We should be able to draw an arc. */

        /* Center is midway between p1 and p2: */
        const vec2f  c = { 0.5f*(p1.x + p2.x), 0.5f*(p1.y + p2.y) };

        /* Constant semi-axis u is halfway from p1 to p2 */
        const vec2f  u = { 0.5f*(p2.x - p1.x), 0.5f*(p2.y - p1.y) };

        /* Semi-axis v is u rotated by +90 degrees */
        vec2f        v = { u.y, -u.x };

        /* f = v . d; positive if in the same direction,
           zero if perpendicular */
        const float  f = v.x*d.x + v.y*d.y;

        /* Loop variable */
        int          i;

        if (f == 0.0f) {
            /* d is perpendicular to v, parallel to p2-p1.
               We do not know which side the arc should
               bulge, so we draw a line instead.
            */ 
            line_to(p2);
            return d;

        } else
        if (f > 0.0f) {
            /* d and v point at the same direction. Reverse v.
               This test is > 0.0f, because we use -u and -v
               in the loop below! */
            v.x = -v.x;
            v.y = -v.y;
        }

        for (i = 1; i < n; i++) {
            const float t = (float)i * 3.14159265358979323846f / (float)n;
            const vec2f p = { c.x - cosf(t)*u.x - sinf(t)*v.x,
                              c.y - cosf(t)*u.y - sinf(t)*v.y };
            line_to(p);
        }

        line_to(p2);

        return v;

    } else {
        /* Parameters indicate no arc, so just draw
           a line segment from p1 to p2.
           Return that direction (p2-p1), too. */
        const vec2f delta = { p2.x - p1.x, p2.y - p1.y };
        line_to(p2);
        return delta;
    }
}

Note that the above function only draws arcs when $\vec{d}$ points in the direction the arc can bulge. Otherwise, it only draws a line segment.