Hacker News Reader

Comment by gus_massa | Hacker News Reader

> But how do you computer a circumcenter for a triangle on a sphere? I found a solution on stackoverflow and implemented it.

Why is it necessary to calculate the circumcenters in 3D? Why not calculating them in the projection to the plane and then back-projecting them to the sphere? Perhaps it's necessary to calculate the Voronoi regions in the plane too.

View on HN

It's pretty easy to do it in 3D. Doing anything on a 2D projection is hard, because the space is so distorted. When you can easily measure distances, this is a lot easier.

It's a little weird that their results are inside the sphere. I don't fully understand the equation, but it looks to me like it's using angles/rotations from a to the centre, so I would expect it to remain on the surface. Maybe the problem is just numerical error?

Of course, if they're projecting the solution back to the surface anyways, the simplest way would be to find the centre of the triangle in xyz space, ignoring the sphere, then projecting the result back to the surface. As long as the triangle isn't larger than half the circumference, the shortest distance through the sphere would correspond to the shortest distance on the surface.

To be honest, I'm more surprised they projected to a plane in the first place. If he was doing it all from scratch, it would probably be simpler to do the triangulation in 3D.

I'm assuming the loss of height comes from measuring distances directly between points instead of along the surface of the sphere. Much cheaper, but by design you'll cut through the sphere to connect each point

I think you're right. The circumcentre equation is just more complicated than the centroid calculation I was imagining. They're doing exactly what I had suggested in the third paragraph.

There may also be a nice derivation of the triangle centre on the sphere coming from quaternion math that would avoid renormalization. I wonder...

I was thinking about having a true Voronoi diagram in the distorted version of the plane and a distorted Vornoi diagram in the sphere. I'm not sure if the result would be good enough to have all the expected properties.

I'm not even sure that it's ok to do the triangulation in the plane as described in the article, perhaps mapping the triangles in the plane to distorted triangles in the sphere may case them to be too curved.

In the projection, some triangles are rather spread out, and some are even going to cross from -Infinity to +Infinity. I didn't want to handle that wrap-around-infinity case and thought it'd be easier to calculate them on the sphere instead of on the projection.

It might be that the triangle is big enough (relative to, say, the radius of the sphere) that that approximation doesn't apply.

Reply on news.ycombinator.com