Voronoi求解器 - 這個邊緣構造方法是做什麼的？

我已經偶然發現了一個Voronoi圖求解器的Fortune算法的實現，但我不確定在下面發佈的Edge類的__construct方法中實際發生了什麼（爲清楚起見刪除了一些片段）。Voronoi求解器 - 這個邊緣構造方法是做什麼的？

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處獲得解算器的最新（不是很有效的）副本。

Voronoi Solver

來源

2013-11-27 CaptainRedmuff

它看起來很像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的定義中得到一個除零的值，這可能是爲什麼它正在分散。

如果你可以解釋點代表的是什麼，算法是從左邊還是右邊掃，我可能會弄清楚它到底想做什麼。

來源

2013-11-28 18:36:58

感謝您的回覆。不幸的是，我發現的源代碼中使用的大部分數學方程式都超出了我的想象。但是，我確信該算法會從下到上掃描，從左到右。如果有任何幫助，您可以查看我的移植實現到Objective C中的邊緣https://github.com/CaptainRedmuff/Voronoi/blob/master/Voronoi/Voronoi/VoronoiEdge。m和解決方案的實現https://github.com/CaptainRedmuff/Voronoi/blob/master/Voronoi/Voronoi/VoronoiSolver.m#L171 – CaptainRedmuff

是的，VoronoiSolver.m的第474和475行表明'f'的確應該是是邊的斜率，g是包含邊的線的y截距。我現在非常有信心，VoronoiEdge.m的第42行是錯誤的 - 分子和分母應該是相反的。更多的，我認爲「開始」是邊緣「誕生」的點，而左側站點和右側站點事件是邊緣與它起源的拋物線相交的地方。 e：在x和y座標互換的時候還有一些奇怪的現象，但我無法破譯到底是以什麼爲目標。 –

我曾嘗試切換分子和分母，但它似乎沒有產生更好的結果。從我添加到我的問題中的圖像來看，它幾乎看起來像它的邊緣整理是不正確的，但奇怪的是，僅限於某些事件。 – CaptainRedmuff

Voronoi求解器 - 這個邊緣構造方法是做什麼的？

回答

相關問題