Диаграмма Вороного с использованием пользовательского (большого круга) расстояния

Question

Я хочу создать диаграмму Вороного на нескольких парах широт / долгот, но хочу использовать расстояние между ними по большому кругу, а не (неточное) пифагорейское расстояние.

Могу ли я заставить qhull / qvoronoi или какую-либо другую программу Linux делать это?

Я подумал о том, чтобы отобразить точки в 3D, с помощью qvoronoi создать трехмерную диаграмму Вороного [1] и пересечь результат с сферой, но я не уверен, что это легко.

[1] Я понимаю, что трехмерное расстояние между двумя широтами / долготами (путь «через Землю») не совпадает с расстоянием большого круга, но легко доказать, что это преобразование сохраняет относительные расстояния, что все, что имеет значение для диаграммы Вороного.

Answer 1

Полагаю, вы нашли эту статью . Исходя из этого, кажется, у вас есть правильная идея с использованием 3D-встраивания. Тогда ваш вопрос, как пересечь результат со сферой.

Прежде всего вам нужно подумать о том, как вы собираетесь представлять диаграмму Вороного. Если вы хотите работать с координатами широты / долготы в 2D-плоскости, тогда ваша диаграмма вороной будет содержать изогнутые ребра, поэтому, возможно, лучше всего использовать 3D-представление.

Если вы используете программу типа qvoronoi, теоретически вам нужны только данные бесконечной гиперплоскости (генерируемые Fo). Это дает вам уравнение плоскости и двух точек, которым она соответствует. Обычно вам нужно использовать диаграмму Вороного только для проверки на включение в регионы, и для этого должно быть достаточно гиперплоскостей.

Answer 2

См. Также этот вопрос: Алгоритм вычисления диаграммы Вороного на сфере?