如果您知道边和三角形的数量，则可以通过三角形列表进行栅格化并创建三角形到边图$(\mathcal{O}(N_{tri}))$并同时创建逆映射，这将为您提供共享边的两个三角形。对该列表的直角三角形对的天真搜索将是$\mathcal{O}(N_{edge})$， 在哪里$N_{edge}$最坏的情况是$3 \cdot N_{tri}$. 当然，这一切都假设您有一种方法可以为图中的每条边计算唯一 ID。