algorithm - Voronoi Solver - 这种边缘构造方法有什么作用？

Question

我偶然发现了一个用于 Voronoi 图解算器的 Fortunes 算法的实现，但我不确定发布的 Edge 类的 __construct 方法中实际发生了什么下面(为清楚起见删除了一些片段)。

class Edge
{
    //removed member vars

    function __construct($start, $left_site_event, $right_site_event)
    {
        //removed property assignment
        //this->start = $start //etc etc

        $this->f = ($right_site_event->position->x - $left_site_event->position->x) / ($left_site_event->position->y - $right_site_event->position->y);
        $this->g = $start->y - $this->f * $start->x;

        $this->direction = new Vector(($right_site_event->position->y - $left_site_event->position->y), ($right_site_event->position->x - $left_site_event->position->x));
    }
};

我有兴趣理解的三行是f、g 和direction 的赋值左右站点事件。

首先，f 和 g 变量的命名似乎很糟糕，除非它们遵循某种公式化的命名法？这些属于什么以及这里实际计算/确定的是什么？

在我看来，方向表示左右站点事件之间的边缘斜率。再说一次，这里计算的是什么？

任何有助于理解这一点的帮助将不胜感激，因为当两个站点事件位于同一 y 轴上时(即:左右站点事件 y 坐标相同)，我发现的实现似乎会出现问题.

更新

我添加了从我找到的源(见下文)移植的实现的当前结果的屏幕截图。此外，如果它对任何人有帮助，您可以从 github 获取最新的(不是很有效)求解器副本。 .

Answer 1

它看起来很像 f 和 g 是用来计算 slope & intercept of a straight line through the points 的，但作者把它搞砸了。如果您允许我滥用符号，f 定义为 x 坐标值与 y 坐标值的比率，我将其写为 f ~ x/y。这意味着在 g 的定义中，您要从 y 项中减去 f*x ~ x^2/y 项。

现在，如果 f 实际上是要定义为 f ~ y/x，那么在 g 的定义中你将是从 y 项中减去 f*x ~ y 项，这会更有意义。我还认为作者可能不小心在 f 的定义中丢失了一个 -1(这就是为什么分母与分子相反)，但我不能肯定地说没有看到其余的代码。

此外，当左右站点的 y 坐标相同时，您会在 f 的定义中除以零，这可能就是它搞砸的原因。

如果您能解释一下 start 点代表什么，以及该算法是从左扫还是从右扫，我也许就能弄清楚它到底想做什么。