How do I get an array of points of a circle union's circumference

Question

so I know that The parametric equation for ONE circle is:

x = cx + r * cos(a)
y = cy + r * sin(a)

From this it's easy to get a point from it's circumference...

But what if I want to get the array points of many intersecting circle's circumference? Like this:

So how can I draw similar circle unions with GL lines containing points (Vertices, sequence matters) in a coordinate system, If I know each circle's center and radius?

(Best would be if you have to iterate trough it using it's collective parametric equation's parameter, to get each Vertex with the desired density.)

Warning! The result is just an array of points (any density) linked with lines as they follow each other (The bold black part). NOT polygons. The shape is not filled.

(I want to draw it in Unity3D using C# and GL.Lines)

Answer 1

Since you know Circle c1:

x1 = cx1 + r1 * cos(a)
y1 = cy1 + r1 * sin(a)

and you want additional condition point P[x1,y1] ∉ any other C. Simply generate all circles(or check the condition when generating) and remove all points that are closer to any Center[cx, cy] then corresponding circle radius R. To calculate ditance (or better square distance and compare to precalculated square R to improve perforamce) simply measure the distance of vector P - Center(pythagoras):

foreach (Point p){
 foreach (other Circle c){
 float dist = (P - Center).Lenght;
 if (dist < c.R){
  // point is not valid, remove
 }
 }
}

this solution isnt indeed optimal(as mentioned in comments). Other approach would be calculate intersections of every circle with every other(https://math.stackexchange.com/questions/256100/how-can-i-find-the-points-at-which-two-circles-intersect) and remove RANGE between those points(the right one ofc - its starting to be complicated). In addtiotion if you need to maintain right sequence, it should be possible to continue generating one circle untill you reach an intersection - then switch circles for the new one etc. Carefull though: you would need to start on outside of the shape!

Answer 2

Depending on which OpenGL version you want to use, a simple way would be to trace the triangles of each circles in a stencil. Then trace same circles in lines excluding the region in the stencil.

For a shader solution, you can check here:

#ifdef GL_ES
precision mediump float;
#endif

uniform vec3      iResolution;           // viewport resolution (in pixels)
uniform float     iGlobalTime;           // shader playback time (in seconds)
uniform float     iChannelTime[4];       // channel playback time (in seconds)
uniform vec3      iChannelResolution[4]; // channel resolution (in pixels)
uniform vec4      iMouse;                // mouse pixel coords. xy: current (if MLB down), zw: click
uniform samplerXX iChannel0..3;          // input channel. XX = 2D/Cube
uniform vec4      iDate;                 // (year, month, day, time in seconds)
uniform float     iSampleRate;           // sound sample rate (i.e., 44100)

bool PixelInsideCircle( vec3 circle )
{
    return length(vec2(gl_FragCoord.xy - circle.xy)) < circle.z;
}

bool PixelOnCircleContour( vec3 circle )
{
    return PixelInsideCircle(circle) && !PixelInsideCircle( vec3(circle.xy,circle.z-1.0) );
}

void main( void )
{
    float timeFactor = (2.0+sin(iGlobalTime))/2.0;

    const int NB_CIRCLES=3;
    vec3 c[NB_CIRCLES];
    c[0] = vec3( 0.6, 0.4, 0.07 ) * iResolution;
    c[1] = vec3( 0.45, 0.69, 0.09 ) * iResolution;
    c[2] = vec3( 0.35, 0.58, 0.06 ) * iResolution;
    c[0].z = 0.09*iResolution.x*timeFactor;
    c[1].z = 0.1*iResolution.x*timeFactor;
    c[2].z = 0.07*iResolution.x*timeFactor;

    c[0].xy = iMouse.xy;

    bool keep = false;
    for ( int i = 0; i < NB_CIRCLES; ++i )
    {
        if ( !PixelOnCircleContour(c[i]) )
            continue;

        bool insideOther = false;
        for ( int j = 0; j < NB_CIRCLES; ++j )
        {
            if ( i == j )
                continue;

            if ( PixelInsideCircle(c[j]) )
                insideOther = true;
        }

        keep = keep || !insideOther;
    }

    if ( keep )
        gl_FragColor = vec4(1.0,1.0,0.0,1.0); 
}

and tweak it a little

Answer 3

Your question is not really complete as you don't explain how you want the points to be spread over the outline. I infer that you would like a dense sequence of points ordered along a single curve.

There is no easy solution to this problem and the resulting shape can be very complex (it can even have holes). You will not spare the computation of intersections between circular arcs and other geometric issues.

One way to address it is to polygonize the circles with sufficient point density and use a polygon union algorithm. The excellent Clipper library comes to mind (http://www.angusj.com/delphi/clipper.php).

Another more quick & dirty solution is to work in raster space: create a large white image and paint all your circles in black. Then use a contour following algorithm such as Moore-neighborhood(http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/index.html).