c# how to detect intersecting circles as separate from edgepoints

Question

I am trying to create a 2(or more) circles from a list of edgepoints which is sorted. A egdepoint is just a point. A list of edgepoints make the edge of a circle. Drawing a line between the edgepoints gives the black line in the pictures. So there is no radius and circles can vary in size.

It looks like this:

My idea is to split it like picture 2. Next, create circles like in this article. Ofcourse with the fist, middle and last point.

I created a method to detect whether the edgepoints are sorted clockwise or counter clockwise. Unfortunately I am stuck on how to detect these "split points" The picture can be rotated ofcourse.

The result should be 2(or more) list with edgepoints:

So how can I detect these "split points"? Or is there a better way to detect intersecting circles as separate?

Answer 1

Input: Something like Point[]. Output: Something like List[Circle] Assume input is sorted by position around the outer edge of some picture that is made up of overlapping circles. Any points in the interior of the picture are not included.

I thought about it more and I think you can find the points easier if you consider slope. Points where the slope varies wildly are the points you are looking for.

[Revised thought - Find the transition points first, then the circles.] Start by using a function to calculate the slope of a line segment between two points. As you go around a circle, you will have a reasonable change in slope (you will have to discover this by reviewing how close the points are together). Say you have points like { A, B, C, D, ...}. Compute the slope of A->B and B->C. If the points are evenly spaced, that difference or the average difference might be a tolerance (you have to be careful of transition points here - maybe compute an average over the entire set of points). If at some point the slope of K->L and L->M is very different from J->K and K->L then record that index as a transition point. Once you have traversed the whole set (include a test for Y->Z and Z->A as well if it is a closed shape), the recorded indexes should define the transition points. Use the mid-point of each segment as the third point for each circle. (e.g. if you identified I and M as transition points, then use I, K, and M to define a circle).

[Original thought - find the circles first] Use the referenced article to determine the center of a circle based on three points. Then determine if it is really an interesting circle by testing some of the points around the reference points. (Say, pick every 5th or 10th point then verify with all the interior points). With more overlapping circles, this becomes a less effective process so you will have to define the algorithm carefully. Once you get all the reference circles, process through all of the edge points (assuming these are points on the exterior of the drawing). Using center, radius, a distance formula, and a tolerance, determine which points are on which circle. Points that fit the tolerance on more than one circle are the points you are looking for I think.