程序丨如何实现类似《钢铁雄心》的可点击地图（二）？
系列回顾：
上回有提到单纯使用边界点与多边形关系判断是无法确定凹凸性的，但代码又舍不得删，怎么办呢？
其实在上一篇的代码也有写到。
取i-1到i+1线段中的一些点，只要这些点不在多边形内部，那点i为凹点
for (int k = 1; k < 10; k++)
｛
if (GeometryHelper.IntersectionOf(new PointF(polygon[j].X + k * pointF.X, polygon[j].Y + k * pointF.Y), new Line(polygon[j - 1], polygon[j + 1])) != GeometryHelper.Intersection.None) ｛
isIn = true;
break;
｝
｝
或者直接利用线段与多边形关系？不过这个线段需要将首尾两端截去一部分？
PointF point = new PointF(polygon[j + 1].X - polygon[j - 1].X, polygon[j + 1].Y - polygon[j - 1].Y);
Line line = new Line(new PointF(polygon[j - 1].X + point.X / 10, polygon[j - 1].Y + point.Y / 10), new PointF(polygon[j + 1].X - point.X / 10, polygon[j + 1].Y - point.Y / 10));
这两个方案都不太好，因为他们无法处理w形的图像
正常情况下，多边形凹凸性判定是不会出现这种现象的，但现在所获取的边界点真的是“正常”的多边形吗？答案是否定的，当然，这不是现在要讨论的问题。
然而答案却是无解的，毕竟由这些边界点所组成的多边形真的就是那样的。
虽然很无法解决这个问题，但我还是决定换一个判定多边形凹凸性的方案，因为这个算法效率真的很低很低。
一．多边形凹凸性的判断
写这个项目，走了很多弯路，但转了很多圈后还是走上了正轨，因为我发现了这篇文章，判断平面多边形的凹凸性。
使用角度判断的方案不考虑，直接上矢量判断。
原代码解决方案
大于小于号分不清这种槽我就不吐了（好像已经吐了），毕竟这应该是c或c艹的代码，无法直接在unity中使用，下面是修改后的C#代码
private List<Vector2> GetHollowPointList(List<Vector2> curveloopPoints)
｛
//假设传进来的顶点数组都是按照顺时针或者逆时针遍历的，且没有重复点
//使用法向量判断凹凸性，检测多边形上是否有凸点，每个顶点的转向都应该一致，若不一致则为凹点
List<Vector2> HollowPoints = new List<Vector2>();
int num = curveloopPoints.Count;
float HollowNor = Vector2.Cross((curveloopPoints[num - 1] - curveloopPoints[0]) , (curveloopPoints[1] - curveloopPoints[0]));
float Nor;
for (int i = 0; i < num; i++)
｛
if (i == 0)//第一个点
｛
Nor = Vector3.Cross((curveloopPoints[0] - curveloopPoints[num - 1]), (curveloopPoints[1] - curveloopPoints[0]));
if (Vector3.Dot(Nor, HollowNor) < 0.0f)
｛
HollowPoints.Add(curveloopPoints[i]);
｝
｝
else if (i == num - 1)//最后一个点
｛
Nor = Vector3.Cross((curveloopPoints[i] - curveloopPoints[i - 1]), (curveloopPoints[0] - curveloopPoints[i]));
if (Vector3.Dot(Nor, HollowNor) < 0.0f)
｛
HollowPoints.Add(curveloopPoints[i]);
｝
｝
else//中间点
｛
Nor = Vector3.Cross((curveloopPoints[i] - curveloopPoints[i - 1]), (curveloopPoints[i + 1] - curveloopPoints[i]));
if (Vector3.Dot(Nor, HollowNor) < 0.0f)
｛
HollowPoints.Add(curveloopPoints[i]);
｝
｝
｝
return HollowPoints;
｝
利用向量的叉乘求得向量的法向量，再利用法向量和点乘的正负形判断角度转向是否一致，不一致则为凹点。
想详细了解的请直接看《3D数学基础图形与游戏开发》一书，这里就不展开了。
二．求凹点凸点的真正方式
没错，上面的代码无法确定多边形的一个顶点一定是凸点或是凹点，因为他使用的“标准”法向量是n-1到0和1到0两个向量的法向量，假如初始点是凹点，那么所返回的所有点将是凸点，如果只是用来判断整个多边形的凹凸性完全没有问题，甚至对于某一个特定的多边形来说，即使出错，也可以通过取反这种操作来得到正确的结果，但本项目完全无法使用这样的“骚操作”，因为使用割耳法每次都会从多边形中割掉一个点，原来的凹点很有可能在下一次计算时变成凸点，我们需要一个稳定的算法代来解决这个问题。
幸好《3D数学基础图形与游戏开发》一书给出了解决方案，那就是计算整个多边形的标准法向量。
private Vector3 ComputeBestFitNormal(List<Vector3> pointList,int num)
｛
//和置零
Vector3 reslut = Vector3.zero;
//从最后一个点开始，避免循环中进行if判断
Vector3 p = pointList[num - 1];
for(int i = 0; i < num; i++)
｛
Vector3 c = pointList[i];
reslut.x += (p.z + c.z) * (p.y - c.y);
reslut.y += (p.x + c.x) * (p.z - c.z);
reslut.z += (p.y + c.y) * (p.x - c.x);
p = c;
｝
reslut.Normalize();
return reslut;
｝
所以遇到算法类问题时最好以书为标准，博客这东西质量真的不稳定，心累。
三．删除坏点
上文有提到，现在获取的边界点并非我们想要的边界点，它有很多坏点来干扰多边形的三角化，问题就出在获取边界点的算法上。
现在的算法就是把区域填充算法的广搜变成了深搜，在本应该结束搜索时却并没有结束，因为有些点的确是边界点，虽然我们并不想要它。
效果三连，注意找不同
有这么多点捣乱，三角化能正常才怪
那怎么控制搜索在合适的时候结束呢？很简单，对比当前点和初始点的距离。
bool HaveMore(Vector2 from,Vector2 to)
｛
if (Vector2.Distance(from, to) > 1)
return true;
else
return false;
｝
if (GenerateMap.GetGenerateMap.borderPointList.Count > 10 && !HaveMore(GenerateMap.GetGenerateMap.borderPointList[0], GenerateMap.GetGenerateMap.borderPointList[i]))
return false;
但增加了这段代码还是有问题
Debug后发现，还是边界点的问题。
由于边界点是以顺时针的顺序添加的，于是就出现了这种折返现象，当然，这些点都不是我们所需要的，将添加顺序略作修改，先上下左右，然后对角线。
bool AddMorePoint()
｛
int x, y;
for (int i = GenerateMap.GetGenerateMap.borderPointList.Count - 1; i > -1; i--)
｛
if (GenerateMap.GetGenerateMap.borderPointList.Count > 10 && !HaveMore(GenerateMap.GetGenerateMap.borderPointList[0], GenerateMap.GetGenerateMap.borderPointList[i]))
return false;
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x - 1;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y + 1;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x + 1;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y - 1;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x - 1;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y + 1;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x + 1;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y + 1;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x + 1;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y - 1;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
x = (int)GenerateMap.GetGenerateMap.borderPointList[i].x - 1;
y = (int)GenerateMap.GetGenerateMap.borderPointList[i].y - 1;
if (IsBorderPoint(x, y))
｛
GenerateMap.GetGenerateMap.borderPointList.Add(new Vector2(x, y));
SetPixel(x, y);
return true;
｝
｝
return false;
｝
问题仍然没有完美解决，于是决定尝试将多余的点（死点）删除
private bool IsDeathPoint(int x, int y)
｛
Color color;
color = GenerateMap.GetGenerateMap.map.GetPixel(x - 1, y);
if (color == GenerateMap.GetGenerateMap.mapColor)
return false;
color = GenerateMap.GetGenerateMap.map.GetPixel(x, y + 1);
if (color == GenerateMap.GetGenerateMap.mapColor)
return false;
color = GenerateMap.GetGenerateMap.map.GetPixel(x + 1, y);
if (color == GenerateMap.GetGenerateMap.mapColor)
return false;
color = GenerateMap.GetGenerateMap.map.GetPixel(x, y - 1);
if (color == GenerateMap.GetGenerateMap.mapColor)
return false;
return true;
｝
for (int i = 1; i < GenerateMap.GetGenerateMap.borderPointList.Count - 1; i++)
｛
if (IsDeathPoint((int)GenerateMap.GetGenerateMap.borderPointList[i].x, (int)GenerateMap.GetGenerateMap.borderPointList[i].y))
｛
GenerateMap.GetGenerateMap.borderPointList.Remove(GenerateMap.GetGenerateMap.borderPointList[i]);
i--;
｝
｝
瞬间效果出来了有没有？
然而好像哪里有些不对？
正反面不是问题，但好像三角化仍然有些不对？
将不同被删除的点用不同颜色标出，发现。。。删多了
由于删除点后未及时更新图，删除了一些非“死点”
所以调整一下删除点的顺序，先删死点，再删多余点。
最后得到
效果非常“棒”有没有？
四．割耳法的边界处理
然而卡住了，QAQ
Debug发现剩余4个点中有2个点为凹点
我能怎么办，我也很绝望。Jpg
但bug还是要调的，仔细分析代码后发现，2个凸点分别位于列表的0号位和n-1号位，所以问题是由边界处理未做好导致的。
修改后的代码
public IEnumerator MakeCityMesh()
｛
List<Vector3> m_vertices = new List<Vector3>();
List<int> m_triangles = new List<int>();
m_vertices.Clear();
m_triangles.Clear();
GameObject go = GameObject.Instantiate(BaseMeshObject, GenerateMap.GetGenerateMap.transform);
Mesh mesh = go.GetComponent<MeshFilter>().mesh;
List<Vector3> polygon = new List<Vector3>();
List<Vector3> hollowPointList;
foreach (Vector2 vec in GenerateMap.GetGenerateMap.borderPointList)
｛
if (!polygon.Contains(new Vector3(vec.x, vec.y, 0)))
｛
polygon.Add(new Vector3(vec.x, vec.y, 0));
m_vertices.Add(new Vector3(vec.x, vec.y, 0));
｝
｝
while (polygon.Count > 2)
｛
hollowPointList = GetHollowPointList(polygon);
for (int j = 0; j < polygon.Count; j++)
｛
if (!hollowPointList.Contains(polygon[j]) && polygon.Count > 2)
｛
Vector3 fVec;
Vector3 nVec;
Vector3 lVec;
if (j > 0 && j < polygon.Count - 1)
｛
fVec = new Vector3(polygon[j - 1].x, polygon[j - 1].y, 0);
nVec = new Vector3(polygon[j].x, polygon[j].y, 0);
lVec = new Vector3(polygon[j + 1].x, polygon[j + 1].y, 0);
｝
else
if (j == 0)
｛
fVec = new Vector3(polygon[polygon.Count - 1].x, polygon[polygon.Count - 1].y, 0);
nVec = new Vector3(polygon[j].x, polygon[j].y, 0);
lVec = new Vector3(polygon[j + 1].x, polygon[j + 1].y, 0);
｝
else
｛
fVec = new Vector3(polygon[j - 1].x, polygon[j - 1].y, 0);
nVec = new Vector3(polygon[j].x, polygon[j].y, 0);
lVec = new Vector3(polygon[0].x, polygon[0].y, 0);
｝
for (int i = 0; i < m_vertices.Count; i++)
if (Vector3.Equals(fVec, m_vertices[i]))
｛
m_triangles.Add(i);
break;
｝
for (int i = 0; i < m_vertices.Count; i++)
if (Vector3.Equals(nVec, m_vertices[i]))
｛
m_triangles.Add(i);
break;
｝
for (int i = 0; i < m_vertices.Count; i++)
if (Vector3.Equals(lVec, m_vertices[i]))
｛
m_triangles.Add(i);
break;
｝
polygon.Remove(polygon[j]);
j--;
｝
｝
hollowPointList.Clear();
mesh.Clear();
mesh.vertices = m_vertices.ToArray();
mesh.triangles = m_triangles.ToArray();
mesh.RecalculateNormals();
yield return new WaitForSeconds(0.1f);
｝
GenerateMap.GetGenerateMap.isDrawMeshOver = true;
｝
非常“完美”，全国蓝化
总感觉这句话好像哪里有些不对？
五．一些其他问题
刚才那张图正面，背面其实是这样的
蓝廋，香菇
这个问题就留到下回再解决吧
其实是我还没有解决，所以，如果有思路，烦请告知！！！
向量判断顶点凹凸性
删除“死”点
“完成”地图mesh的绘制
上面是不同时期项目，想看效果的可以点击阅读原文前往下载。
----------------------
今日推荐
添加小编微信，可享双重福利
1.加入GAD程序猿交流基地
获取行业干货资讯，观看大牛分享直播
2.领取60G独家程序资料，地址在小编朋友圈
包括腾讯内部分享、文章教程、视频教程等全套资料
↓长按添加小编GAD苏苏↓