一種城市道路網路的隨機生成方式（Unity中可視化）
- 1. 說在開頭
- 2. 有限元網格劃分
- 2.1. 什么是有限元
- 2.2. 前沿推進法/波前推進法（Advancing Front Technique）
- 3. 實作
- 3.1. 資料的定義
- 3.2. 邊界的分類
- 3.3. 生成一個小網格
- 3.4. 生成橋邊
- 4. 完整代碼
- 4.1. 一些定義或輔助
- 4.2. AFT演算法
- 4.3. 可視化
參考：
[1]王元,煉訓,李航.基于有限元網格劃分的城市道路網建模[J].圖學學報,2016,37(03):377-385.
[2]李任君. 關于四邊形有限元網格生成演算法的研究[D].吉林大學,2008.
1. 說在開頭
做畢設的時候，第一步就需要城市道路網路的生成，翻了一些文獻，感覺王元等人1所提到的利用有限元網格生成的方式進行的路網生成效果挺不錯的，于是打算用這種方式實作，但是論文中并沒有過多的提演算法本身，所以實作演算法的時候主要還是參考李任君2的那篇文獻，
寫這篇博客的時候，我已經大體上把生成路網的初步功能給實作了，當然實作的非常粗糙，而且自身演算法能力非常有限，很多地方寫的也很暴力，還會有一定幾率會生成出質量很差的網格、甚至還有一些BUG沒有解決，后續繼續做下去的時候應該還是會進一步完善的，現在先寫一篇博客，記錄一下階段性的成果，順便當作是給最后寫畢業設計說明書打個草稿，
目前為止可以實作的是，通過給定一個多邊形的頂點資料作為路網的邊緣，然后自動的生成路網的資料，也可以實作不同區域的路網密度不同，
先放一下演示視頻，視頻播放有問題或者不對的話，可以跳轉到原網頁查看，
<iframe id="UGMBeaiy-1612281435164" src="https://player.bilibili.com/player.html?aid=88416805&page=5" allowfullscreen="true" data-mediaembed="bilibili"></iframe>
路網生成效果
稍微講解一下，目前是在Unity中，簡單的通過輸入頂點的方式給定路網邊緣，然后可以設定的引數有單元格長度（每一小段道路長度會盡可能的貼近單元格的長度），隨機種子（用于隨機一些長度和角度，種子一樣且其他引數一樣的情況下每次的結果也會一樣），然后就是一些可視化除錯用的選項，以及在世界坐標靠近原點的位置那一區塊道路密度更高（以后會改成專門制定密度的形式，這個靠近原點密度更高只是暫時用來測驗密度變化功能用的），
當前也存在著一些比較明顯的問題，比如有的網格質量非常差，所劃分的區域很小很窄，道路也靠的很近，效果不好，有的時候生成會出現死回圈的情況（檢測到死回圈就自動跳出），無法繼續向下劃分（視頻中出現過一次，一般換一個隨機種子就有很大幾率解決，當然這也是治標不治本），目前認為主要還是網格密度變化導致的一些缺陷，有待優化，
2. 有限元網格劃分
2.1. 什么是有限元
百度百科：
在數學中，有限元法（FEM，Finite Element Method）是一種為求解偏微分方程邊值問題近似解的數值技術，求解時對整個問題區域進行分解，每個子區域都成為簡單的部分，這種簡單部分就稱作有限元，
它通過變分方法，使得誤差函式達到最小值并產生穩定解，類比于連接多段微小直線逼近圓的思想，有限元法包含了一切可能的方法，這些方法將許多被稱為有限元的小區域上的簡單方程聯系起來，并用其去估計更大區域上的復雜方程，它將求解域看成是由許多稱為有限元的小的互連子域組成，對每一單元假定一個合適的（較簡單的）近似解，然后推導求解這個域總的滿足條件（如結構的平衡條件），從而得到問題的解，這個解不是準確解，而是近似解，因為實際問題被較簡單的問題所代替，由于大多數實際問題難以得到準確解，而有限元不僅計算精度高，而且能適應各種復雜形狀，因而成為行之有效的工程分析手段，
定義還是有點難懂，根據我的一些淺顯的了解（可能不太準確），大概就是在工業上，對一些模型進行某些力學分析等處理的時候，需要將模型細分為很多的小塊，用到的是有限元分析，
查資料的時候搜到的也基本是對三維模型，特別是CAD等的處理，
然后一個平面有限元網格劃分的結果，的確是有一點像路網的意思，再給他加上一些調整就更像了，
2.2. 前沿推進法/波前推進法（Advancing Front Technique）
進行有限元網格劃分的方法并不止一種，比較常見的有Delaunay法、映射法、AFT法等，通常也都是生成三角形，但是也有生成四邊形的，
我這里用到的就是AFT法，下面先大概講一下這個演算法的思路，主要參考的是李任君的論文，
- 首先是有一個邊界的多邊形資料（一般別人的邊界可以是曲線也可以是直線，我這就不搞那么復雜了，只有直線），如下圖，
- 然后把根據設定的單元格長度把一條長的邊離散開來，如下圖，
- 這一圈藍色的邊就稱作當前的前沿，然后開始遍歷前沿上的每一個點，判斷該點適合往里面生成一個怎樣的網格單元，生成一個網格單元就記錄起來，并且更新前沿，實其不包括已經生成出去的網格單元，然后一直重復直到整個前沿剩下最后一個小的網格單元，即生成完畢，如下圖的藍色邊界是一個已經生成了四個網格單元之后的前沿，
下圖藍色邊界是生成了更多網格單元之后的前沿，
下圖是生成完之后，已經沒有了前沿，
這個視頻就是一個動態的程序，其中也能看到橋邊把前沿劃分開的情況，（后面會提到橋邊的概念）
<iframe id="mYgxrBoQ-1612504567843" src="https://player.bilibili.com/player.html?aid=88416805&page=7" allowfullscreen="true" data-mediaembed="bilibili"></iframe>AFT動態可視化
3. 實作
3.1. 資料的定義
首先是節點和道路的定義，非常的簡單明了，稍微提一下就是，每一個節點和道路都需要一個唯一的ID，然后AftNode中的angle，其實是可以不用的，因為后面實際用到角度的時候我都是用一次當場計算一次的，這里存起來只是當時還在除錯演算法的時候，可視化角度用的，
public class AftNode
{
// ID
public readonly uint ID;
// 位置
public Vector3 Coord { get; }
// 該點內角角度
public float Angle;
/// <summary>
/// 建構式
/// </summary>
/// <param name="coord">該點的坐標</param>
/// <param name="id">ID</param>
public AftNode(Vector3 coord,uint id)
{
Coord = coord;
ID = id;
}
}
/// <summary>
/// 邊界線段
/// </summary>
public class AftEdge
{
// ID
public readonly uint ID;
// 開始的節點
public AftNode Begin { get; }
// 結束的節點
public AftNode End { get; }
// 所在的標準單元
public readonly List<StandardUnit> Units = new List<StandardUnit>();
/// <summary>
/// 建構式
/// </summary>
/// <param name="begin">開始節點</param>
/// <param name="end">結束節點</param>
/// <param name="id">ID</param>
public AftEdge(AftNode begin, AftNode end,uint id)
{
this.Begin = begin;
this.End = end;
ID = id;
}
/// <summary>
/// 解除與該邊界相關的標準單元格的關系
/// </summary>
public void DeleteRelateUit()
{
foreach (var unit in Units)
unit.Edges.Remove(this);
Units.Clear();
}
}
上面還有一個概念——標準單元，所謂的標準單元就是一個矩形，如下圖一個灰色的框框就是一個標準單元，
為什么需要引入標準單元這個概念呢？是因為在后面演算法的計算中，需要進行非常多次的線段碰撞判斷等操作，如果直接與所有的線段邊界都比較一次，那顯然開銷特別大，而且做了很多無用功，因為100條線段中，也許90條都根本不可能發生碰撞，因為他們相隔實在太遠了，
標準單元，記錄自身所包含的線段，每一個線段也記錄著他所相關的所有單元，比如上圖中綠色的一條線段，他所在的標準單元就是黃色的三個單元，當他要進行比較的時候只需要與這三個標準單元中所包含的線段比較即可，
下面是標準單元的定義，(X、Y其實不需要，因為后續演算法中是用一個二維陣列存盤所有的標準單元，直接通過計算索引就可以找到標準單元，這里只是我在將他可視化出來成黃色框框的時候，需要用到而已)
/// <summary>
/// 標準單元
/// </summary>
public class StandardUnit
{
// 標準單元內包含的邊界
public List<AftEdge> Edges = new List<AftEdge>();
// TEST 可視化的時候需要知道單元格的坐標，但實際上演算法中不需要坐標
public int X, Y;
}
這就是標準網格的存盤方式，
// 標準網格（由標準單元組成）
public static StandardUnit[,] StandardNet { get; private set; }
然后在生成一個小網格的時候，需要把它作為結果存起來，需要存下來的資料有頂點的位置，道路（包含兩個頂點），街區（包含多個道路），我使用字典的方式存盤，用他們的ID作為key，
public static readonly Dictionary<uint, Block> ResultBlocks = new Dictionary<uint, Block>();
public static readonly Dictionary<uint, Node> ResultNodes = new Dictionary<uint, Node>();
public static readonly Dictionary<uint, Road> ResultRoads = new Dictionary<uint, Road>();
這是結果類的定義，
/// <summary>
/// 一段道路的定義
/// </summary>
public class Road
{
// 道路的唯一ID
public uint ID { get; private set; }
// 起始節點
public Node Begin { get; private set; }
// 結束節點
public Node End { get; private set; }
// 道路等級
public ushort Level { get; private set; }
// TODO 建構式等未實作
public Road(uint id, Node begin, Node end)
{
ID = id;
Begin = begin;
End = end;
}
}
/// <summary>
/// 一個道路節點的定義
/// </summary>
public class Node
{
// 節點的唯一ID
public uint ID { get; private set; }
// 位置
public Vector3 Coord { get; private set; }
// 建構式
public Node(uint id, Vector3 coord)
{
ID = id;
Coord = coord;
}
}
/// <summary>
/// 一個街區的定義
/// </summary>
public class Block
{
// 街區的唯一ID
public uint ID { get; private set; }
public readonly List<Road> Edges;
public Block(uint id, List<Road> edges)
{
ID = id;
Edges = edges;
}
// TODO 更多內容未實作
}
然后整個前沿是以一個類物件的形式存在的，類為AdvancingFrontTechnique，部分定義如下圖所示，后面還有很多函式就不展示了，最后會放上完整的代碼，(IsDone可以忽視掉，在之前不完善的演算法中是用到這一個變數的，后面改進之后就不需要了，只是遺留在這里沒有洗掉，)
3.2. 邊界的分類
在前沿每一次往內推進的程序中，是需要生成新的邊界的，論文中是把邊界分成了三類，我這里根據我自己的想法稍微改了一下，分成了四類，
首先先說明一下，如上圖所示，圖中是整個前沿中截出來的一下段，假設現在正在處理第i個頂點（紅色是頂點，藍色是邊和角），此時其他點的名稱即分別為點i-1、點i+1、點i+2、點i+3，邊為邊i-1、邊i、邊i+1、邊i+3（邊i為點i與點i+1的連線），然后點i+1和點i+2所在的角度分別為a1、a2，
然后就是四種分類：
- 添加一條邊的情況（1）
如果此時a1<65°，且a2>90°，則將點i與點i+2相連作為新的邊，然后邊i、邊i+1、黃色的新邊就作為一個新的小網格存到結果中去，以及所包含的點和邊也是，并且把邊i、邊i+1從前沿中去掉，在該位置插入黃色的新邊，同時也去掉點i+1， - 添加一條邊的情況（2）
當65°<=a1<115°，且160°<=a1+a2<240°時，將點i與點i+3相連作為新的邊，與上面的情況一樣，洗掉點i+1、點i+2、邊i、邊i+1、邊i+2，并把邊i、邊i+1、邊i+2、黃色新邊所構成的網格作為新的結果存起來， - 添加兩條邊的情況
當65°<=a1<115°，200°<=a1+a2時，創建一個新頂點點t1，然后連接點i和點t1作為邊e1，以此類推，將邊e1、邊e2加入到前沿中，點t1也加入到前沿中，其他的該洗掉洗掉，該存結果存結果， - 添加三條邊的情況
和前面三種一個套路，話不多說，懂得都懂，
寫了個簡單的demo，大概效果就如下，有時候各種情況都不符合的，基本上當i到下一個的時候，或者下一輪生成的時候也就都生成了，
<iframe id="aTOBwvQu-1612411137771" src="https://player.bilibili.com/player.html?aid=88416805&page=6" allowfullscreen="true" data-mediaembed="bilibili"></iframe>
邊界分類
3.3. 生成一個小網格
生成一個網格主要是有一個private void GenerateABlock(int i)來搞定，這個也是整個演算法中最核心的一個函式，半數代碼都在這（當讓也是因為我寫的比較爛，感覺挺亂的），
前面的public List<AftNode> Nodes = new List<AftNode>();和public List<AftEdge> Edges = new List<AftEdge>();就是按照逆時針的順序存著當前的前沿中，所有的點和邊 （這里我用的List來存這個資料，其實是不妥當的，因為更新前沿時會經常的在中間進行插入和洗掉的操作，而且需要不斷地回圈，并且處理頂點的時候也是一個接著一個的處理，幾乎不怎么需要隨機讀取任意位置的資料，所以改用雙向回圈鏈表來存前沿的資料才是最合適的， 但是我寫到后期才意識到這個問題，而且可能是因為資料量的確不算大，即便用List的時候生成路網也是蠻快的，反正這個速度我可以接受，就懶得改了，不過為了處理跨越結尾的增刪操作等等，我還是寫了好多函式和求余操作去處理，的確實制造了挺多的麻煩） ，
然后GenerateABlock中的引數i的意思就是處理第i個節點的時候，就是根據前面提到的邊界分類，進行判斷然后處理，我就挑生成三條邊的情況稍微講一下，其他的情況也是按照思路寫就是了，
- 首先第一步判斷當前前沿中頂點的個數是否是6以下，即小于等于5，如果是的話，直接把剩下的所有頂點作為一個街區，然后清空前沿，結束，（其實論文中是以生成四邊形網格為目標，迫不得已就生成一個三角形，但是我覺得我的需求其實無所謂，5邊形我覺得也是可以接受的，所以我就這樣寫了）
// 當節點剩下的已經足夠少,直接組成Block
if (Nodes.Count < 6)
{
// 標記已執行
_executed = true;
// 添加街區
AddToResultBlock(Edges.ToArray());
// 清空
Nodes.Clear();
Edges.Clear();
// 標記結束
IsDone = true;
return;
}
- 然后就是按照邊界分類那部分講的一樣，計算
a1和a2的角度，這個AngleOf(int n)函式是我自己寫的，回傳的是前沿中第n個頂點所在的角度，求余是因為處理正好+1、+2之后跨越邊界饒了一圈的情況，
// 不需要比較的邊的ID
var noCompareIDs = new List<uint>();
// 求得下兩個頂點的角度之和
var angle1 = AngleOf((i + 1) % Nodes.Count);
var angle2 = AngleOf((i + 2) % Nodes.Count);
// 新加的邊界是否與已存在的邊界碰撞
var isCollide = false;
- 然后判斷當符合生成三條邊的時候，
if (angle1 >= 115 && angle1 < 220 && angle2 >= 115 && angle2 < 220)，繼續執行下面對應的函式， - 然后就是要生成出新的兩個點和三個邊，邊好說，只要有這幾個點，按順序直接連起來就好了，可是點要怎么求呢？我這里用到的方法就是定義
向量dir是一個從點i+1到點i+2的向量旋轉90度之后的向量，那么點i+1加上向量dir就是點t1的位置，點t2同理，當然這個向量dir需要先單位話然后再乘上單元格的長度，這樣就可以時得生成的網格中，每一個小段道路都是貼近單元格長度，不過我再此還加上了一個亂數（可以指定隨機種子），讓路網不至于太規規矩矩，這個時候生成出來的兩條邊都還是垂直于邊i+1的，因為是按照90度旋轉的，要是喜歡在這也可以加上一定的隨機，代碼里面用node1、node2存了以下就是不想后面每次用都寫Nodes[(i + 1) % Nodes.Count]這么麻煩，其實node1就是圖中的點i+1，node2就是點i+2，這里可以留意一下，我是寫了一個IdManger來管理ID，確保每一個ID都是唯一的，以及里面的WeightUnitLength函式，這里本來應該是直接寫的單元格長度，但是后來我加了一個控制密度的功能，就是我可以指定某一個區域的路網更稀疏或者更密集，我就可以通過這個函式獲取當前位置的長度應該是多少，當然目前這個函式背后只是很簡單的根據位置判斷了以下長度回傳回來，還處于測驗階段，
// 記錄一下node1 node2
AftNode node1 = Nodes[(i + 1) % Nodes.Count], node2 = Nodes[(i + 2) % Nodes.Count];
// 計算第一個點到第二個點的方向
var dir = node2.Coord - node1.Coord;
// 計算旋轉矩陣
var roateMat = Matrix4x4.Rotate(Quaternion.Euler(0, -90, 0));
// 計算并創建出第一個要添加的點
var testScale = RandomRange(0.9f, 1.1f);
Vector3 newDir = (roateMat * dir).normalized * (WeightUnitLength(node1.Coord.x,node1.Coord.z) * testScale);
var tempNode1 = new AftNode(node1.Coord + newDir, IdManager.GetNodeID());
// 計算第二個點到底一個點的方向（反轉即可）
dir *= -1;
// 計算旋轉矩陣
roateMat = Matrix4x4.Rotate(Quaternion.Euler(0, 90, 0));
// 計算并創建出第二個要添加的點
newDir = (roateMat * dir).normalized * (WeightUnitLength(node1.Coord.x,node1.Coord.z) * testScale);
var tempNode2 = new AftNode(node2.Coord + newDir, IdManager.GetNodeID());
// 計算新的三條邊
var tempEdge1 = new AftEdge(node1, tempNode1, IdManager.GetRoadID());
var tempEdge2 = new AftEdge(tempNode1, tempNode2, IdManager.GetRoadID());
var tempEdge3 = new AftEdge(tempNode2, node2, IdManager.GetRoadID());
- 然后就是給新加的這三條邊設定與標準單元的關系，用于等會計算碰撞，函式實作可以看最后放的完整代碼，反正這里就是設定了關系，
// 設定關系
SetUnitRelation(tempEdge1);
SetUnitRelation(tempEdge2);
SetUnitRelation(tempEdge3);
- 判斷新加入的邊是否與其他邊相互碰撞，如果有碰撞的話就說明無法按這個方式生成，首先我們可以知道，新加的邊本身，和相鄰的邊是不需要判斷碰撞的，而且因為他們是點對點的接在一起，甚至真有可能判斷為碰撞，所以先把不需要碰撞的邊的ID存一下，待會檢測的時候只要是這些ID就不需要比較，結合著上面的圖片看就會比較容易理解了，然后就是遍歷當前邊每一個有關系的單元中，所有有關系的邊，雖然這里是雙重回圈，但是一般來說一條邊最多只會和三個標準單元有關系（因為一條邊的長度就是按照標準單元的長度生成的），然后比較的時候，除非真的有碰撞，否則大多數情況除了不需要比較的ID，其他也沒多少需要比較的，一旦找到一個也直接跳出所有的判斷了，所以這里效率其實還算可以，但也不是沒法優化了，還是可能會出現再兩個單元格內都出現同一條邊，然后重復比較的情況，可以記錄一下比較過的邊的ID，但是這種情況感覺也不多，就算了，
// 判斷碰撞
// 設定不需要比較碰撞的ID(新加的邊以及幾個邊是不需要比較的)
noCompareIDs.Clear();
noCompareIDs.Add(tempEdge1.ID);
noCompareIDs.Add(tempEdge2.ID);
noCompareIDs.Add(tempEdge3.ID);
noCompareIDs.Add(Edges[(i + 1) % Edges.Count].ID);
// 遍歷新邊所在的所有標準單元
foreach (var unit in tempEdge2.Units)
// 遍歷每一個標準單元中的其他邊
foreach (var edge in unit.Edges)
// 如果發生碰撞，就記錄并跳出（不比較某些邊）
if (!noCompareIDs.Contains(edge.ID) && IsCollide(edge, tempEdge2))
{
isCollide = true;
// 跳出這個雙重回圈
goto outLoop;
}
noCompareIDs.Add(Edges[i].ID);
foreach (var unit in tempEdge1.Units)
// 遍歷每一個標準單元中的其他邊
foreach (var edge in unit.Edges)
// 如果發生碰撞，就記錄并跳出（不比較某些邊）
if (!noCompareIDs.Contains(edge.ID) && IsCollide(edge, tempEdge1))
{
isCollide = true;
// 跳出這個雙重回圈
goto outLoop;
}
noCompareIDs.Remove(Edges[i].ID);
noCompareIDs.Add(Edges[(i + 2) % Edges.Count].ID);
foreach (var unit in tempEdge3.Units)
// 遍歷每一個標準單元中的其他邊
foreach (var edge in unit.Edges)
// 如果發生碰撞，就記錄并跳出（不比較某些邊）
if (!noCompareIDs.Contains(edge.ID) && IsCollide(edge, tempEdge3))
{
isCollide = true;
// 跳出這個雙重回圈
goto outLoop;
}
outLoop:
- 如果檢測到碰撞
isCollide就會為true，那么說明這三條邊這樣生成是不行的，所以首先要解除他們與標準單元的關系，因為如果他們的資訊還存在里面，以后判斷別的邊的時候，很可能會將明明不碰撞的判斷為了碰撞，所以要把殘留的關系清除，同時因為剛才都給新增的頂點和邊界分配了唯一ID，如果不將ID識訓的話，將會浪費很多ID，（不過說實在的，我大概只需要幾千個，頂多上萬個街區就已經足夠了，uint這么多ID其實根本分配不完，但是能省則省吧）所以還需要跟IdManager說明移除這些分配過的ID，待會就還可以繼續分配，
// 清除關系
tempEdge1.DeleteRelateUit();
tempEdge2.DeleteRelateUit();
tempEdge3.DeleteRelateUit();
// 移除ID
IdManager.RemoveNodeID(tempNode1.ID);
IdManager.RemoveNodeID(tempNode2.ID);
IdManager.RemoveRoadID(tempEdge1.ID);
IdManager.RemoveRoadID(tempEdge2.ID);
IdManager.RemoveRoadID(tempEdge3.ID);
- 如果沒有碰撞，說明這樣的生成方法可行，那么就把該存到結果的存到結果，然后把新的邊和頂點加入到前沿中，同時把已經不屬于前沿的頂點和邊從前沿中刪去，
// 添加新Node到結果中
AddToResultNode(tempNode1);
AddToResultNode(tempNode2);
// 添加新Road到結果中
AddToResultRoad(tempEdge1);
AddToResultRoad(tempEdge2);
AddToResultRoad(tempEdge3);
// 添加新Block到結果中
AddToResultBlock(Edges[(i + 1) % Edges.Count], tempEdge3, tempEdge2, tempEdge1);
// 清除掉無用邊界與其標準單元的關系
Edges[(i + 1) % Edges.Count].DeleteRelateUit();
// 添加新頂點到前沿中
var tempNodeList = new List<AftNode>()
{
tempNode1,
tempNode2
};
Nodes.InsertRange((i + 2) % Nodes.Count, tempNodeList);
// 添加新邊界到前沿中
var tempEdgeList = new List<AftEdge>()
{
tempEdge1,
tempEdge2,
tempEdge3
};
Edges.InsertRange((i + 1) % Edges.Count, tempEdgeList);
// 洗掉無用邊界
RemoveEdgesInList((i + 4) % Edges.Count, 1);
至此，如果沒有問題的話，第i個頂點位置的一個小的網格就生成好了，有問題的話就不會生成，如果是因為碰撞導致的不生成，后面會直接用橋邊的方式解決，如果是不滿足四類的任何一種情況導致的不生成，那么要么就會在下一個點的時候生成，要么在下一輪的時候生成，很少會出現卡死的情況（目前還是有一定記錄出現到某些情況的時候會卡住，無法繼續往下生成，觀察后感覺主要是因為加入了密度改變的功能之后，當有時候一個小前沿中，怎么生成都會碰撞，但有的邊有太長而不符合橋邊的規則的時候會出現，這個后續有待優化，但是更換以下隨機種子還是很大程度上的暫時的解決這個問題），
3.4. 生成橋邊
當前沿兩邊靠的足夠近的時候，很容易就會出現，并且總是會出現怎么生成都會碰撞的情況，如下圖紅色圈起來的部分，到這里按照前面的分類生成肯定會碰撞，如果沒有生成橋邊的功能，那么演算法到這里將會卡死無法繼續生成，
當一個頂點可以找到一個足夠近的其他頂點的時候，可以將兩點連接起來，分為兩個前沿，然后再分別生成，
比如上圖中，C和H兩點已經足夠近了，可以直接連接生成橋邊，然后再分成左邊的前沿和右邊的前沿繼續生成，
只要遍歷一下一個點所在的標準單元以及附近的一圈的標準單元中，最近的那個點是否滿足足夠近的這個原則，就可以找到連接點，（為啥還需要判斷附近一圈的標準單元呢？因為很可能出現兩個點很近但是又處于相鄰的標準單元的情況），
但是還有一個要考慮的問題就是，假設當前的前沿如下圖所示，此時正在尋找第i個頂點適合連接橋邊的另一個頂點，如果單純按距離來算，很可能會找到紫色圈起來的頂點，很明顯這不是我們想要的橋邊，
我們想要的是如下圖黃色區域所示，這一區域中，最近的且滿足距離要求的點，
我這里是利用向量的計算，判斷這個頂點是否屬于黃色一邊的區域，這是在檢測線段碰撞的方法中得到啟發所改寫的，
/// <summary>
/// 找到距離該點，最近的（下限以內）且是左側的點的坐標
/// </summary>
/// <param name="currentIndex">需要判斷的點</param>
/// <param name="noCompareIDs">不需要判斷的邊的ID</param>
/// <param name="p1">比較點前一個點坐標</param>
/// <param name="p2">比較點坐標</param>
/// <param name="p3">比較點下一個點坐標</param>
/// <returns></returns>
private int FindClosestNodeIndex(int currentIndex, ICollection<uint> noCompareIDs, Vector3 p1, Vector3 p2, Vector3 p3)
{
// 計算這個坐標位于的標準網格索引
int indexX = (int) Math.Floor((Nodes[currentIndex].Coord.x - StartCoordinate.x) / StandardUintLength),
indexY = (int) Math.Floor((Nodes[currentIndex].Coord.z - StartCoordinate.z) / StandardUintLength);
// 暫存最近距離
var tempDistance = StandardUintLength * 100;
AftNode tempNode = null;
// 遍歷附近包括自己所在的9個標準單元
for (var x = Math.Max(0, indexX - 1); x <= Math.Min(indexX + 1, StandardNet.GetLength(0) - 1); x++)
{
for (var y = Math.Max(0, indexY - 1); y <= Math.Min(indexY + 1, StandardNet.GetLength(1) - 1); y++)
{
// 遍歷每個單元內需要比較的邊
foreach (var edge in StandardNet[x, y].Edges)
{
// 去除不需要比較的情況
if (noCompareIDs.Contains(edge.ID)) continue;
var distance = Vector3.Distance(edge.Begin.Coord, Nodes[currentIndex].Coord);
// 判斷該線段上兩個端點有沒有足夠近的頂點
// TODO 1.35有待考究
if (distance < tempDistance && distance < WeightUnitLength(Nodes[currentIndex].Coord.x,Nodes[currentIndex].Coord.z) * 1.35f)
{
if (Vector3.SignedAngle(p2 - p1, p3 - p2, Vector3.up) > 0)
{
if (CrossVec2(edge.Begin.Coord - p1, p2 - p1) < 0 ||
CrossVec2(edge.Begin.Coord - p2, p3 - p2) < 0)
// 在左側
{
tempDistance = distance;
tempNode = edge.Begin;
}
}
else
{
if (CrossVec2(edge.Begin.Coord - p1, p2 - p1) < 0 &&
CrossVec2(edge.Begin.Coord - p2, p3 - p2) < 0) // 在左側
{
tempDistance = distance;
tempNode = edge.Begin;
}
}
}
distance = Vector3.Distance(edge.End.Coord, Nodes[currentIndex].Coord);
if (distance < tempDistance && distance < WeightUnitLength(Nodes[currentIndex].Coord.x,Nodes[currentIndex].Coord.z) * 1.35f)
{
if (Vector3.SignedAngle(p1 - p2, p2 - p3, Vector3.up) > 0)
{
if (CrossVec2(edge.End.Coord - p1, p2 - p1) < 0 ||
CrossVec2(edge.End.Coord - p2, p3 - p2) < 0) // 在左側
{
tempDistance = distance;
tempNode = edge.End;
}
}
else
{
if (CrossVec2(edge.End.Coord - p1, p2 - p1) < 0 &&
CrossVec2(edge.End.Coord - p2, p3 - p2) < 0) // 在左側
{
tempDistance = distance;
tempNode = edge.End;
}
}
}
}
}
}
if (tempNode != null) return Nodes.IndexOf(tempNode);
// 沒有找到
return -1;
}
然后就是在處理完第i個頂點所生成的網格之后，順帶如下面代碼一樣，判斷一下是否有可以生成橋邊的情況，如果有則生成橋邊，并且將當前前沿根據橋邊劃分為兩部分，一部分繼續生成，另一部分存到_edgesLinkedList和_nodesLinkedList鏈表中，直到當前前沿生成結束，節生成鏈表中的下一個前沿，
// 判斷有沒有距離該節點很近的其他非鄰邊節點
noCompareIDs.Clear();
noCompareIDs.Add(Edges[i > 0 ? i - 1 : Edges.Count - 1].ID);
noCompareIDs.Add(Edges[i].ID);
noCompareIDs.Add(Edges[(i + 1) % Edges.Count].ID);
noCompareIDs.Add(Edges[(i + 2) % Edges.Count].ID);
// 找到一個最近的，并且位于左側的一個符合距離的頂點
var closestIndex = FindClosestNodeIndex((i + 1) % Nodes.Count, noCompareIDs,
Nodes[i].Coord,
Nodes[(i + 1) % Nodes.Count].Coord,
Nodes[(i + 2) % Nodes.Count].Coord);
// 如果找到
if (closestIndex >= 0)
{
// 標記已執行
_executed = true;
// 【注意】此ID由兩個方向的邊用，但實際是一條邊，任意一條邊加入結果即可
var brigeEdgeID = IdManager.GetRoadID();
// 創建橋邊
var brigeEdge = new AftEdge(Nodes[closestIndex], Nodes[(i + 1)%Nodes.Count], brigeEdgeID);
// 添加到結果中
AddToResultRoad(brigeEdge);
// 創建橋邊分割開來的另一半的頂點和邊
var newNodes = CopyRangeInNodes((i + 1) % Nodes.Count, closestIndex);
var newEdges = CopyRangeInEdges((i + 1) % Edges.Count, closestIndex > 0 ? closestIndex - 1 : Edges.Count - 1);
newEdges.Add(brigeEdge);
// 將新的邊界和頂點存到鏈表后，用于以后繼續生成，代替遞回
_edgesLinkedList.AddLast(newEdges);
_nodesLinkedList.AddLast(newNodes);
// 洗掉掉已經劃分的邊和頂點
// 計算需要刪掉幾個邊
var deleteEdgeCount = (Edges.Count + closestIndex - i - 1) % Edges.Count;
// 添加橋邊
Edges.Insert((i + 1) % Edges.Count, new AftEdge(Nodes[(i + 1) % Nodes.Count], Nodes[closestIndex], brigeEdgeID));
// 洗掉多余邊
RemoveEdgesInList((i + 2) % Edges.Count, deleteEdgeCount);
// 洗掉多余頂點
RemoveNodesInList((i + 2) % Nodes.Count, deleteEdgeCount - 1);
}
這一部分的時候我遇到一個坑，一開始我不是這樣寫的，一開始我是生成橋邊之后，用劃分出來的另一半生成一個新的AdvancingFrontTechnique物件，然后讓他繼續劃分，直到所有結束，是一種遞回的思想，當然這種方法沒問題，是對的，實驗出來的結果也OK，（那個IsDone也是這個地方用的，當IsDone為true就說明這個前沿生成完畢，就回傳到剛才的前沿接著生成）
但是當我單元網格長度越挑調小，也就是密度越來越高，資料越來越大的時候，Unity閃退了，真的是突然就閃退，也沒有崩潰日志，就像有一個臨界值，只要密度超過那個他就閃退，我被這個問題難了幾乎整整一天，也和群里的同學討論了很久，一開始認為是unity的問題，后來又感覺不是，覺得是不是記憶體爆了（但是任務管理器看記憶體是好好的，占用很少，啥都沒爆），并且單步除錯看到閃退前的資料量也不大，也就幾千，真是百思不得其解，甚至當晚我下單了一條8G記憶體第二天到貨（雖然后來在記憶體到之前我就把問題解決了），企圖的解決這個問題，
然后第二天早上我就嘗試著把這個演算法直接粘到vs的專案里面運行，看看是不是unity的問題，不過由于我還是用了不少uinity給的數學運算，不在unity里面都沒法用，好在github上有這一部分原始碼，我就照著拿了一些過來用，改了以下終于能跑了，然后測驗了和在unity中運行時會閃退的資料，VS終于給了我一個結果，
堆疊溢位，
好家伙終于把問題找到了，原來是堆疊溢位，Unity要早報這個錯我早解決了，下圖是用Rider除錯的時候，閃退前的堆疊情況，左邊那個長到令人發指的就是不停的劃分橋邊生成新物件并且呼叫函式用到的堆疊，簡單的上網查了以下，貌似是c#一個行程的堆疊大小就只給你1m，也沒法改，像我這樣整肯定就溢位了，
然后我才把這段代碼改成前面那樣用鏈表存著劃分出來的另一個前沿，然后用下面這種形式來控制所有的前沿來生成，
public void GenOnce()
{
while (_edgesLinkedList.Count > 0 && _nodesLinkedList.Count > 0)
{
_executed = false;
if(Nodes != null && Edges != null){
if (Nodes.Count == 0 && Edges.Count == 0)
{
_nodesLinkedList.RemoveFirst();
_edgesLinkedList.RemoveFirst();
if (_nodesLinkedList.Count > 0 && _edgesLinkedList.Count > 0)
{
Nodes = _nodesLinkedList.First.Value;
Edges = _edgesLinkedList.First.Value;
}
}
if(Nodes != null && Edges!= null)
for (var i = 0; i < Nodes.Count; i++)
GenerateABlock(i);
}
if (!_executed && _edgesLinkedList.Count > 0 && _nodesLinkedList.Count > 0)
{
Debug.LogWarning("檢測到死回圈，跳出！");
return;
}
}
}
4. 完整代碼
基本的思想就在前面講了一遍，下面是完整的代碼，多很多函式的實作，也多了一些細節，注釋也很充足，(同時也有很多沒用的代碼在里面，不用太在意)
當然現在我這個東西其實也還是個半成品，不少東西還不完善，也還處于測驗的狀態，說不定還會有BUG存在，
有什么問題也歡迎交流，
4.1. 一些定義或輔助
using System.Collections.Generic;
using UnityEngine;
namespace RoadNetwork
{
/// <summary>
/// 整個地圖的資料
/// </summary>
public class RoadMap
{
// 所有道路節點
public Dictionary<uint, Node> Nodes { get; private set; }
// 所有道路
public Dictionary<uint, Road> Roads { get; private set; }
// 所有街區
public Dictionary<uint, Block> Blocks { get; private set; }
// TODO 未實作
}
/// <summary>
/// 一段道路的定義
/// </summary>
public class Road
{
// 道路的唯一ID
public uint ID { get; private set; }
// 起始節點
public Node Begin { get; private set; }
// 結束節點
public Node End { get; private set; }
// 道路等級
public ushort Level { get; private set; }
// TODO 建構式等未實作
public Road(uint id, Node begin, Node end)
{
ID = id;
Begin = begin;
End = end;
}
}
/// <summary>
/// 一個道路節點的定義
/// </summary>
public class Node
{
// 節點的唯一ID
public uint ID { get; private set; }
// 位置
public Vector3 Coord { get; private set; }
// 建構式
public Node(uint id, Vector3 coord)
{
ID = id;
Coord = coord;
}
}
/// <summary>
/// 一個街區的定義
/// </summary>
public class Block
{
// 街區的唯一ID
public uint ID { get; private set; }
public readonly List<Road> Edges;
public Block(uint id, List<Road> edges)
{
ID = id;
Edges = edges;
}
// TODO 更多內容未實作
}
}
using System.Collections.Generic;
namespace RoadNetwork
{
public static class IdManager
{
// 當前的最大ID（已分配）
// 0不會被分配
public static uint currentNodeID { get; private set; }
public static uint currentRoadID { get; private set; }
public static uint currentBlcokID { get; private set; }
// 被移除掉的ID，獲取ID時會優先分配這些ID，以免浪費ID
private static Queue<uint> _removedNodeID = new Queue<uint>();
private static Queue<uint> _removedRoadID = new Queue<uint>();
private static Queue<uint> _removedBlockID = new Queue<uint>();
/// <summary>
/// 所有都進行初始化
/// </summary>
public static void Initialization()
{
InitNode();
InitRoad();
InitBlock();
}
/// <summary>
/// 僅初始化節點
/// </summary>
public static void InitNode()
{
currentNodeID = 0;
_removedNodeID.Clear();
}
/// <summary>
/// 僅初始化道路
/// </summary>
public static void InitRoad()
{
currentRoadID = 0;
_removedRoadID.Clear();
}
/// <summary>
/// 僅初始化街區
/// </summary>
public static void InitBlock()
{
currentBlcokID = 0;
_removedBlockID.Clear();
}
/// <summary>
/// 獲取當前的節點唯一ID
/// </summary>
/// <returns></returns>
public static uint GetNodeID()
{
// 優先分配已洗掉的ID
if (_removedNodeID.Count > 0) return _removedNodeID.Dequeue();
return ++currentNodeID;
}
/// <summary>
/// 獲取當前的道路唯一ID
/// </summary>
/// <returns></returns>
public static uint GetRoadID()
{
// 優先分配已洗掉的ID
if (_removedRoadID.Count > 0) return _removedRoadID.Dequeue();
return ++currentRoadID;
}
/// <summary>
/// 獲取當前的街區唯一ID
/// </summary>
/// <returns></returns>
public static uint GetBlockID()
{
// 優先分配已洗掉的ID
if (_removedBlockID.Count > 0) return _removedBlockID.Dequeue();
return ++currentBlcokID;
}
/// <summary>
/// 去除掉這一個ID
/// </summary>
/// <param name="id"></param>
public static void RemoveNodeID(uint id)
{
_removedNodeID.Enqueue(id);
}
/// <summary>
/// 去除掉這一個ID
/// </summary>
/// <param name="id"></param>
public static void RemoveRoadID(uint id)
{
_removedRoadID.Enqueue(id);
}
/// <summary>
/// 去除掉這一個ID
/// </summary>
/// <param name="id"></param>
public static void RemoveBlockID(uint id)
{
_removedBlockID.Enqueue(id);
}
}
}
4.2. AFT演算法
using System;
using System.Collections.Generic;
using UnityEngine;
namespace RoadNetwork
{
public class AdvancingFrontTechnique
{
// 該前沿是否生成完成
public bool IsDone { get; private set; }
// 當前多邊形邊界的所有頂點
private readonly LinkedList<List<AftNode>> _nodesLinkedList = new LinkedList<List<AftNode>>();
public List<AftNode> Nodes = new List<AftNode>();
// 當前多邊形邊界的所有邊界線段
private readonly LinkedList<List<AftEdge>> _edgesLinkedList = new LinkedList<List<AftEdge>>();
public List<AftEdge> Edges = new List<AftEdge>();
// 單個標準單元的長度
public float StandardUintLength { get; }
// 標準網格（由標準單元組成）
public static StandardUnit[,] StandardNet { get; private set; }
// 網格起始點
public Vector3 StartCoordinate { get; private set; }
// 生成的結果
public static readonly Dictionary<uint, Block> ResultBlocks = new Dictionary<uint, Block>();
public static readonly Dictionary<uint, Node> ResultNodes = new Dictionary<uint, Node>();
public static readonly Dictionary<uint, Road> ResultRoads = new Dictionary<uint, Road>();
// 亂數
private static System.Random _random;
// TODO 建構式
public AdvancingFrontTechnique(IEnumerable<Vector3> coords, float unitLength = 1,int randomSeed = 0)
{
// 初始化
IsDone = false;
ResultBlocks.Clear();
ResultNodes.Clear();
ResultRoads.Clear();
// TODO
_nodesLinkedList.AddLast(Nodes);
_edgesLinkedList.AddLast(Edges);
_random = new System.Random(randomSeed);
// 創建節點
foreach (var point in coords)
Nodes.Add(new AftNode(point, IdManager.GetNodeID()));
// 引數傳遞
StandardUintLength = unitLength;
// 離散邊界
DisperseNodes(ref Nodes);
// 生成邊
for (var i = 0; i < Nodes.Count - 1; i++)
Edges.Add(new AftEdge(Nodes[i], Nodes[i + 1], IdManager.GetRoadID()));
// 最后一條邊
Edges.Add(new AftEdge(Nodes[Nodes.Count - 1], Nodes[0], IdManager.GetRoadID()));
// 生成標準網格
GenerateStandardNet(Nodes);
// TEST 計算所有頂點的角度
for (var i = 0; i < Nodes.Count; i++)
Nodes[i].Angle = AngleOf(i);
// 把最初的邊界和頂點加入到結果中
foreach (var node in Nodes)
AddToResultNode(node);
foreach (var edge in Edges)
AddToResultRoad(edge);
}
/// <summary>
/// 離散頂點，在兩個頂點之間距離過長的中間插入頂點
/// </summary>
/// <param name="nodes"></param>
private void DisperseNodes(ref List<AftNode> nodes)
{
for (var i = 0; i < nodes.Count; i++)
{
// 計算該頂點與下一頂點的位置
float distance = Vector3.Distance(nodes[i].Coord, nodes[(i + 1) % nodes.Count].Coord);
// 當距離超過一定限度就需要進行劃分
// TODO 這個1.5應該還需要考究
if (distance > StandardUintLength * 1.5f)
{
// 計算中間需要拆分的數量
var partsCount = (int) Math.Floor(distance / StandardUintLength) + 1;
var tempList = new List<AftNode>();
for (var j = 1; j < partsCount; j++)
{
// 通過插值計算位置并插入新的List中
tempList.Add(new AftNode(
Vector3.Lerp(
nodes[i].Coord,
nodes[(i + 1) % nodes.Count].Coord,
(float) j / partsCount), IdManager.GetNodeID()));
}
// 插入到原來的List中
nodes.InsertRange(i + 1, tempList);
// 新加入的節點已經符合要求，不需要繼續判斷，可以直接跳過
i += partsCount - 1;
}
}
}
/// <summary>
/// 生成標準網格
/// </summary>
/// <param name="coords">邊界資料</param>
private void GenerateStandardNet(List<AftNode> coords)
{
// 找到邊界的XY值
FindEdgePoints(coords, out var minX, out var maxX, out var minZ, out var maxZ);
// 計算所需的單元個數
int xCount = (int) Math.Ceiling((maxX - minX) / StandardUintLength),
zCount = (int) Math.Ceiling((maxZ - minZ) / StandardUintLength);
// 初始化標準網格
StandardNet = new StandardUnit[xCount, zCount];
for (var i = 0; i < xCount; i++)
{
for (var j = 0; j < zCount; j++)
{
StandardNet[i, j] = new StandardUnit();
// TEST 可視化的時候需要知道單元格的坐標，但實際上演算法中不需要坐標
StandardNet[i, j].X = i;
StandardNet[i, j].Y = j;
}
}
// 初始化網格起始點
StartCoordinate = new Vector3(minX, 0, minZ);
// 設定當前所有邊的關系
foreach (var edge in Edges)
SetUnitRelation(edge);
}
// 是否執行了操作，用來檢測死回圈 // 初始化為false
private bool _executed;
//private int counter = 0;
public void GenOnce()
{
// while (_edgesLinkedList.Count > 0 && _nodesLinkedList.Count > 0)
// // {
// _executed = false;
//
// if(Nodes != null && Edges != null){
// if (Nodes.Count == 0 && Edges.Count == 0)
// {
// _nodesLinkedList.RemoveFirst();
// _edgesLinkedList.RemoveFirst();
// if (_nodesLinkedList.Count > 0 && _edgesLinkedList.Count > 0)
// {
// Nodes = _nodesLinkedList.First.Value;
// Edges = _edgesLinkedList.First.Value;
// }
// }
// // if(Nodes != null && Edges!= null)
// // for (var i = 0; i < Nodes.Count; i++)
// GenerateABlock((counter++)%Nodes.Count);
// }
//
// if (!_executed && _edgesLinkedList.Count > 0 && _nodesLinkedList.Count > 0)
// {
// Debug.LogWarning("檢測到死回圈，跳出！");
// return;
// }
// //}
while (_edgesLinkedList.Count > 0 && _nodesLinkedList.Count > 0)
{
_executed = false;
if(Nodes != null && Edges != null){
if (Nodes.Count == 0 && Edges.Count == 0)
{
_nodesLinkedList.RemoveFirst();
_edgesLinkedList.RemoveFirst();
if (_nodesLinkedList.Count > 0 && _edgesLinkedList.Count > 0)
{
Nodes = _nodesLinkedList.First.Value;
Edges = _edgesLinkedList.First.Value;
}
}
if(Nodes != null && Edges!= null)
for (var i = 0; i < Nodes.Count; i++)
GenerateABlock(i);
}
if (!_executed && _edgesLinkedList.Count > 0 && _nodesLinkedList.Count > 0)
{
Debug.LogWarning("檢測到死回圈，跳出！");
return;
}
}
}
// TODO 待完善
/// <summary>
/// 在該點生成一個街區
/// </summary>
/// <param name="i">頂點的索引</param>
private void GenerateABlock(int i)
{
// 當節點剩下的已經足夠少,直接組成Block
if (Nodes.Count < 6)
{
// 標記已執行
_executed = true;
// 添加街區
AddToResultBlock(Edges.ToArray());
// 清空
Nodes.Clear();
Edges.Clear();
// 標記結束
IsDone = true;
return;
}
var noCompareIDs = new List<uint>();
// 求得下兩個頂點的角度之和
var angle1 = AngleOf((i + 1) % Nodes.Count);
var angle2 = AngleOf((i + 2) % Nodes.Count);
// 新加的邊界是否與已存在的邊界碰撞
var isCollide = false;
// 只需要添加一條新線段的情況（角度特別小）
// TODO 角度需要研究
if (angle1 < 65 && angle2 > 90)
{
// 創建出需要添加的邊
var tempEdge = new AftEdge(Nodes[i], Nodes[(i + 2) % Nodes.Count], IdManager.GetRoadID());
// 判斷該邊是否與附近的其他邊相交
// 先設定新邊與標準單元格的關系
SetUnitRelation(tempEdge);
// 設定不需要比較的ID(新加的邊以及幾個邊是不需要比較的 )
noCompareIDs.Clear();
noCompareIDs.Add(tempEdge.ID);
noCompareIDs.Add(Edges[i > 0 ? i - 1 : Edges.Count - 1].ID);
noCompareIDs.Add(Edges[i].ID);
noCompareIDs.Add(Edges[(i + 1) % Edges.Count].ID);
noCompareIDs.Add(Edges[(i + 2) % Edges.Count].ID);
// 遍歷新邊所在的所有標準單元
foreach (var unit in tempEdge.Units)
{
// 遍歷每一個標準單元中的其他邊
foreach (var edge in unit.Edges)
{
// 如果發生碰撞，就記錄并跳出（不比較某些邊）
if (!noCompareIDs.Contains(edge.ID) && IsCollide(edge, tempEdge))
{
isCollide = true;
// 跳出這個雙重回圈
goto outLoop;
}
}
}
outLoop:
// 如果沒有相交
if (!isCollide)
{
// 標記已執行
_executed = true;
// 把新加的邊加入結果中
AddToResultRoad(tempEdge);
// 清除掉無用邊界與其標準單元的關系
Edges[i].DeleteRelateUit();
Edges[(i + 1) % Edges.Count].DeleteRelateUit();
// 添加街區到結果中
AddToResultBlock(Edges[i], Edges[(i + 1) % Edges.Count], tempEdge);
// 把新邊界加入到前沿中
Edges.Insert(i, tempEdge);
// 洗掉無用邊界
RemoveEdgesInList((i + 1) % Edges.Count, 2);
// 洗掉無用頂點
RemoveNodesInList((i + 1) % Nodes.Count, 1);
}
// 如果有相交
else
{
tempEdge.DeleteRelateUit();
IdManager.RemoveRoadID(tempEdge.ID);
// 去判斷最近
//goto checkClose;
}
}
// 只需要添加一條新線段的情況
// TODO 角度需要研究
else if (angle1 >= 65 && angle1 < 115 && angle1 + angle2 >= 160 && angle1 + angle2 < 240)
{
// TEST
if(Vector3.Distance(Nodes[i].Coord,Nodes[(i + 3) % Nodes.Count].Coord) < WeightUnitLength(Nodes[i].Coord.x,Nodes[i].Coord.z) * 0.8f) return;
// 創建出需要添加的邊
var tempEdge = new AftEdge(Nodes[i], Nodes[(i + 3) % Nodes.Count], IdManager.GetRoadID());
// 判斷該邊是否與附近的其他邊相交
// 先設定新邊與標準單元格的關系
SetUnitRelation(tempEdge);
// 設定不需要比較的ID(新加的邊以及幾個邊是不需要比較的 )
noCompareIDs.Clear();
noCompareIDs.Add(tempEdge.ID);
noCompareIDs.Add(Edges[i > 0 ? i - 1 : Edges.Count - 1].ID);
noCompareIDs.Add(Edges[i].ID);
noCompareIDs.Add(Edges[(i + 1) % Edges.Count].ID);
noCompareIDs.Add(Edges[(i + 2) % Edges.Count].ID);
noCompareIDs.Add(Edges[(i + 3) % Edges.Count].ID);
// 遍歷新邊所在的所有標準單元
foreach (var unit in tempEdge.Units)
{
// 遍歷每一個標準單元中的其他邊
foreach (var edge in unit.Edges)
{
// 如果發生碰撞，就記錄并跳出（不比較某些邊）
if (!noCompareIDs.Contains(edge.ID) && IsCollide(edge, tempEdge))
{
isCollide = true;
// 跳出這個雙重回圈
goto outLoop;
}
}
}
outLoop:
// 如果沒有相交
if (!isCollide)
{
// 標記已執行
_executed = true;
// 新加入的邊和頂點
var newEdges = new List<AftEdge>();
var newNodes = new List<AftNode>();
// 判斷新加入的邊是否過長
var distance = Vector3.Distance(tempEdge.Begin.Coord, tempEdge.End.Coord);
if (distance > 1.5 * WeightUnitLength(tempEdge.Begin.Coord.x,tempEdge.Begin.Coord.z))
{
// 如果過長 拆分為多段加入
// 取消邊的ID
IdManager.RemoveRoadID(tempEdge.ID);
// 計算中間需要拆分的數量
var partsCount = (int) Math.Floor(distance / WeightUnitLength(tempEdge.Begin.Coord.x,tempEdge.Begin.Coord.z)) + 1;
// 計算頂點
for (var j = 1; j < partsCount; j++)
{
// 通過插值計算位置并插入新的List中
newNodes.Add(new AftNode(
Vector3.Lerp(
tempEdge.Begin.Coord,
tempEdge.End.Coord,
(float) j / partsCount), IdManager.GetNodeID()));
}
// 計算新邊
// 第一個邊
newEdges.Add(new AftEdge(tempEdge.Begin,newNodes[0],IdManager.GetRoadID()));
// 中間的邊
for (var j = 0; j < newNodes.Count - 1; j++)
newEdges.Add(new AftEdge(newNodes[j],newNodes[j+1],IdManager.GetRoadID()));
// 最后一個邊
newEdges.Add(new AftEdge(newNodes[newNodes.Count - 1],tempEdge.End,IdManager.GetRoadID()));
}
else
{
newEdges.Add(tempEdge);
}
// 把新加的邊和頂點加入結果中
foreach (var node in newNodes)
AddToResultNode(node);
foreach (var edge in newEdges)
AddToResultRoad(edge);
// 清除掉無用邊界與其標準單元的關系
Edges[i].DeleteRelateUit();
Edges[(i + 1) % Edges.Count].DeleteRelateUit();
Edges[(i + 2) % Edges.Count].DeleteRelateUit();
// 添加街區到結果中 // TODO
var edgesToBlock = new List<AftEdge>();
edgesToBlock.Add(Edges[i]);
edgesToBlock.Add(Edges[(i + 1) % Edges.Count]);
edgesToBlock.Add(Edges[(i + 2) % Edges.Count]);
// 反轉一下
newEdges.Reverse();
edgesToBlock.AddRange(newEdges);
AddToResultBlock(edgesToBlock.ToArray());
// 回傳來
newEdges.Reverse();
//AddToResultBlock(Edges[i], Edges[(i + 1) % Edges.Count], Edges[(i + 2) % Edges.Count], tempEdge);
// 把新邊界加入到前沿中
Edges.InsertRange(i, newEdges);
// 洗掉無用邊界
RemoveEdgesInList((i + newEdges.Count) % Edges.Count, 3);
// 如果有新頂點就加入
if (newNodes.Count > 0)
Nodes.InsertRange(i + 1, newNodes);
// 洗掉無用頂點
RemoveNodesInList((i + 1 + newNodes.Count) % Nodes.Count, 2);
}
// 如果有相交
else
{
tempEdge.DeleteRelateUit();
IdManager.RemoveRoadID(tempEdge.ID);
// 去判斷最近
//goto checkClose;
}
}
// 需要添加兩條線段的情況
else if (angle1 < 115 && angle1 > 65 && angle1 + angle2 > 200)
{
// 記錄一下node1 node2
AftNode node1 = Nodes[(i + 1) % Nodes.Count], node2 = Nodes[(i + 2) % Nodes.Count];
// 計算第i點到第一個點的方向
var dir = node2.Coord -node1.Coord;
// 計算旋轉矩陣
var roateMat = Matrix4x4.Rotate(Quaternion.Euler(0, -angle1 + RandomRange(-2,2), 0));
// 計算并創建出第一個要添加的點
// TEST 加個隨機的縮放看效果如何
//var testScale = UnityEngine.Random.Range(0.95f, 1.05f);
//var testScale = 1f;
var testScale = RandomRange(0.9f, 1.1f);
dir = (roateMat * dir).normalized * (WeightUnitLength(node1.Coord.x,node1.Coord.z) * testScale);
var tempNode = new AftNode(node2.Coord + dir, IdManager.GetNodeID());
// 創建倆個新的邊
var tempEdge1 = new AftEdge(Nodes[i], tempNode, IdManager.GetRoadID());
var tempEdge2 = new AftEdge(tempNode, node2, IdManager.GetRoadID());
// 設定關系
SetUnitRelation(tempEdge1);
SetUnitRelation(tempEdge2);
// 判斷碰撞
// 設定不需要比較碰撞的ID(新加的邊以及幾個邊是不需要比較的)
noCompareIDs.Clear();
noCompareIDs.Add(tempEdge1.ID);
noCompareIDs.Add(tempEdge2.ID);
noCompareIDs.Add(Edges[i > 0 ? i - 1 : Edges.Count - 1].ID);
noCompareIDs.Add(Edges[i].ID);
noCompareIDs.Add(Edges[(i + 1) % Edges.Count].ID);
// 遍歷新邊所在的所有標準單元
foreach (var unit in tempEdge1.Units)
// 遍歷每一個標準單元中的其他邊
foreach (var edge in unit.Edges)
// 如果發生碰撞，就記錄并跳出（不比較某些邊）
if (!noCompareIDs.Contains(edge.ID) && IsCollide(edge, tempEdge1))
{
isCollide = true;
// 跳出這個雙重回圈
goto outLoop;
}
noCompareIDs.Remove(Edges[i > 0 ? i - 1 : Edges.Count - 1].ID);
noCompareIDs.Remove(Edges[i].ID);
noCompareIDs.Add(Edges[(i + 2) % Edges.Count].ID);
foreach (var unit in tempEdge2.Units)
// 遍歷每一個標準單元中的其他邊
foreach (var edge in unit.Edges)
// 如果發生碰撞，就記錄并跳出（不比較某些邊）
if (!noCompareIDs.Contains(edge.ID) && IsCollide(edge, tempEdge2))
{
isCollide = true;
// 跳出這個雙重回圈
goto outLoop;
}
outLoop:
// 如果沒有碰撞
if (!isCollide)
{
// 標記已執行
_executed = true;
// 添加新Node到結果中
AddToResultNode(tempNode);
// 添加新Road到結果中
AddToResultRoad(tempEdge1);
AddToResultRoad(tempEdge2);
// 添加新Block到結果中
AddToResultBlock(Edges[i], Edges[(i + 1) % Edges.Count], tempEdge2, tempEdge1);
// 清除掉無用邊界與其標準單元的關系
Edges[i].DeleteRelateUit();
Edges[(i + 1) % Edges.Count].DeleteRelateUit();
// 直接替換頂點
Nodes[(i + 1) % Nodes.Count] = tempNode;
// 直接替換
Edges[i] = tempEdge1;
Edges[(i + 1) % Edges.Count] = tempEdge2;
}
// 如果有碰撞
else
{
// 清除關系
tempEdge1.DeleteRelateUit();
tempEdge2.DeleteRelateUit();
// 移除ID
IdManager.RemoveNodeID(tempNode.ID);
IdManager.RemoveRoadID(tempEdge1.ID);
IdManager.RemoveRoadID(tempEdge2.ID);
// 去判斷最近
//goto checkClose;
}
}
// 需要添加三條線段的情況
else if (angle1 >= 115 && angle1 < 220 && angle2 >= 115 && angle2 < 220)
{
// 記錄一下node1 node2
AftNode node1 = Nodes[(i + 1) % Nodes.Count], node2 = Nodes[(i + 2) % Nodes.Count];
// 計算第一個點到第二個點的方向
var dir = node2.Coord - node1.Coord;
// 計算旋轉矩陣
var roateMat = Matrix4x4.Rotate(Quaternion.Euler(0, -90, 0));
// 計算并創建出第一個要添加的點
// TEST 加個隨機的縮放看效果如何
//float testScale = UnityEngine.Random.Range(0.8f, 1.1f);
//var testScale = 1;
var testScale = RandomRange(0.9f, 1.1f);
Vector3 newDir = (roateMat * dir).normalized * (WeightUnitLength(node1.Coord.x,node1.Coord.z) * testScale);
var tempNode1 = new AftNode(node1.Coord + newDir, IdManager.GetNodeID());
// 計算第二個點到底一個點的方向（反轉即可）
dir *= -1;
// 計算旋轉矩陣
roateMat = Matrix4x4.Rotate(Quaternion.Euler(0, 90, 0));
// 計算并創建出第二個要添加的點
// TEST 加個隨機的縮放看效果如何
//testScale = UnityEngine.Random.Range(0.8f, 1.1f);
newDir = (roateMat * dir).normalized * (WeightUnitLength(node1.Coord.x,node1.Coord.z) * testScale);
var tempNode2 = new AftNode(node2.Coord + newDir, IdManager.GetNodeID());
// 計算新的三條邊
var tempEdge1 = new AftEdge(node1, tempNode1, IdManager.GetRoadID());
var tempEdge2 = new AftEdge(tempNode1, tempNode2, IdManager.GetRoadID());
var tempEdge3 = new AftEdge(tempNode2, node2, IdManager.GetRoadID());
// 設定關系
SetUnitRelation(tempEdge1);
SetUnitRelation(tempEdge2);
SetUnitRelation(tempEdge3);
// 判斷碰撞
// 設定不需要比較碰撞的ID(新加的邊以及幾個邊是不需要比較的)
noCompareIDs.Clear();
noCompareIDs.Add(tempEdge1.ID);
noCompareIDs.Add(tempEdge2.ID);
noCompareIDs.Add(tempEdge3.ID);
noCompareIDs.Add(Edges[(i + 1) % Edges.Count].ID);
// 遍歷新邊所在的所有標準單元
foreach (var unit in tempEdge2.Units)
// 遍歷每一個標準單元中的其他邊
foreach (var edge in unit.Edges)
// 如果發生碰撞，就記錄并跳出（不比較某些邊）
if (!noCompareIDs.Contains(edge.ID) && IsCollide(edge, tempEdge2))
{
isCollide = true;
// 跳出這個雙重回圈
goto outLoop;
}
noCompareIDs.Add(Edges[i].ID);
foreach (var unit in tempEdge1.Units)
// 遍歷每一個標準單元中的其他邊
foreach (var edge in unit.Edges)
// 如果發生碰撞，就記錄并跳出（不比較某些邊）
if (!noCompareIDs.Contains(edge.ID) && IsCollide(edge, tempEdge1))
{
isCollide = true;
// 跳出這個雙重回圈
goto outLoop;
}
noCompareIDs.Remove(Edges[i].ID);
noCompareIDs.Add(Edges[(i + 2) % Edges.Count].ID);
foreach (var unit in tempEdge3.Units)
// 遍歷每一個標準單元中的其他邊
foreach (var edge in unit.Edges)
// 如果發生碰撞，就記錄并跳出（不比較某些邊）
if (!noCompareIDs.Contains(edge.ID) && IsCollide(edge, tempEdge3))
{
isCollide = true;
// 跳出這個雙重回圈
goto outLoop;
}
outLoop:
// 如果沒有碰撞
if (!isCollide)
{
// 標記已執行
_executed = true;
// 添加新Node到結果中
AddToResultNode(tempNode1);
AddToResultNode(tempNode2);
// 添加新Road到結果中
AddToResultRoad(tempEdge1);
AddToResultRoad(tempEdge2);
AddToResultRoad(tempEdge3);
// 添加新Block到結果中
AddToResultBlock(Edges[(i + 1) % Edges.Count], tempEdge3, tempEdge2, tempEdge1);
// 清除掉無用邊界與其標準單元的關系
Edges[(i + 1) % Edges.Count].DeleteRelateUit();
// 添加新頂點到前沿中
var tempNodeList = new List<AftNode>()
{
tempNode1,
tempNode2
};
Nodes.InsertRange((i + 2) % Nodes.Count, tempNodeList);
// 添加新邊界到前沿中
var tempEdgeList = new List<AftEdge>()
{
tempEdge1,
tempEdge2,
tempEdge3
};
Edges.InsertRange((i + 1) % Edges.Count, tempEdgeList);
// 洗掉無用邊界
RemoveEdgesInList((i + 4) % Edges.Count, 1);
}
// 如果有碰撞
else
{
// 清除關系
tempEdge1.DeleteRelateUit();
tempEdge2.DeleteRelateUit();
tempEdge3.DeleteRelateUit();
// 移除ID
IdManager.RemoveNodeID(tempNode1.ID);
IdManager.RemoveNodeID(tempNode2.ID);
IdManager.RemoveRoadID(tempEdge1.ID);
IdManager.RemoveRoadID(tempEdge2.ID);
IdManager.RemoveRoadID(tempEdge3.ID);
}
}
// 檢測近距離頂點
else
{
// 判斷有沒有距離該節點很近的其他非鄰邊節點
noCompareIDs.Clear();
noCompareIDs.Add(Edges[i > 0 ? i - 1 : Edges.Count - 1].ID);
noCompareIDs.Add(Edges[i].ID);
noCompareIDs.Add(Edges[(i + 1) % Edges.Count].ID);
noCompareIDs.Add(Edges[(i + 2) % Edges.Count].ID);
// 找到一個最近的，并且位于左側的一個符合距離的頂點
var closestIndex = FindClosestNodeIndex((i + 1) % Nodes.Count, noCompareIDs,
Nodes[i].Coord,
Nodes[(i + 1) % Nodes.Count].Coord,
Nodes[(i + 2) % Nodes.Count].Coord);
// 如果找到
if (closestIndex >= 0)
{
// 標記已執行
_executed = true;
// TEST
//Debug.LogWarning("有橋邊" + Nodes[i].ID +" ," + Nodes[closestIndex].ID);
// 【注意】此ID由兩個方向的邊用，但實際是一條邊，任意一條邊加入結果即可
var brigeEdgeID = IdManager.GetRoadID();
// 創建橋邊
var brigeEdge = new AftEdge(Nodes[closestIndex], Nodes[(i + 1)%Nodes.Count], brigeEdgeID);
// 設定關系
SetUnitRelation(brigeEdge);
// TODO 這里也許需要加碰撞檢測，但是不加的話 好像也不會出現碰撞，但是沒有證明過
// 添加到結果中
AddToResultRoad(brigeEdge);
// 創建橋邊分割開來的另一半的頂點和邊
var newNodes = CopyRangeInNodes((i + 1) % Nodes.Count, closestIndex);
var newEdges = CopyRangeInEdges((i + 1) % Edges.Count, closestIndex > 0 ? closestIndex - 1 : Edges.Count - 1);
newEdges.Add(brigeEdge);
// 將新的邊界和頂點存到鏈表后，用于以后繼續生成，代替遞回
_edgesLinkedList.AddLast(newEdges);
_nodesLinkedList.AddLast(newNodes);
// 洗掉掉已經劃分的邊和頂點
// 計算需要刪掉幾個邊
var deleteEdgeCount = (Edges.Count + closestIndex - i - 1) % Edges.Count;
// 添加橋邊
Edges.Insert((i + 1) % Edges.Count, new AftEdge(Nodes[(i + 1) % Nodes.Count], Nodes[closestIndex], brigeEdgeID));
// 洗掉多余邊
RemoveEdgesInList((i + 2) % Edges.Count, deleteEdgeCount);
// 洗掉多余頂點
RemoveNodesInList((i + 2) % Nodes.Count, deleteEdgeCount - 1);
}
// TEST
// 當節點剩下的已經足夠少,直接組成Block
if (Nodes.Count < 6)
{
// 標記已執行
_executed = true;
// 添加街區
AddToResultBlock(Edges.ToArray());
// 清空
Nodes.Clear();
Edges.Clear();
// 標記結束
IsDone = true;
}
}
}
/// <summary>
/// 找到距離該點，最近的（下限以內）且是左側的點的坐標
/// </summary>
/// <param name="currentIndex">需要判斷的點</param>
/// <param name="noCompareIDs">不需要判斷的邊的ID</param>
/// <param name="p1">比較點前一個點坐標</param>
/// <param name="p2">比較點坐標</param>
/// <param name="p3">比較點下一個點坐標</param>
/// <returns></returns>
private int FindClosestNodeIndex(int currentIndex, ICollection<uint> noCompareIDs, Vector3 p1, Vector3 p2, Vector3 p3)
{
// 計算這個坐標位于的標準網格索引
int indexX = (int) Math.Floor((Nodes[currentIndex].Coord.x - StartCoordinate.x) / StandardUintLength),
indexY = (int) Math.Floor((Nodes[currentIndex].Coord.z - StartCoordinate.z) / StandardUintLength);
// 暫存最近距離
var tempDistance = StandardUintLength * 100;
AftNode tempNode = null;
// 遍歷附近包括自己所在的9個標準單元
for (var x = Math.Max(0, indexX - 1); x <= Math.Min(indexX + 1, StandardNet.GetLength(0) - 1); x++)
{
for (var y = Math.Max(0, indexY - 1); y <= Math.Min(indexY + 1, StandardNet.GetLength(1) - 1); y++)
{
// 遍歷每個單元內需要比較的邊
foreach (var edge in StandardNet[x, y].Edges)
{
// 去除不需要比較的情況
if (noCompareIDs.Contains(edge.ID)) continue;
var distance = Vector3.Distance(edge.Begin.Coord, Nodes[currentIndex].Coord);
// 判斷該線段上兩個端點有沒有足夠近的頂點
// TODO 1.35有待考究
if (distance < tempDistance && distance < WeightUnitLength(Nodes[currentIndex].Coord.x,Nodes[currentIndex].Coord.z) * 1.35f)
{
if (Vector3.SignedAngle(p2 - p1, p3 - p2, Vector3.up) > 0)
{
if (CrossVec2(edge.Begin.Coord - p1, p2 - p1) < 0 ||
CrossVec2(edge.Begin.Coord - p2, p3 - p2) < 0)
// 在左側
{
tempDistance = distance;
tempNode = edge.Begin;
}
}
else
{
if (CrossVec2(edge.Begin.Coord - p1, p2 - p1) < 0 &&
CrossVec2(edge.Begin.Coord - p2, p3 - p2) < 0) // 在左側
{
tempDistance = distance;
tempNode = edge.Begin;
}
}
}
distance = Vector3.Distance(edge.End.Coord, Nodes[currentIndex].Coord);
if (distance < tempDistance && distance < WeightUnitLength(Nodes[currentIndex].Coord.x,Nodes[currentIndex].Coord.z) * 1.35f)
{
if (Vector3.SignedAngle(p1 - p2, p2 - p3, Vector3.up) > 0)
{
if (CrossVec2(edge.End.Coord - p1, p2 - p1) < 0 ||
CrossVec2(edge.End.Coord - p2, p3 - p2) < 0) // 在左側
{
tempDistance = distance;
tempNode = edge.End;
}
}
else
{
if (CrossVec2(edge.End.Coord - p1, p2 - p1) < 0 &&
CrossVec2(edge.End.Coord - p2, p3 - p2) < 0) // 在左側
{
tempDistance = distance;
tempNode = edge.End;
}
}
}
}
}
}
if (tempNode != null) return Nodes.IndexOf(tempNode);
// 沒有找到
return -1;
}
/// <summary>
/// 便捷的移除AftNode中List的節點
/// </summary>
/// <param name="begin"></param>
/// <param name="count"></param>
private void RemoveNodesInList(int begin, int count)
{
// 如果需要跨越結尾進行洗掉
if (begin + count > Nodes.Count)
{
var frontCount = begin + count - Nodes.Count;
count = Nodes.Count - begin;
Nodes.RemoveRange(begin, count);
Nodes.RemoveRange(0, frontCount);
}
// 如果可以直接洗掉
else
{
Nodes.RemoveRange(begin, count);
}
}
/// <summary>
/// 便捷的移除AftEdge中List的節點
/// </summary>
/// <param name="begin"></param>
/// <param name="count"></param>
private void RemoveEdgesInList(int begin, int count)
{
// 如果需要跨越結尾進行洗掉
if (begin + count > Edges.Count)
{
var frontCount = begin + count - Edges.Count;
count = Edges.Count - begin;
Edges.RemoveRange(begin, count);
Edges.RemoveRange(0, frontCount);
}
// 如果可以直接洗掉
else
{
Edges.RemoveRange(begin, count);
}
}
/// <summary>
/// 從Node的List中復制一部分出來(可跨越)
/// </summary>
/// <param name="begin">開始索引</param>
/// <param name="end">結束索引</param>
/// <returns></returns>
private List<AftNode> CopyRangeInNodes(int begin, int end)
{
var res = new List<AftNode>();
// TODO 可優化
if (end > begin)
{
for (var i = begin; i <= end; i++)
res.Add(Nodes[i]);
}
else
{
for (var i = begin; i < Nodes.Count; i++)
res.Add(Nodes[i]);
for (var i = 0; i <= end; i++)
res.Add(Nodes[i]);
}
return res;
}
/// <summary>
/// 從Edges的List中復制一部分出來(可跨越)
/// </summary>
/// <param name="begin">開始索引</param>
/// <param name="end">結束索引</param>
/// <returns></returns>
private List<AftEdge> CopyRangeInEdges(int begin, int end)
{
var res = new List<AftEdge>();
// TODO 可優化
if (end > begin)
{
for (var i = begin; i <= end; i++)
res.Add(Edges[i]);
}
else
{
for (var i = begin; i < Nodes.Count; i++)
res.Add(Edges[i]);
for (var i = 0; i <= end; i++)
res.Add(Edges[i]);
}
return res;
}
/// <summary>
/// 快捷的構造一個街區并且添加到結果中去,逆時針順序
/// </summary>
/// <param name="edges"></param>
private void AddToResultBlock(params AftEdge[] edges)
{
// 判斷是否符合要求
if (edges.Length < 3)
{
Debug.LogWarning("傳入的邊界不足以構成街區");
return;
}
// 創建街區所需的道路List
var roads = new List<Road>();
foreach (var edge in edges)
{
roads.Add(ResultRoads[edge.ID]);
}
// 加入到結果中
var tempBlock = new Block(IdManager.GetBlockID(), roads);
ResultBlocks.Add(tempBlock.ID,tempBlock);
}
/// <summary>
/// 隨機一個小數
/// </summary>
/// <param name="begin"></param>
/// <param name="end"></param>
/// <returns></returns>
private static float RandomRange(float begin,float end)
{
return Mathf.Lerp(begin, end, (float) _random.NextDouble());
}
/// <summary>
/// 快捷的把該邊界加入到結果中
/// </summary>
/// <param name="road"></param>
private void AddToResultRoad(AftEdge road)
{
if (ResultRoads.ContainsKey(road.ID))
{
Debug.LogWarning("添加道路邊界時 出現重復ID：" + road.ID);
return;
}
ResultRoads.Add(road.ID,new Road(road.ID,ResultNodes[road.Begin.ID],ResultNodes[road.End.ID]));
}
/// <summary>
/// 快捷的把該節點加入到結果中
/// </summary>
/// <param name="node"></param>
private void AddToResultNode(AftNode node)
{
if (ResultNodes.ContainsKey(node.ID))
{
Debug.LogWarning("添加節點時 出現重復ID：" + node.ID);
return;
}
ResultNodes.Add(node.ID,new Node(node.ID,node.Coord));
}
/// <summary>
/// 設定邊界線段與單元格的關系
/// </summary>
/// <param name="edge">邊界線段</param>
private void SetUnitRelation(AftEdge edge)
{
// 計算線段兩個節點所在的單元格索引
int node1X = (int)Math.Floor((edge.Begin.Coord.x - StartCoordinate.x) / StandardUintLength),
node1Y = (int)Math.Floor((edge.Begin.Coord.z - StartCoordinate.z) / StandardUintLength);
int node2X = (int)Math.Floor((edge.End.Coord.x - StartCoordinate.x) / StandardUintLength),
node2Y = (int)Math.Floor((edge.End.Coord.z - StartCoordinate.z) / StandardUintLength);
// 讓1為小的值，2為大的值
if(node1X > node2X) Swap(ref node1X,ref node2X);
if(node1Y > node2Y) Swap(ref node1Y,ref node2Y);
// 找到需要檢測的單元格
for (var i = node1X; i <= node2X; i++)
{
for (var j = node1Y; j <= node2Y; j++)
{
// 檢測該單元格與線段是否碰撞
if (IsCollide(edge, RectOf(i,j)))
{
// 在邊界中加入單元
edge.Units.Add(StandardNet[i,j]);
// 在單元中加入邊界
StandardNet[i,j].Edges.Add(edge);
}
}
}
}
/// <summary>
/// 回傳該位置帶權重的單元長度
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
private float WeightUnitLength(float x, float y)
{
if (Mathf.Abs(x) < 12 && Mathf.Abs(y) < 12)
{
return StandardUintLength / 2;
}
return StandardUintLength;
}
/// <summary>
/// 判斷線段與矩形是否碰撞
/// </summary>
/// <param name="edge"></param>
/// <param name="rect"></param>
/// <returns></returns>
private static bool IsCollide(AftEdge edge, Vector3[] rect)
{
/*參考：https://blog.csdn.net/weixin_43807642/article/details/89243356
判斷兩個對角線與直線的交點是否在矩形內，
雖然這里是線段不是直線，但是經過前面的篩選后不會出現線段不碰撞而直線碰撞的矩形了，所以直接當成直線檢測即可*/
// k1 b1為線段的斜率和b，k2 b2為矩形對角線的斜率和b，交點xy
// 求線段的斜率和b
var k1 = (edge.End.Coord.z - edge.Begin.Coord.z) / (edge.End.Coord.x - edge.Begin.Coord.x);
var b1 = edge.Begin.Coord.z - k1 * edge.Begin.Coord.x;
// 求第一個對角線的斜率和b
var k2 = (rect[1].z - rect[0].z) / (rect[1].x - rect[0].x);
var b2 = rect[0].z - k2 * rect[0].x;
// 計算第一個交點
var x = (b1 - b2) / (k2 - k1);
var y = (b1 - b2) / (k2 - k1) * k1 + b1;
// 判斷第一個交點是否在矩形內，如果是直接回傳true
if (x > rect[0].x && x < rect[1].x && y > rect[0].z && y < rect[1].z)
return true;
// 求第二個對角線的斜率和b
// 交換一下求的另一個對角線
var temp = rect[0].z;
rect[0].z = rect[1].z;
rect[1].z = temp;
k2 = (rect[1].z - rect[0].z) / (rect[1].x - rect[0].x);
b2 = rect[0].z - k2 * rect[0].x;
// 計算第二個交點
x = (b1 - b2) / (k2 - k1);
y = (b1 - b2) / (k2 - k1) * k1 + b1;
// 判斷第二個交點是否在矩形內，如果是直接回傳true
return x >= rect[0].x && x <= rect[1].x && y >= rect[1].z && y <= rect[0].z;
}
/// <summary>
/// 判斷兩線段是否相交
/// </summary>
/// <param name="edge1"></param>
/// <param name="edge2"></param>
/// <returns></returns>
private static bool IsCollide(AftEdge edge1, AftEdge edge2)
{
/* 參考： https://blog.csdn.net/stevenkylelee/article/details/87934320
基于向量叉乘，判斷每個線段的兩端是否分別在另一個線段所劃分的空間的兩端，是則相交*/
// 定義四個點
var ap1 = new Vector2(edge1.Begin.Coord.x, edge1.Begin.Coord.z);
var ap2 = new Vector2(edge1.End.Coord.x, edge1.End.Coord.z);
var bp1 = new Vector2(edge2.Begin.Coord.x, edge2.Begin.Coord.z);
var bp2 = new Vector2(edge2.End.Coord.x, edge2.End.Coord.z);
// 判斷是否異號
if (CrossVec2(ap2 - ap1, bp1 - ap1) * CrossVec2(ap2 - ap1, bp2 - ap1) < 0 &&
CrossVec2(bp1 - bp2, ap1 - bp2) * CrossVec2(bp1 - bp2, ap2 - bp2) < 0)
return true;
return false;
}
/// <summary>
/// 二維向量叉乘
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
private static float CrossVec2(Vector2 a, Vector2 b)
{
return (a.x * b.y) - (b.x * a.y);
}
private static float CrossVec2(Vector3 a, Vector3 b)
{
return (a.x * b.z) - (b.x * a.z);
}
/// <summary>
/// 計算該頂點的角度
/// </summary>
/// <param name="n">頂點索引</param>
/// <returns>角度</returns>
private float AngleOf(int n)
{
// 計算該點的兩個向量
var vec1 = Nodes[n > 0 ? n - 1 : Nodes.Count - 1].Coord - Nodes[n].Coord;
var vec2 = Nodes[(n + 1) % Nodes.Count].Coord - Nodes[n].Coord;
// 計算角度
var angle = Vector3.SignedAngle(vec1, vec2, Vector3.up);
// 將負的角度改成正數
if (angle < 0) angle = 360 + angle;
return angle;
}
/// <summary>
/// 回傳對應單元格的矩形資料
/// </summary>
/// <param name="x">索引x</param>
/// <param name="y">索引y</param>
/// <returns>矩形資料（2維，只有對角的坐標）</returns>
private Vector3[] RectOf(int x, int y)
{
var res = new Vector3[2];
res[0].x = StartCoordinate.x + x * StandardUintLength;
res[0].z = StartCoordinate.z + y * StandardUintLength;
res[1].x = res[0].x + StandardUintLength;
res[1].z = res[0].z + StandardUintLength;
return res;
}
/// <summary>
/// 交換
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <typeparam name="T"></typeparam>
private static void Swap<T>(ref T a, ref T b)
{
var temp = a;
a = b;
b = temp;
}
/// <summary>
/// 查找多邊形的最邊界的頂點的坐標
/// </summary>
/// <param name="coords">頂點List</param>
/// <param name="minX">x方向上最小的頂點的坐標</param>
/// <param name="maxX">x方向上最大的頂點的坐標</param>
/// <param name="minZ">z方向上最小的頂點的坐標</param>
/// <param name="maxZ">z方向上最大的頂點的坐標</param>
private static void FindEdgePoints(IReadOnlyList<AftNode> coords, out float minX, out float maxX, out float minZ, out float maxZ)
{
// 遍歷一遍找到對應的索引
int minXIndex = 0, maxXIndex = 0, minZIndex = 0, maxZIndex = 0;
for (var i = 1; i < coords.Count; i++)
{
if (coords[i].Coord.x < coords[minXIndex].Coord.x)
minXIndex = i;
if (coords[i].Coord.x > coords[maxXIndex].Coord.x)
maxXIndex = i;
if (coords[i].Coord.z < coords[minZIndex].Coord.z)
minZIndex = i;
if (coords[i].Coord.z > coords[maxZIndex].Coord.z)
maxZIndex = i;
}
// 賦值
minX = coords[minXIndex].Coord.x;
maxX = coords[maxXIndex].Coord.x;
minZ = coords[minZIndex].Coord.z;
maxZ = coords[maxZIndex].Coord.z;
}
}
/// <summary>
/// 標準單元
/// </summary>
public class StandardUnit
{
// 標準單元內包含的邊界
public List<AftEdge> Edges = new List<AftEdge>();
// TEST 可視化的時候需要知道單元格的坐標，但實際上演算法中不需要坐標
public int X, Y;
}
/// <summary>
/// 節點
/// </summary>
public class AftNode
{
// ID
public readonly uint ID;
// 位置
public Vector3 Coord { get; }
// 該點內角角度
public float Angle;
/// <summary>
/// 建構式
/// </summary>
/// <param name="coord">該點的坐標</param>
/// <param name="id">ID</param>
public AftNode(Vector3 coord,uint id)
{
Coord = coord;
ID = id;
}
}
/// <summary>
/// 邊界線段
/// </summary>
public class AftEdge
{
// ID
public readonly uint ID;
// 開始的節點
public AftNode Begin { get; }
// 結束的節點
public AftNode End { get; }
// 所在的標準單元
public readonly List<StandardUnit> Units = new List<StandardUnit>();
/// <summary>
/// 建構式
/// </summary>
/// <param name="begin">開始節點</param>
/// <param name="end">結束節點</param>
/// <param name="id">ID</param>
public AftEdge(AftNode begin, AftNode end,uint id)
{
this.Begin = begin;
this.End = end;
ID = id;
}
/// <summary>
/// 解除與該邊界相關的標準單元格的關系
/// </summary>
public void DeleteRelateUit()
{
foreach (var unit in Units)
unit.Edges.Remove(this);
Units.Clear();
}
}
}
4.3. 可視化
using System;
using System.Collections.Generic;
using UnityEngine;
using RoadNetwork;
using System.Threading;
namespace Test
{
public class TestAFT : MonoBehaviour
{
public List<Transform> polygon = new List<Transform>();
public float unitLength = 1.5f;
public float nodeShpereSize = 0.2f;
public int randomSeed = 0;
public enum ShowType
{
Input,
Front,
Result,
FrontAndResult
}
public enum LableType
{
NodeAndRoad,
Node,
Road
}
public LableType idType;
public int genType;
public ShowType showType;
private List<Vector3> polygonCoords = new List<Vector3>();
public AdvancingFrontTechnique _boundary;
// TEST 可視化選擇邊界用到
[Range(1,100)]
public int edgeIndex = 1;
public void Creat()
{
// 獲取多邊形頂點位置
polygonCoords.Clear();
foreach (var point in polygon)
polygonCoords.Add(point.position);
Generate();
}
public void GenAndGen()
{
Generate();
_boundary.GenOnce();
Debug.Log("Done");
Debug.Log(AdvancingFrontTechnique.ResultNodes.Count);
}
private void OnDrawGizmos()
{
// 畫出標準網格
if (_boundary != null)
{
// 顯示起始點
Gizmos.color = Color.red;
Gizmos.DrawSphere(_boundary.StartCoordinate,0.4f);
// 顯示標磚網格
Gizmos.color = Color.gray;
for (int i = 0; i < AdvancingFrontTechnique.StandardNet.GetLength(0); i++)
{
for (int j = 0; j < AdvancingFrontTechnique.StandardNet.GetLength(1); j++)
{
Vector3 p1 = _boundary.StartCoordinate, p2 = _boundary.StartCoordinate;
p1.x += i * _boundary.StandardUintLength;
p1.z += j * _boundary.StandardUintLength;
p2.x = p1.x + _boundary.StandardUintLength;
p2.z = p1.z + _boundary.StandardUintLength;
DrawRect(p1,p2);
}
}
}
switch (showType)
{
case ShowType.Input:
// 畫出所構建的多邊形
if (polygon.Count > 0)
{
Gizmos.color = Color.blue;
for (var i = 0; i < polygon.Count; i++)
{
Gizmos.DrawLine(polygon[i].position, polygon[(i + 1) % polygon.Count].position);
}
}
break;
case ShowType.Front:
if (_boundary != null)
{
// 顯示離散之后的各個頂點
Gizmos.color = Color.magenta;
foreach (var node in _boundary.Nodes)
Gizmos.DrawSphere(node.Coord,nodeShpereSize);
// 顯示前沿
Gizmos.color = Color.blue;
foreach (var edge in _boundary.Edges)
{
Gizmos.DrawLine(edge.Begin.Coord, edge.End.Coord);
}
// 顯示一個邊以及對應的單元格
// 線條
Gizmos.color = Color.green;
edgeIndex %= _boundary.Edges.Count;
Gizmos.DrawLine(_boundary.Edges[edgeIndex].Begin.Coord,_boundary.Edges[edgeIndex].End.Coord);
// 單元格
Gizmos.color = Color.yellow;
foreach (var unit in _boundary.Edges[edgeIndex].Units)
{
Vector3 p1 = _boundary.StartCoordinate, p2 = _boundary.StartCoordinate;
p1.x += unit.X * _boundary.StandardUintLength;
p1.z += unit.Y * _boundary.StandardUintLength;
p2.x = p1.x + _boundary.StandardUintLength;
p2.z = p1.z + _boundary.StandardUintLength;
DrawRect(p1,p2);
}
}
break;
case ShowType.Result:
if (_boundary != null && _boundary.IsDone)
{
// 繪制結果頂點
Gizmos.color = Color.magenta;
foreach (var node in AdvancingFrontTechnique.ResultNodes)
Gizmos.DrawSphere(node.Value.Coord,nodeShpereSize);
// 繪制結果邊界
Gizmos.color = Color.green;
foreach (var road in AdvancingFrontTechnique.ResultRoads)
{
Gizmos.DrawLine(road.Value.Begin.Coord,road.Value.End.Coord);
}
}
break;
case ShowType.FrontAndResult:
if (_boundary != null)
{
// 繪制結果邊界
Gizmos.color = Color.green;
foreach (var road in AdvancingFrontTechnique.ResultRoads)
{
Gizmos.DrawLine(road.Value.Begin.Coord,road.Value.End.Coord);
}
// 顯示前沿
Gizmos.color = Color.blue;
foreach (var edge in _boundary.Edges)
{
Gizmos.DrawLine(edge.Begin.Coord, edge.End.Coord);
}
// 繪制結果頂點
Gizmos.color = Color.white;
foreach (var node in AdvancingFrontTechnique.ResultNodes)
Gizmos.DrawSphere(node.Value.Coord,nodeShpereSize);
// 顯示離散之后的各個頂點
Gizmos.color = Color.red;
foreach (var node in _boundary.Nodes)
Gizmos.DrawSphere(node.Coord,nodeShpereSize);
}
break;
}
}
// 畫四邊形
private void DrawRect(Vector3 p1, Vector3 p3)
{
Vector3 p2 = new Vector3(p1.x,0,p3.z), p4 = new Vector3(p3.x,0,p1.z);
Gizmos.DrawLine(p1,p2);
Gizmos.DrawLine(p2,p3);
Gizmos.DrawLine(p3,p4);
Gizmos.DrawLine(p4,p1);
}
public void Generate()
{
// 初始化IDManager
IdManager.Initialization();
_boundary = new AdvancingFrontTechnique(polygonCoords, unitLength, randomSeed);
}
// TEST 測驗用的函式
private Thread _thread;
public void TEST()
{
// 獲取多邊形頂點位置
polygonCoords.Clear();
foreach (var point in polygon)
polygonCoords.Add(point.position);
_thread = new Thread(new ThreadStart(GenAndGen));
_thread.Start();
}
public void StopThread()
{
_thread.Abort();
}
private static float CrossVec2(Vector3 a, Vector3 b)
{
return (a.x * b.z) - (b.x * a.z);
}
}
}
using System.Collections.Generic;
using RoadNetwork;
using UnityEditor;
using UnityEngine;
namespace Test.Editor
{
[CustomEditor(typeof(TestAFT))]
public class TestAftEditor : UnityEditor.Editor
{
private bool showLable;
public override void OnInspectorGUI()
{
base.OnInspectorGUI();
showLable = GUILayout.Toggle(showLable, "ShowLable");
TestAFT script = target as TestAFT;
if (GUILayout.Button("生成"))
{
script.Creat();
SceneView.RepaintAll();
}
if (script._boundary!=null && GUILayout.Button("生成一次網格"))
{
script._boundary.GenOnce();
Debug.Log(AdvancingFrontTechnique.ResultBlocks.Count);
SceneView.RepaintAll();
}
if (GUILayout.Button("TEST"))
{
script.TEST();
}
if (GUILayout.Button("STOP"))
{
script.StopThread();
}
}
private void OnSceneGUI()
{
TestAFT script = target as TestAFT;
if (showLable && script._boundary != null)
{
switch (script.showType)
{
case TestAFT.ShowType.Front:
// TEST 可視化角度 (更新過前沿之后這個角度就不對了，因為每次用角度都是重新計算的，并沒有更新這個角度)
foreach (var node in script._boundary.Nodes)
Handles.Label(node.Coord,"Node: " + node.ID.ToString());
foreach (var road in script._boundary.Edges)
Handles.Label(Vector3.Lerp(road.Begin.Coord,road.End.Coord,0.5f),"Road: "+road.ID.ToString());
break;
case TestAFT.ShowType.Result:
// 可視化ID
Handles.color = Color.white;
foreach (var node in AdvancingFrontTechnique.ResultNodes)
Handles.Label(node.Value.Coord,"Node: " + node.Value.ID.ToString());
Handles.color = Color.black;
foreach (var road in AdvancingFrontTechnique.ResultRoads)
Handles.Label(Vector3.Lerp(road.Value.Begin.Coord,road.Value.End.Coord,0.5f),"Road: "+road.Value.ID.ToString());
break;
case TestAFT.ShowType.FrontAndResult:
// 可視化ID
Handles.color = Color.white;
if(script.idType == TestAFT.LableType.NodeAndRoad || script.idType == TestAFT.LableType.Node)
foreach (var node in AdvancingFrontTechnique.ResultNodes)
Handles.Label(node.Value.Coord,"Node: " + node.Value.ID.ToString());
Handles.color = Color.black;
if(script.idType == TestAFT.LableType.NodeAndRoad || script.idType == TestAFT.LableType.Road)
foreach (var road in AdvancingFrontTechnique.ResultRoads)
Handles.Label(Vector3.Lerp(road.Value.Begin.Coord,road.Value.End.Coord,0.5f),"Road: "+road.Value.ID.ToString());
break;
}
}
}
private void TestLinkedList()
{
var linkedList = new LinkedList<MyClass>();
linkedList.AddLast(new MyClass("1",1));
linkedList.AddLast(new MyClass("2",2));
linkedList.AddLast(new MyClass("3",3));
linkedList.AddLast(new MyClass("4",4));
linkedList.AddLast(new MyClass("5",5));
linkedList.AddLast(new MyClass("6",6));
linkedList.AddLast(new MyClass("7",7));
linkedList.AddLast(new MyClass("8",8));
MyClass temp = linkedList.First.Value;
temp.str = "liu";
ShowLinked(linkedList);
}
private void RemoveRange(ref LinkedList<MyClass> link, LinkedList<MyClass>.Enumerator begin, LinkedList<MyClass>.Enumerator end)
{
var i = begin;
link.Remove(i.Current);
}
private void ShowLinked(LinkedList<MyClass> targetList)
{
foreach (var node in targetList)
{
Debug.Log(node);
}
}
public class MyClass
{
public string str;
public int inter;
public MyClass(string str, int inter)
{
this.inter = inter;
this.str = str;
}
public override string ToString()
{
return str;
}
}
}
}
王元,煉訓,李航.基于有限元網格劃分的城市道路網建模[J].圖學學報,2016,37(03):377-385. ??
李任君. 關于四邊形有限元網格生成演算法的研究[D].吉林大學,2008. ??
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/256861.html
標籤：區塊鏈