3 ms·
> 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 t
by gus_massa 8y ago
> 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.
- gugagore 8y agoIt might be that the triangle is big enough (relative to, say, the radius of the sphere) that that approximation doesn't apply.
- slavik81 8y agoIt'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.
- frenchie14 8y agoI'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
- slavik81 8y agoI 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...
- gus_massa 8y agoI 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.
- amitp 8y agoIn 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.