0

I have Voronoi polygons (triangles and quadrilaterals, given as a set of points) on a (unit) sphere. Now given an arbitrary point p on the sphere (given in XYZ or polar), I can determine, using the great circle distance, in which polygon it lies. Now, given the Voronoi's centre point c, I want to "draw" an arc that goes through the centre and p and determine which of the edges of the polygon is intersected by this arc (drawn in white). I want to determine the point q where the intersection occurs.

(I'm not a professional mathematician, so I would appreciate if the answers are understandable by a lay person.)

enter image description here

Bernard
  • 175,478
Emit Taste
  • 177
  • 8
  • Regarding what you're trying to achieve, what happens if your point $q$ coincides with the Voronoi site $c$? About solving your problem, I am unsure what precise Voronoi diagram you're using, but in this particular case, you can easily go from a cell on the sphere (with great circle distance), and the cell in the entire space $\mathbb R^3$ (with the standard Euclidean distance). So if you're having trouble with working on the sphere, you can solve the problem in $\mathbb R^3$ and then get back to the sphere. – N.Bach May 19 '18 at 16:56
  • @N.Bach I am trying to determine a pair (angle, distance) for q inside the voronoi, where the angle would go from 0 to 2pi across the sides of the polygon, and the distance goes from 0 (centre) to 1 (on the polygon). If q == c, the relative distance is zero and the angle does not matter, so it does not matter which polygon side is detected. – Emit Taste May 19 '18 at 19:34
  • @N.Bach you mean R2, right? Or using chords in R3? – Emit Taste May 19 '18 at 21:24
  • I think it might be a duplicate of https://math.stackexchange.com/questions/1720450/arc-intersection-on-a-sphere – Emit Taste May 19 '18 at 21:43
  • Yes, you can apply the method from the question you linked. And no, I meant $\mathbb R^3$. If you take the ray originating from the center of the sphere, and that goes through a point in the voronoi cell of $u$ on the sphere, then the whole ray belongs to the cell of $u$ in $\mathbb R^3$. And conversely if any point belongs to the cell of $u$ in the $\mathbb R^3$ diagram, its projection on the sphere belongs to the cell of $u$ in the sphere diagram. Basically I suggested working with portions of planes and lines/rays, if you were having trouble with the spherical geometry. – N.Bach May 19 '18 at 22:43
  • This answer can be used. B and D are the two end points of the white arc segment, N is $p \times c$, and then q corresponds with H. – Emit Taste May 19 '18 at 23:41

1 Answers1

1

The other Voronoi regions on your sphere also have centers. Suppose the center of the red region is named $b.$ Then the white arc is part of a great circle that is exactly halfway between $b$ and $c.$ The plane in which that great circle lies (which also passes through the center of the sphere) is perpendicular to the vector $b - c,$ using Cartesian $(x,y,z)$ coordinates for $b$ and $c.$

You can get a unit normal vector for the plane of the arc by scaling $b-c$: $$ \hat n = \frac{1}{\lVert b - c\rVert}(b - c), $$ but this is not actually necessary for the purposes of the problem you're trying to solve. A great-circle arc can be identified by the direction of a vector perpendicular to the plane of the arc, regardless of the length of the vector.

The arc from $c$ through $p$ to $q$ also is an arc of a great circle, and the plane of that great circle is perpendicular to the vector $p \times c.$ (As you surmised, this corresponds to the vector $n$ in the linked answer, but once again it is the direction of the vector, not its length, that matters for the purposes of this problem, and it is not really necessary to divide the length of the vector by $\lVert p \times c\rVert.$)

Assuming the great circle through $c$ and $p$ exits the green region along the white arc, the point $q$ is at the intersection of that arc's great circle and the great circle through $c$ and $p.$ Since we have vectors $b - c$ and $p \times c$ perpendicular to each of those great circles, we can find the intersection point by taking the cross product of those two vectors. That is, $$ q = k\big((p \times c) \times (b - c)\big), $$ where $k$ is some number, possibly negative. More specifically, $$ q = \pm\frac{R}{\lVert(p \times c) \times (b - c)\rVert} \big((p \times c) \times (b - c)\big), $$ where $R$ is the radius of the sphere. In this particular exercise the order of operations has been set up so that the correct answer uses the positive sign, but you can also do the operations without being careful about taking the input vectors of each cross product in the "correct" order, and then decide at the end whether you need to change the sign of the answer.

To decide which of the arcs bounding the green Voronoi region is the one that will be intersected by the great circle arc from $c$ through $p,$ you can find the vertices of the Voronoi polygon by taking cross products of vectors perpendicular to each side of the polygon. For example, suppose $a$ is the center of the purple region. Then $$ u = (b - c) \times (a - c) $$ is a vector in the direction of the polygon vertex where the green, red, and purple regions meet. Then $u \times c$ is a vector perpendicular to the great circle arc from $c$ to that vertex.

So let's use this technique to find a vector $u$ pointing at one end of the white arc and a vector $v$ pointing at the other end. The arc from $c$ through $p$ will exit the green region along the white arc if $p$ is inside the spherical triangle formed by $c,$ $u,$ and $v.$

We use the fact that if the inner product (also called the dot product) of the vector to a point and a vector perpendicular to a plane through the origin is positive, then the two vectors are on the same side of that plane. So to find out if a point $p$ inside the green region is within the spherical triangle $\triangle cuv,$ evaluate the following statements: $$ p \cdot (c\times u) \text{ has the same sign as } v \cdot (c\times u),\\ p \cdot (c\times v) \text{ has the same sign as } u \cdot (c\times v). $$ If both statements are true, $p$ is inside the triangle and the arc from $c$ through $p$ will intersect the white arc.

David K
  • 98,388