如何唯一識別線段？

Question

我正在處理一個問題以消除路徑集合中的常見線段。許多這些路徑共享相同的細分市場。

看來，2D線有一些方法可以唯一標識自己。像一把鑰匙。

因此，一個線[（A，B），（C，d）]是與[（C，d），（A，B）]

唯一的解決辦法我能想出是對點進行排序。

這似乎是數學或圖形中的常見問題，但解決方案逃脫了我。

Answer 1

從數學的角度來看，這看起來像一個無向圖（與有向圖相對）的問題。對點進行排序是處理這種情況的一種方式：用單一的，明確選擇的值來表示無序邊緣的直接方式（只要它對所有可能的情況都是一致的，選擇什麼順序無關緊要）段）。您確實需要確保將此順序保持爲不變式：意外滑入錯誤的邊緣可能會導致依賴於順序的任何問題。然而，從數學上講，無向圖通常定義爲具有對稱性的有向圖：如果（A，B）是邊，則（B，A）也是如此。這提示了另一種方式：確保您總是存儲（（A，B）和（B，A））。也許這兩種細分排序都可能與任何常見數據有關聯，並且可能是快速訪問另一種數據的方式。 （與排序點方法一樣，您需要將此對稱性保持爲不變量。）

最好的選擇取決於您的應用程序。如果您將細分用作關鍵字，排序方法可能是最好的。但是，有些應用程序更適合對稱方法。例如，doubly connected edge list是一個數據結構，它將每個邊表示爲兩個鏈接的「半邊」，每個方向一個。

---

由於您提到了圖形，請注意，雙連接邊列表通常用於表示3D多邊形的邊。

另外，請注意與定向三角形的相似性：計算機圖形將三角形視爲「單面」的原因有很好的實際原因，因此從一側繪製三角形可以從繪製可見的三角形另一個。像半邊一樣，這種區分是由頂點的順序決定的：一邊爲順時針，另一邊爲逆時針。