|
? ? ? ? 日常项目中我们所能拿到的GIS数据都是shp或者Genjson类型数据文件，之前的处理方式基本都是经过一些ArcGIS及建模软件的处理导出成模型，再放在Unity中产出项目。
? ? ? ? 后来经过研究，实现了基于三角剖分算法完成Gis数据实时构建城市建筑水系功能。
????????首先定义计算过程中需要的实体类，起始就是类似于Unity中的Vector3 和Vector2，至于为什么要自己定义，你在计算时自己去查下性能分析就知道了；
二维坐标 V2.cs
public class V2
{
public double x;
public double y;
public V2(double _x, double _y)
{
this.x = _x;
this.y = _y;
}
}
三维坐标? V3.cs
public class V3
{
public double x;
public double y;
public double z;
public V3(double _x, double _y, double _z)
{
this.x = _x;
this.y = _y;
this.z = _z;
}
}
三角面实体类?Triangle.cs
/// <summary>
/// 三角面 实体类
/// </summary>
struct Triangle
{
public int p1;
public int p2;
public int p3;
public Triangle(int point1, int point2, int point3)
{
p1 = point1;
p2 = point2;
p3 = point3;
}
}
边实体类
/// <summary>
/// 边 实体类
/// </summary>
class Edge
{
public int p1;
public int p2;
public Edge(int point1, int point2)
{
p1 = point1;
p2 = point2;
}
public Edge() : this(0, 0) { }
public bool Equals(Edge other)
{
return ((this.p1 == other.p2) && (this.p2 == other.p1)) || ((this.p1 == other.p1) && (this.p2 == other.p2));
}
}
三角剖分核心算法类?Triangulator.cs
/// <summary>
/// 三角面生成核心类 (三角剖分)
/// </summary>
public class Triangulator
{
/// <summary>
/// 科学精度误差值
/// </summary>
public const double Epsilon = 1e-7;
/// <summary>
/// 浮点类型 比较 小于
/// </summary>
/// <param name="value"></param>
/// <param name="other"></param>
/// <returns></returns>
public static bool FloatLess(float value, float other)
{
return Mathf.Abs(other - value) > Epsilon;
}
/// <summary>
/// 浮点类型 比较 大于
/// </summary>
/// <param name="value"></param>
/// <param name="other"></param>
/// <returns></returns>
static bool FloatGreat(float value, float other)
{
return Mathf.Abs(value - other) > Epsilon;
}
/// <summary>
/// 浮点类型 比较 等于
/// </summary>
/// <param name="value"></param>
/// <param name="other"></param>
/// <returns></returns>
public static bool FloatEqual(float value, float other)
{
return Mathf.Abs(value - other) <= Epsilon;
}
/// <summary>
/// double类型 比较 等于
/// </summary>
/// <param name="value"></param>
/// <param name="other"></param>
/// <returns></returns>
public static bool FloatEqual(double value, double other)
{
return Abs(value - other) <= Epsilon;
}
static double Abs(double value)
{
return value >= 0 ? value : -value;
}
/// <summary>
/// Vector3类型 比较 等于
/// </summary>
/// <param name="value"></param>
/// <param name="other"></param>
/// <returns></returns>
static bool Vector3Equal(Vector3 a, Vector3 b)
{
return FloatEqual(a.x, b.x) && FloatEqual(a.y, b.y) && FloatEqual(a.z, b.z);
}
/// <summary>
/// Vector2类型 比较 等于
/// </summary>
/// <param name="value"></param>
/// <param name="other"></param>
/// <returns></returns>
static bool Vector2Equal(Vector2 a, Vector2 b)
{
return FloatEqual(a.x, b.x) && FloatEqual(a.y, b.y);
}
static bool TriangulatePolygonSubFunc_InCircle(Vector2 p, Vector2 p1, Vector2 p2, Vector2 p3)
{
if (FloatEqual(p1.y, p2.y) && FloatEqual(p2.y, p3.y))
{
return false;
}
float m1, m2, mx1, mx2, my1, my2, xc, yc;
if (FloatEqual(p2.y, p1.y))
{
m2 = -(p3.x - p2.x) / (p3.y - p2.y);
mx2 = (p2.x + p3.x) * 0.5f;
my2 = (p2.y + p3.y) * 0.5f;
xc = (p2.x + p1.x) * 0.5f;
yc = m2 * (xc - mx2) + my2;
}
else if (FloatEqual(p3.y,p2.y))
{
m1 = -(p2.x - p1.x) / (p2.y - p1.y);
mx1 = (p1.x + p2.x) * 0.5f;
my1 = (p1.y + p2.y) * 0.5f;
xc = (p3.x + p2.x) * 0.5f;
yc = m1 * (xc - mx1) + my1;
}
else
{
m1 = -(p2.x - p1.x) / (p2.y - p1.y);
m2 = -(p3.x - p2.x) / (p3.y - p2.y);
mx1 = (p1.x + p2.x) * 0.5f;
mx2 = (p2.x + p3.x) * 0.5f;
my1 = (p1.y + p2.y) * 0.5f;
my2 = (p2.y + p3.y) * 0.5f;
xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
yc = m1 * (xc - mx1) + my1;
}
float dx = p2.x - xc;
float dy = p2.y - yc;
float rsqr = dx * dx + dy * dy;
dx = p.x - xc;
dy = p.y - yc;
double drsqr = dx * dx + dy * dy;
return (drsqr <= rsqr);
}
static bool TriangulatePolygonSubFunc_InCircle(V2 p, V2 p1, V2 p2, V2 p3)
{
if (FloatEqual(p1.y, p2.y) && FloatEqual(p2.y, p3.y))
{
return false;
}
double m1, m2, mx1, mx2, my1, my2, xc, yc;
if (FloatEqual(p2.y, p1.y))
{
m2 = -(p3.x - p2.x) / (p3.y - p2.y);
mx2 = (p2.x + p3.x) * 0.5f;
my2 = (p2.y + p3.y) * 0.5f;
xc = (p2.x + p1.x) * 0.5f;
yc = m2 * (xc - mx2) + my2;
}
else if (FloatEqual(p3.y, p2.y))
{
m1 = -(p2.x - p1.x) / (p2.y - p1.y);
mx1 = (p1.x + p2.x) * 0.5f;
my1 = (p1.y + p2.y) * 0.5f;
xc = (p3.x + p2.x) * 0.5f;
yc = m1 * (xc - mx1) + my1;
}
else
{
m1 = -(p2.x - p1.x) / (p2.y - p1.y);
m2 = -(p3.x - p2.x) / (p3.y - p2.y);
mx1 = (p1.x + p2.x) * 0.5f;
mx2 = (p2.x + p3.x) * 0.5f;
my1 = (p1.y + p2.y) * 0.5f;
my2 = (p2.y + p3.y) * 0.5f;
xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
yc = m1 * (xc - mx1) + my1;
}
double dx = p2.x - xc;
double dy = p2.y - yc;
double rsqr = dx * dx + dy * dy;
dx = p.x - xc;
dy = p.y - yc;
double drsqr = dx * dx + dy * dy;
return (drsqr <= rsqr);
}
/// <summary>
/// 凸面多边形三角剖分 布线更优
/// </summary>
/// <param name="XZofVertices"></param>
/// <returns></returns>
public static int[] TriangulateConvexPolygon(V2[] XZofVertices)
{
int VertexCount = XZofVertices.Length;
double xmin = XZofVertices[0].x;
double ymin = XZofVertices[0].y;
double xmax = xmin;
double ymax = ymin;
for (int ii1 = 1; ii1 < VertexCount; ii1++)
{
if (XZofVertices[ii1].x < xmin) { xmin = XZofVertices[ii1].x; }
else if (XZofVertices[ii1].x > xmax) { xmax = XZofVertices[ii1].x; }
if (XZofVertices[ii1].y < ymin) { ymin = XZofVertices[ii1].y; }
else if (XZofVertices[ii1].y > ymax) { ymax = XZofVertices[ii1].y; }
}
double dx = xmax - xmin;
double dy = ymax - ymin;
double dmax = (dx > dy) ? dx : dy;
double xmid = (xmax + xmin) * 0.5f;
double ymid = (ymax + ymin) * 0.5f;
V2[] ExpandedXZ = new V2[3 + VertexCount];
for (int ii1 = 0; ii1 < VertexCount; ii1++)
{
ExpandedXZ[ii1] = XZofVertices[ii1];
}
ExpandedXZ[VertexCount] = new V2((xmid - 2 * dmax), (ymid - dmax));
ExpandedXZ[VertexCount + 1] = new V2(xmid, (ymid + 2 * dmax));
ExpandedXZ[VertexCount + 2] = new V2((xmid + 2 * dmax), (ymid - dmax));
List<Triangle> TriangleList = new List<Triangle>
{
new Triangle(VertexCount, VertexCount + 1, VertexCount + 2)
};
for (int ii1 = 0; ii1 < VertexCount; ii1++)
{
List<Edge> Edges = new List<Edge>();
for (int ii2 = 0; ii2 < TriangleList.Count; ii2++)
{
if (TriangulatePolygonSubFunc_InCircle(
ExpandedXZ[ii1], ExpandedXZ[TriangleList[ii2].p1],
ExpandedXZ[TriangleList[ii2].p2],
ExpandedXZ[TriangleList[ii2].p3]))
{
Edges.Add(new Edge(TriangleList[ii2].p1, TriangleList[ii2].p2));
Edges.Add(new Edge(TriangleList[ii2].p2, TriangleList[ii2].p3));
Edges.Add(new Edge(TriangleList[ii2].p3, TriangleList[ii2].p1));
TriangleList.RemoveAt(ii2);
ii2--;
}
}
if (ii1 >= VertexCount) { continue; }
for (int ii2 = Edges.Count - 2; ii2 >= 0; ii2--)
{
for (int ii3 = Edges.Count - 1; ii3 >= ii2 + 1; ii3--)
{
if (Edges[ii2].Equals(Edges[ii3]))
{
Edges.RemoveAt(ii3);
Edges.RemoveAt(ii2);
ii3--;
continue;
}
}
}
for (int ii2 = 0; ii2 < Edges.Count; ii2++)
{
TriangleList.Add(new Triangle(Edges[ii2].p1, Edges[ii2].p2, ii1));
}
Edges.Clear();
Edges = null;
}
for (int ii1 = TriangleList.Count - 1; ii1 >= 0; ii1--)
{
if (TriangleList[ii1].p1 >= VertexCount ||
TriangleList[ii1].p2 >= VertexCount ||
TriangleList[ii1].p3 >= VertexCount)
{ TriangleList.RemoveAt(ii1); }
}
TriangleList.TrimExcess();
int[] Triangles = new int[3 * TriangleList.Count];
for (int ii1 = 0; ii1 < TriangleList.Count; ii1++)
{
Triangles[3 * ii1] = TriangleList[ii1].p1;
Triangles[3 * ii1 + 1] = TriangleList[ii1].p2;
Triangles[3 * ii1 + 2] = TriangleList[ii1].p3;
}
return Triangles;
}
/// <summary>
/// 凸面多边形三角剖分 布线更优
/// </summary>
/// <param name="XZofVertices"></param>
/// <returns></returns>
public static int[] TriangulateConvexPolygon(Vector2[] XZofVertices)
{
int VertexCount = XZofVertices.Length;
float xmin = XZofVertices[0].x;
float ymin = XZofVertices[0].y;
float xmax = xmin;
float ymax = ymin;
for (int ii1 = 1; ii1 < VertexCount; ii1++)
{
if (XZofVertices[ii1].x < xmin) { xmin = XZofVertices[ii1].x; }
else if (XZofVertices[ii1].x > xmax) { xmax = XZofVertices[ii1].x; }
if (XZofVertices[ii1].y < ymin) { ymin = XZofVertices[ii1].y; }
else if (XZofVertices[ii1].y > ymax) { ymax = XZofVertices[ii1].y; }
}
float dx = xmax - xmin;
float dy = ymax - ymin;
float dmax = (dx > dy) ? dx : dy;
float xmid = (xmax + xmin) * 0.5f;
float ymid = (ymax + ymin) * 0.5f;
Vector2[] ExpandedXZ = new Vector2[3 + VertexCount];
for (int ii1 = 0; ii1 < VertexCount; ii1++)
{
ExpandedXZ[ii1] = XZofVertices[ii1];
}
ExpandedXZ[VertexCount] = new Vector2((xmid - 2 * dmax), (ymid - dmax));
ExpandedXZ[VertexCount + 1] = new Vector2(xmid, (ymid + 2 * dmax));
ExpandedXZ[VertexCount + 2] = new Vector2((xmid + 2 * dmax), (ymid - dmax));
List<Triangle> TriangleList = new List<Triangle>
{
new Triangle(VertexCount, VertexCount + 1, VertexCount + 2)
};
for (int ii1 = 0; ii1 < VertexCount; ii1++)
{
List<Edge> Edges = new List<Edge>();
for (int ii2 = 0; ii2 < TriangleList.Count; ii2++)
{
if (TriangulatePolygonSubFunc_InCircle(
ExpandedXZ[ii1], ExpandedXZ[TriangleList[ii2].p1],
ExpandedXZ[TriangleList[ii2].p2],
ExpandedXZ[TriangleList[ii2].p3]))
{
Edges.Add(new Edge(TriangleList[ii2].p1, TriangleList[ii2].p2));
Edges.Add(new Edge(TriangleList[ii2].p2, TriangleList[ii2].p3));
Edges.Add(new Edge(TriangleList[ii2].p3, TriangleList[ii2].p1));
TriangleList.RemoveAt(ii2);
ii2--;
}
}
if (ii1 >= VertexCount) { continue; }
for (int ii2 = Edges.Count - 2; ii2 >= 0; ii2--)
{
for (int ii3 = Edges.Count - 1; ii3 >= ii2 + 1; ii3--)
{
if (Edges[ii2].Equals(Edges[ii3]))
{
Edges.RemoveAt(ii3);
Edges.RemoveAt(ii2);
ii3--;
continue;
}
}
}
for (int ii2 = 0; ii2 < Edges.Count; ii2++)
{
TriangleList.Add(new Triangle(Edges[ii2].p1, Edges[ii2].p2, ii1));
}
Edges.Clear();
Edges = null;
}
for (int ii1 = TriangleList.Count - 1; ii1 >= 0; ii1--)
{
if (TriangleList[ii1].p1 >= VertexCount ||
TriangleList[ii1].p2 >= VertexCount ||
TriangleList[ii1].p3 >= VertexCount)
{ TriangleList.RemoveAt(ii1); }
}
TriangleList.TrimExcess();
int[] Triangles = new int[3 * TriangleList.Count];
for (int ii1 = 0; ii1 < TriangleList.Count; ii1++)
{
Triangles[3 * ii1] = TriangleList[ii1].p1;
Triangles[3 * ii1 + 1] = TriangleList[ii1].p2;
Triangles[3 * ii1 + 2] = TriangleList[ii1].p3;
}
return Triangles;
}
/// <summary>
/// 构建凹多边形 仅能计算简单的凹多边形
/// </summary>
/// <param name="_points"></param>
/// <returns></returns>
public static int[] TriangulateConcavePolygon(V2[] _points)
{
List<int> indices = new List<int>();
int n = _points.Length;
if (n < 3)
{
return indices.ToArray();
}
int[] V = new int[n];
for (int v = 0; v < n; v++)
{
V[v] = v;
}
//能够判定为凹多边形的 面积一定不为零 切当前构建顺序为顺时针，因此不需要做面积判断直接 正序排列顶点即可
if (Area(_points) >= 0.0f)
{
for (int v = 0; v < n; v++)
{
V[v] = v;
}
}
else
{
for (int v = 0; v < n; v++)
{
V[v] = (n - 1) - v;
}
}
int nv = n;
int count = 2 * nv;
for (int v = nv - 1; nv > 2;)
{
if ((count--) < -1)
{
return indices.ToArray();
}
int u = v;
if (nv <= u)
{
u = 0;
}
v = u + 1;
if (nv <= v)
{
v = 0;
}
int w = v + 1;
if (nv <= w)
{
w = 0;
}
if (Snip(_points, u, v, w, nv, V))
{
int a, b, c, s, t;
a = V[u];
b = V[v];
c = V[w];
indices.Add(a);
indices.Add(b);
indices.Add(c);
for (s = v, t = v + 1; t < nv; s++, t++)
{
V[s] = V[t];
}
nv--;
count = 2 * nv;
}
}
return indices.ToArray();
}
/// <summary>
/// 构建凹多边形 仅能计算简单的凹多边形
/// </summary>
/// <param name="_points"></param>
/// <returns></returns>
public static int[] TriangulateConcavePolygon(Vector2[] _points)
{
List<int> indices = new List<int>();
int n = _points.Length;
if (n < 3)
{
return indices.ToArray();
}
int[] V = new int[n];
for (int v = 0; v < n; v++)
{
V[v] = v;
}
//能够判定为凹多边形的 面积一定不为零 切当前构建顺序为顺时针，因此不需要做面积判断直接 正序排列顶点即可
if (Area(_points) >= 0.0f)
{
for (int v = 0; v < n; v++)
{
V[v] = v;
}
}
else
{
for (int v = 0; v < n; v++)
{
V[v] = (n - 1) - v;
}
}
int nv = n;
int count = 2 * nv;
for (int v = nv - 1; nv > 2;)
{
if ((count--) < -1)
{
return indices.ToArray();
}
int u = v;
if (nv <= u)
{
u = 0;
}
v = u + 1;
if (nv <= v)
{
v = 0;
}
int w = v + 1;
if (nv <= w)
{
w = 0;
}
if (Snip(_points, u, v, w, nv, V))
{
int a, b, c, s, t;
a = V[u];
b = V[v];
c = V[w];
indices.Add(a);
indices.Add(b);
indices.Add(c);
for (s = v, t = v + 1; t < nv; s++, t++)
{
V[s] = V[t];
}
nv--;
count = 2 * nv;
}
}
return indices.ToArray();
}
/// <summary>
/// 自动三角剖分 注意 凹凸多边形计算后 三角面构建顺序不同 记得翻面
/// </summary>
/// <param name="_points"></param>
/// <returns></returns>
public static int[] TriangulatePolygon(Vector2[] _points)
{
if (IsConcavePolygon(_points))
{
return TriangulateConcavePolygon(_points);
}
else
{
return TriangulateConvexPolygon(_points);
}
}
/// <summary>
/// 检测给定的点 是否是凹多边形
/// </summary>
/// <param name="curveloopPoints"></param>
/// <returns></returns>
public static bool IsConcavePolygon(V2[] _points)
{
int n = _points.Length;
for (int i = 0; i < n; i++)
{
double t = (_points[i % n].x - _points[(i + 2) % n].x) * (_points[(i + 1) % n].y - _points[(i + 2) % n].y) - (_points[(i + 1) % n].x - _points[(i + 2) % n].x) * (_points[i % n].y - _points[(i + 2) % n].y);
if (t < 0)
{
return true;
}
}
return false;
}
/// <summary>
/// 检测给定的点 是否是凹多边形
/// </summary>
/// <param name="curveloopPoints"></param>
/// <returns></returns>
public static bool IsConcavePolygon(Vector2[] _points)
{
int n = _points.Length;
for (int i = 0; i < n; i++)
{
float t = (_points[i % n].x - _points[(i + 2) % n].x) * (_points[(i + 1) % n].y - _points[(i + 2) % n].y) - (_points[(i + 1) % n].x - _points[(i + 2) % n].x) * (_points[i % n].y - _points[(i + 2) % n].y);
if(t < 0)
{
return true;
}
}
return false;
}
/// <summary>
/// 多边形等距缩放 注意参数为负是向内收缩， 为正是向外扩张(有问题待修复)
/// </summary>
/// <param name="_points"></param>
/// <param name="_scale"></param>
/// <returns></returns>
public static List<Vector2> Scale(List<Vector2> _points, float _scale)
{
List<Vector2> normalizeds = new List<Vector2>();
List<Vector2> points = new List<Vector2>();
for (int i = 0; i < _points.Count; i++)
{
normalizeds.Add((_points[i == _points.Count -1 ? 0 : i + 1] - _points[i]).normalized);
}
for (int i = 0; i < _points.Count; i++)
{
int startIndex = i;
int endIndex =( i == _points.Count - 1 ? 0 : i + 1);
float sina = _points[startIndex].x * _points[endIndex].y - _points[startIndex].y * _points[endIndex].x;
float len = _scale / sina;
Vector2 vec = normalizeds[endIndex] - normalizeds[startIndex];
Vector2 point = _points[i] + vec * len;
points.Add(point);
}
return points;
}
/// <summary>
/// 检测给定的点 是否是凹多边形 计算内角和法
/// </summary>
/// <param name="curveloopPoints"></param>
/// <returns></returns>
public static bool IsConcavePolygon(List<Vector3> curveloopPoints)
{
//使用角度和判断凹凸性：凸多边形的内角和为（n-2）*180°
var num = curveloopPoints.Count;
float angleSum = 0.0f;
for (int i = 0; i < num; i++)
{
Vector3 e1;
if (i == 0)
{
e1 = curveloopPoints[num - 1] - curveloopPoints[i];
}
else
{
e1 = curveloopPoints[i - 1] - curveloopPoints[i];
}
Vector3 e2;
if (i == num - 1)
{
e2 = curveloopPoints[0] - curveloopPoints[i];
}
else
{
e2 = curveloopPoints[i + 1] - curveloopPoints[i];
}
//标准化
e1.Normalize();
e2.Normalize();
//计算点乘
float mdot = Vector3.Dot(e1, e2);
//计算夹角弧度
float theta = Mathf.Acos(mdot);
//注意计算内角
angleSum += theta;
}
//计算内角和
float convexAngleSum = (float)((num - 2)) * Mathf.PI;
//判断凹凸性
if (angleSum < convexAngleSum)
{
return true;//是凹
}
return false;//否则是凸
}
/// <summary>
/// 计算三角形的大小
/// </summary>
/// <param name="_points"></param>
/// <returns></returns>
private static double Area(V2[] _points)
{
int n = _points.Length;
double A = 0.0f;
for (int p = n - 1, q = 0; q < n; p = q++)
{
V2 pval = _points[p];
V2 qval = _points[q];
A += pval.x * qval.y - qval.x * pval.y; //Cross
}
return (A * 0.5); // Triangle Size
}
/// <summary>
/// 计算三角形的大小
/// </summary>
/// <param name="_points"></param>
/// <returns></returns>
private static float Area(Vector2[] _points)
{
int n = _points.Length;
float A = 0.0f;
for (int p = n - 1, q = 0; q < n; p = q++)
{
Vector2 pval = _points[p];
Vector2 qval = _points[q];
A += pval.x * qval.y - qval.x * pval.y; //Cross
}
return (A * 0.5f); // Triangle Size
}
/// <summary>
/// 检测三角形是否 可继续拆分
/// </summary>
/// <param name="_points"></param>
/// <param name="u"></param>
/// <param name="v"></param>
/// <param name="w"></param>
/// <param name="n"></param>
/// <param name="V"></param>
/// <returns></returns>
private static bool Snip(V2[] _points, int u, int v, int w, int n, int[] V)
{
int p;
V2 A = _points[V[u]];
V2 B = _points[V[v]];
V2 C = _points[V[w]];
if (float.Epsilon > (((B.x - A.x) * (C.y - A.y)) - ((B.y - A.y) * (C.x - A.x))))
{
return false; // 三边重合以及方向检测
}
for (p = 0; p < n; p++)
{
if ((p == u) || (p == v) || (p == w))
{
continue;
}
V2 P = _points[V[p]];
if (InsideTriangle(A, B, C, P))
{
return false;
}
}
return true;
}
/// <summary>
/// 检测三角形是否 可继续拆分
/// </summary>
/// <param name="_points"></param>
/// <param name="u"></param>
/// <param name="v"></param>
/// <param name="w"></param>
/// <param name="n"></param>
/// <param name="V"></param>
/// <returns></returns>
private static bool Snip(Vector2[] _points, int u, int v, int w, int n, int[] V)
{
int p;
Vector2 A = _points[V[u]];
Vector2 B = _points[V[v]];
Vector2 C = _points[V[w]];
if (float.Epsilon> (((B.x - A.x) * (C.y - A.y)) - ((B.y - A.y) * (C.x - A.x))))
{
return false; // 三边重合以及方向检测
}
for (p = 0; p < n; p++)
{
if ((p == u) || (p == v) || (p == w))
{
continue;
}
Vector2 P = _points[V[p]];
if (InsideTriangle(A, B, C, P))
{
return false;
}
}
return true;
}
/// <summary>
/// 获取不规则多边形几何中心点
/// </summary>
/// <param name="mPoints"></param>
/// <returns></returns>
public static Vector2 GetCenterPoint(Vector2[] mPoints)
{
float cx = (GetMinX(mPoints) + GetMaxX(mPoints)) / 2;
float cy = (GetMinY(mPoints) + GetMaxY(mPoints)) / 2;
return new Vector2(cx, cy);
}
/// <summary>
/// 获取不规则多边形几何中心点
/// </summary>
/// <param name="mPoints"></param>
/// <returns></returns>
public static V2 GetCenterPoint(V2[] mPoints)
{
double cx = (GetMinX(mPoints) + GetMaxX(mPoints)) / 2;
double cy = (GetMinY(mPoints) + GetMaxY(mPoints)) / 2;
return new V2(cx, cy);
}
/// <summary>
/// 获取最小X值
/// </summary>
/// <param name="mPoints"></param>
/// <returns></returns>
public static float GetMinX(Vector2[] mPoints)
{
float minX = 0;
if (mPoints.Length > 0)
{
minX = mPoints[0].x;
foreach (Vector2 point in mPoints)
{
if (point.x < minX)
minX = point.x;
}
}
return minX;
}
/// <summary>
/// 获取最小X值
/// </summary>
/// <param name="mPoints"></param>
/// <returns></returns>
public static double GetMinX(V2[] mPoints)
{
double minX = 0;
if (mPoints.Length > 0)
{
minX = mPoints[0].x;
foreach (V2 point in mPoints)
{
if (point.x < minX)
minX = point.x;
}
}
return minX;
}
/// <summary>
/// 获取最大X值
/// </summary>
/// <param name="mPoints"></param>
/// <returns></returns>
public static double GetMaxX(V2[] mPoints)
{
double maxX = 0;
if (mPoints.Length > 0)
{
maxX = mPoints[0].x;
foreach (V2 point in mPoints)
{
if (point.x > maxX)
maxX = point.x;
}
}
return maxX;
}
/// <summary>
/// 获取最大X值
/// </summary>
/// <param name="mPoints"></param>
/// <returns></returns>
public static float GetMaxX(Vector2[] mPoints)
{
float maxX = 0;
if (mPoints.Length > 0)
{
maxX = mPoints[0].x;
foreach (Vector2 point in mPoints)
{
if (point.x > maxX)
maxX = point.x;
}
}
return maxX;
}
/// <summary>
/// 获取最小Y值
/// </summary>
/// <param name="mPoints"></param>
/// <returns></returns>
public static double GetMinY(V2[] mPoints)
{
double minY = 0;
if (mPoints.Length > 0)
{
minY = mPoints[0].y;
foreach (V2 point in mPoints)
{
if (point.y < minY)
minY = point.y;
}
}
return minY;
}
/// <summary>
/// 获取最小Y值
/// </summary>
/// <param name="mPoints"></param>
/// <returns></returns>
public static float GetMinY(Vector2[] mPoints)
{
float minY = 0;
if (mPoints.Length > 0)
{
minY = mPoints[0].y;
foreach (Vector2 point in mPoints)
{
if (point.y < minY)
minY = point.y;
}
}
return minY;
}
/// <summary>
/// 获取最大Y值
/// </summary>
/// <param name="mPoints"></param>
/// <returns></returns>
public static double GetMaxY(V2[] mPoints)
{
double maxY = 0;
if (mPoints.Length > 0)
{
maxY = mPoints[0].y;
foreach (V2 point in mPoints)
{
if (point.y > maxY)
maxY = point.y;
}
}
return maxY;
}
/// <summary>
/// 获取最大Y值
/// </summary>
/// <param name="mPoints"></param>
/// <returns></returns>
public static float GetMaxY(Vector2[] mPoints)
{
float maxY = 0;
if (mPoints.Length > 0)
{
maxY = mPoints[0].y;
foreach (Vector2 point in mPoints)
{
if (point.y > maxY)
maxY = point.y;
}
}
return maxY;
}
/// <summary>
/// 获取不规则多边形重心点
/// </summary>
/// <param name="mPoints"></param>
/// <returns></returns>
public static Vector2 GetGravityPoint(List<Vector2> mPoints)
{
float area = 0.0f;//多边形面积
float gx = 0.0f, gy = 0.0f;// 重心的x、y
for (int i = 1; i <= mPoints.Count; i++)
{
float iX = mPoints[i % mPoints.Count].x;
float iY = mPoints[i % mPoints.Count].y;
float nextX = mPoints[i - 1].x;
float nextY = mPoints[i - 1].y;
float temp = (iX * nextY - iY * nextX) * 0.5f;
area += temp;
gx += temp * (iX + nextX) / 3.0f;
gy += temp * (iY + nextY) / 3.0f;
}
gx = gx / area;
gy = gy / area;
Vector2 v2 = new Vector2(gx, gy);
return v2;
}
/// <summary>
/// 计算 点 P 是否在 A、B、C 围成的三角形中
/// </summary>
/// <param name="A"></param>
/// <param name="B"></param>
/// <param name="C"></param>
/// <param name="P"></param>
/// <returns></returns>
public static bool InsideTriangle(V2 A, V2 B, V2 C, V2 P)
{
double ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
double cCROSSap, bCROSScp, aCROSSbp;
ax = C.x - B.x; ay = C.y - B.y;
bx = A.x - C.x; by = A.y - C.y;
cx = B.x - A.x; cy = B.y - A.y;
apx = P.x - A.x; apy = P.y - A.y;
bpx = P.x - B.x; bpy = P.y - B.y;
cpx = P.x - C.x; cpy = P.y - C.y;
aCROSSbp = ax * bpy - ay * bpx;
cCROSSap = cx * apy - cy * apx;
bCROSScp = bx * cpy - by * cpx;
return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
}
public static double CrossVec2(V2 a, V2 b)
{
return (a.x * b.y) - (a.y * b.x);
}
/// <summary>
/// 计算 点 P 是否在 A、B、C 围成的三角形中
/// </summary>
/// <param name="A"></param>
/// <param name="B"></param>
/// <param name="C"></param>
/// <param name="P"></param>
/// <returns></returns>
public static bool InsideTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
{
float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
float cCROSSap, bCROSScp, aCROSSbp;
ax = C.x - B.x; ay = C.y - B.y;
bx = A.x - C.x; by = A.y - C.y;
cx = B.x - A.x; cy = B.y - A.y;
apx = P.x - A.x; apy = P.y - A.y;
bpx = P.x - B.x; bpy = P.y - B.y;
cpx = P.x - C.x; cpy = P.y - C.y;
aCROSSbp = ax * bpy - ay * bpx;
cCROSSap = cx * apy - cy * apx;
bCROSScp = bx * cpy - by * cpx;
return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
}
public static float CrossVec2(Vector2 a, Vector2 b)
{
return (a.x * b.y) - (a.y * b.x);
}
/// <summary>
/// 检测三角形 顶点数组是否为顺时针排列 返回1表示顺时针，0表示三点共线，-1表示逆时针
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <param name="c"></param>
/// <returns></returns>
public static bool CheckClockwise(Vector3 a, Vector3 b, Vector3 c)
{
float m00 = a.x;
float m01 = a.y;
float m02 = a.z;
float m10 = b.x;
float m11 = b.y;
float m12 = b.z;
float m20 = c.x;
float m21 = c.y;
float m22 = c.z;
// 计算det.
float f =
m00 * (m11 * m22 - m12 * m21)
+ m01 * (m12 * m20 - m10 * m22)
+ m02 * (m10 * m21 - m11 * m20);
return f >= 0;
}
#endregion
}
以上就是三角剖分的核心算法，其中还包含了几何中心计算，包含关系计算，凸多边形索引计算、凹多边形索引计算、凹凸多边形判定、三角面构建顺序判定等等，都是图形计算中比较常用的算法。
接下来就是如何使用了：
首先我们先要读取到shp或者genjson的数据，网上有很多，我就不赘述了
然后是将WGS84经纬度转到Unity的世界坐标，通常采用的方式是用两个点来计算比例，网上也有很多。
转换之后我们会获取到图形的数组，这样我们就可以计算怎么构建出图形了
首先我们需要先判断下所给定的点是不是首位点重复，如果重复我们需要去重一次
//判断首尾点是否为同一点
if (Triangulator.FloatEqual(Vector3.Distance(surfacePoints[0], surfacePoints[count - 1]), 0.0f))
{
count--;
}
去重后我们需要吧Vector3[] 数组转换到我们计算需要的V[] 数组
for (int i = 0; i < count; i++)
{
d2Verts[i] = new V2(surfacePoints[i].x, surfacePoints[i].z);
normals[i] = Vector3.up;
}
上面顺便将所有的顶点的法线都设置成了Vector.up，也就是向上
之后我们就需要使用封装好的三角剖分类来计算顶点的索引了
//使用三角剖分计算 三角面索引
int[] bv = Triangulator.TriangulateConcavePolygon(d2Verts);
上面的bv就是几何面顶点的索引，在Triangulator.TriangulateConcavePolygon中会自动计算多边形的凹凸性，并进行计算，拿到顶点的索引后我们还需要计算多边形上的UV，我这里采用的方式是计算外接正方形，然后根据每个点在x、y上的位置计算相应的UV
//获取顶面外接四边形 用来计算uv分布
float minX = (float)Triangulator.GetMinX(d2Verts);
float maxX = (float)Triangulator.GetMaxX(d2Verts);
float minY = (float)Triangulator.GetMinY(d2Verts);
float maxY = (float)Triangulator.GetMaxY(d2Verts);
float xLen = maxX - minX;
float yLen = maxY - minY;
for (int i = 0; i < count; i++)
{
uvs[i] = new Vector2((surfacePoints[i].x - minX) / xLen, (surfacePoints[i].z - minY) / yLen);
}
这样一个建筑 或者水系的 图形就可以被构建出来了，如果是建筑的话，还需将其面提高到对应的高度，并添加立面的mesh，相对比较简单，我就不一一细说了；
|