Determining Which Points on the Perimeter of a Circle Fall Between Two Other Points That Are on Its Radius

Question

I have a circle with a known radius centered at the origin.

Radius <- 1
Horizontal_Coordinates <- seq(-Radius, Radius, 0.01)
Positive_Vertical_Coordinates <- sqrt((Radius ^ 2) - (Horizontal_Coordinates ^ 2))
Negative_Vertical_Coordinates <- -sqrt((Radius ^ 2) - (Horizontal_Coordinates ^ 2))
Circle_Coordinates <- data.frame(Horizontal_Coordinates = c(Horizontal_Coordinates, rev(Horizontal_Coordinates), Horizontal_Coordinates[1]), Vertical_Coordinates = c(Positive_Vertical_Coordinates, rev(Negative_Vertical_Coordinates), Positive_Vertical_Coordinates[1]))
plot(0, type = "n", xlim = c(-(Radius * 1.05), (Radius * 1.05)), ylim = c(-(Radius * 1.05), (Radius * 1.05)), xlab = "", ylab = "")
polygon(Circle_Coordinates$Horizontal_Coordinates, Circle_Coordinates$Vertical_Coordinates)

I also have two points (these two happen to have been chosen at random) that fall somewhere along the perimeter of this circle.

Random_Angle_1 <- runif(1, 0, (2 * pi))
Random_Angle_2 <- runif(1, 0, (2 * pi))
Point_1 <- c(cos(Random_Angle_1), sin(Random_Angle_1))
Point_2 <- c(cos(Random_Angle_2), sin(Random_Angle_2))
points(Point_1[1], Point_1[2], pch = 19, col = 2)
points(Point_2[1], Point_2[2], pch = 19, col = 2)

The Circle_Coordinates data frame is of particular interest to me. I want to subset this data frame so that it only includes values that fall between the two points that are red in the figure. The two points will never fall directly opposite on the circle from each other, so there will always be a shorter arc and a longer arc between them. I'm interested only in the shorter arc - I want to subset the data frame so it only includes values that fall on the shorter arc.

Answer 1

We can use the Law of Cosines to calculate the angle of the arc between any two points on the circumference of a circle.

arc <- function(p1, p2, r = 1) {
  d2 <- sum((p1 - p2)^2)
  acos((2 * r^2 - d2) / (2 * r^2))
}

CC <- Circle_Coordinates

# arc angle from Point 1 to Point 2
arc.p1p2 <- arc(Point_1, Point_2)
# arc angle from Point 1 (Point 2) to other points on the circle
arc.p1 <- apply(CC, 1, arc, Point_1)
arc.p2 <- apply(CC, 1, arc, Point_2)
arc.sum <- arc.p1 + arc.p2

If a point lies between Point 1 and Point 2, its arc.sum will be equal to arc.p1p2.

CC[abs(arc.sum - arc.p1p2) < 1e-7, ]

Here I do not use CC[arc.sum == arc.p1p2, ] because of the inaccurate floating point arithmetic.

---

Diagram

plot(0, type = "n", xlim = c(-(Radius * 1.05), (Radius * 1.05)), ylim = c(-(Radius * 1.05), (Radius * 1.05)), xlab = "", ylab = "")
polygon(CC$Horizontal_Coordinates, CC$Vertical_Coordinates)
points(CC)
points(rbind(Point_1, Point_2), pch = 16, cex = 2, col = 2)
points(CC[abs(arc.sum - arc.p1p2) < 1e-7, ], col = 3)

Answer 2

Consider a secant (line on graph below) through Point_1 and Point_2 (red dots). The key principle is that any point on the circle that is in the minor arc (green) will be on the opposite side of the secant as the origin (black dot).

We can check for this by creating a function f that takes a point in the plane P and returns zero if P is on the secant and returns positive values on one side and negative values on the other side of the secant. If P is a point on the circle and O is the origin then P will be on the minor arc iff f(P) * f(O) < 0 since the product of a negative and positive number is negative whereas the product of two negatives or two positives is positive. (Those familiar with linear support vector machines may recognize that similar constructs involving half planes are used.)

The two approaches below are two different ways of creating f (using linear regression or using determinants) but are otherwise the same.

No trig functions are used. Also the basic idea can be generalized to higher dimensions by generating a hyperplane (e.g. a plane in 3d space) in place of a line.

1) Here we define f = b + mx - y to be the function that is zero getting the equation by regressing the y values of Point_1 and Point_2 on the x value and using predict to get the value of b + mx. Below ok is a calculated logical vector with one element per row of Circle_Coordinates. An element of it is TRUE if the corresponding row is on the minor arc and FALSE otherwise so it can be used to subset Circle_Coordinates to the rows on the minor arc.

# run code from question as given in Note below first

CC <- Circle_Coordinates
M <- rbind(Point_1, Point_2)
fm <- lm(V2 ~ V1, as.data.frame(M))
f <- function(z) predict(fm, list(V1 = z[1])) - z[2]
ok <- f(numeric(2)) * apply(CC, 1, f) < 0
CC_minor <- CC[ok, ]

# show on plot
points(CC)
points(M, pch = 20, cex = 3, col = "red")
points(CC[ok, ], col = "green")
points(0, 0, pch = 20)
abline(fm)

(continued after graph)

2) Another approach is via determinants. P lies on the secant passing through Point_1 and Point_2 iff f2(P) defined below is zero. (See Determinant Form section of the Linear Equation Wikipedia page.) ok2 has a similar meaning to ok in (1).

CC <- Circle_Coordinates
f2 <- function(z) det(cbind(Point_2, z) - Point_1)
ok2 <- f2(numeric(2)) * apply(CC, 1, f2) < 0
CC_minor2 <- CC[ok2, ]

identical(ok, ok2)
## [1] TRUE

Note

This code is from the question except we have added set.seed(...) to make it reproducible. To test the above with different Point_1 and Point_2 change the seed, run it and then run the answers above.

set.seed(12345)
Radius <- 1
Horizontal_Coordinates <- seq(-Radius, Radius, 0.01)
Positive_Vertical_Coordinates <- sqrt((Radius ^ 2) - (Horizontal_Coordinates ^ 2))
Negative_Vertical_Coordinates <- -sqrt((Radius ^ 2) - (Horizontal_Coordinates ^ 2))
Circle_Coordinates <- data.frame(Horizontal_Coordinates = c(Horizontal_Coordinates, rev(Horizontal_Coordinates), Horizontal_Coordinates[1]), Vertical_Coordinates = c(Positive_Vertical_Coordinates, rev(Negative_Vertical_Coordinates), Positive_Vertical_Coordinates[1]))
plot(0, type = "n", xlim = c(-(Radius * 1.05), (Radius * 1.05)), ylim = c(-(Radius * 1.05), (Radius * 1.05)), xlab = "", ylab = "")
polygon(Circle_Coordinates$Horizontal_Coordinates, Circle_Coordinates$Vertical_Coordinates)

Random_Angle_1 <- runif(1, 0, (2 * pi))
Random_Angle_2 <- runif(1, 0, (2 * pi))
Point_1 <- c(cos(Random_Angle_1), sin(Random_Angle_1))
Point_2 <- c(cos(Random_Angle_2), sin(Random_Angle_2))
points(Point_1[1], Point_1[2], pch = 19, col = 2)
points(Point_2[1], Point_2[2], pch = 19, col = 2)

Update

Have added (2), simplified both it and (1) and made the approaches more similar. Also improved exposition factoring out the common elements to a discussion at the beginning.