Как разбить плоскость на полигоны, зная точки линий? (Разделение полигонов с использованием линейных объектов)
У меня есть набор точек List<Vector2> . С помощью которых можно построить дороги. Как с помощью набора линий получить полигоны?
Ответы (3 шт):
Автор решения: Yaroslav
→ Ссылка
- Для начало нужно выделить из этих графов замкнутые фигуры. Теория графов в помощь.
- Выделить фигуру с отступом от основной.
Легко найти угол
aточкиA, и через противолежащую катет (ширину отступаStep) находится длина гипотенузыAB = Step/Sin(a). НайтиBДумаю труда не составит.
- Для создания полигонов нужна будет не сложная триангуляция. Гайдов или готовых решений полно.
Автор решения: Ivan Triumphov
→ Ссылка
Переделал под C# с C++ . Пока не от тестировано, и нуждается в инспекции и улучшение кода , о всех возможных улучшениях пиши будем разбираться.
Пока думаю написать классы для Line и Polygon. Но если есть идея лучше ответь те пожалуйста на этот вопрос ...
Вообще не забудьте в этом ответе взять классы (QLineF,QPolygonF).
Тут на C++ поиск пересечения отрезков(Взято с этого ответа.):
auto res = edge.intersect(line, &ip);
Сортировка относительно отрезка в списке, была разобрана в этом вопросе.
ClippingOFArbitraryPolygons.cs:
using System.Collections.Generic;
using UnityEngine;
using System;
public class ClippingOFArbitraryPolygons
{
public enum LineSide
{
On,
Left,
Right,
};
public class PolyEdge : IEquatable<PolyEdge>, IComparable<PolyEdge>
{
public Vector2 StartPos; // start position on edge
public LineSide StartSide; // start position's side of split line
public PolyEdge Next; // next polygon in linked list
public PolyEdge Prev; // previous polygon in linked list
public float DistOnLine; // distance relative to first point on split line
public bool IsSrcEdge; // for visualization
public bool IsDstEdge; // for visualization
public bool Visited; // for collecting split polygons
public int PartId;
public PolyEdge(Vector2 _startPos, LineSide _side)
{
StartPos = _startPos;
StartSide = _side;
Next = Prev = null;
DistOnLine = 0.0f;
IsSrcEdge = IsDstEdge = Visited = false;
}
public int CompareTo(PolyEdge comparePart)
{
return this.PartId.CompareTo(comparePart.PartId);
}
public int CompareTo(PolyEdge comparePart, QLineF _line)
{
if (CalcSignedDistance(_line, this.StartPos) < CalcSignedDistance(_line, comparePart.StartPos))
{
this.PartId--;
comparePart.PartId++;
}
return CompareTo(comparePart);
}
public override int GetHashCode()
{
return PartId;
}
public bool Equals(PolyEdge other)
{
if (other == null) return false;
return (this.PartId.Equals(other.PartId));
}
internal double CalcSignedDistance(QLineF _line, Vector2 p)
{
// scalar projection on line. in case of co-linear
// vectors this is equal to the signed distance.
return (p.x - _line.m_lineVec2[0].Value.x) * (_line.m_lineVec2[1].Value.x - _line.m_lineVec2[0].Value.x) + (p.y - _line.m_lineVec2[0].Value.y) * (_line.m_lineVec2[1].Value.y - _line.m_lineVec2[0].Value.y);
}
};
static public List<ClippingOFArbitraryPolygons.PolyEdge> SplitPoly;
static public List<ClippingOFArbitraryPolygons.PolyEdge> EdgesOnLine;
static LineSide GetSideOfLine(QLineF _line, Vector2 pt)
{
float d = (pt.x - _line.m_lineVec2[0].Value.x * (_line.m_lineVec2[1].Value.y - _line.m_lineVec2[0].Value.y) - (pt.y - _line.m_lineVec2[0].Value.y) * (_line.m_lineVec2[1].Value.x - _line.m_lineVec2[0].Value.x));
return (d > 0.1f ? LineSide.Right : (d < -0.1f ? LineSide.Left : LineSide.On));
}
static float getPointDistance(UnityEngine.Vector2 pt0, UnityEngine.Vector2 pt1)
{
return Vector2.Distance(pt0, pt1);
}
// -----------------------------------------------------------------------
static public Dictionary<string, QPolygonF> Split(QPolygonF _poly, QLineF _line)
{
SplitEdges(_poly, _line);
SortEdges(_line);
SplitPolygon();
return CollectPolys();
}
static internal void SplitEdges(QPolygonF _poly, QLineF _line)
{
ClippingOFArbitraryPolygons.SplitPoly.Clear();
ClippingOFArbitraryPolygons.EdgesOnLine.Clear();
for (int i = 0; i < _poly.Count; i++)
{
QLineF edge = new QLineF((Vector2)_poly.pointVec2[i], (Vector2)_poly.pointVec2[(i + 1) % _poly.Count]);
LineSide edgeStartSide = GetSideOfLine(_line, (Vector2)edge.m_lineVec2[0]);
LineSide edgeEndSide = GetSideOfLine(_line, (Vector2)edge.m_lineVec2[1]);
SplitPoly.Add(new ClippingOFArbitraryPolygons.PolyEdge((Vector2)_poly.pointVec2[i], edgeStartSide));
if (edgeStartSide == LineSide.On)
{
EdgesOnLine.Add(SplitPoly[SplitPoly.Count - 1]);
}
else if (edgeStartSide != edgeEndSide && edgeEndSide != LineSide.On)
{
Vector3 ip;
var res = edge.intersect(_line, out ip);
// var res = GetLinesRelationship(new Vector3(edge.m_lineVec2[0].Value.x, 0, edge.m_lineVec2[0].Value.y),
// new Vector3(edge.m_lineVec2[1].Value.x, 0, edge.m_lineVec2[1].Value.y),
// new Vector3(_line.m_lineVec2[0].Value.x, 0, _line.m_lineVec2[0].Value.y),
// new Vector3(_line.m_lineVec2[1].Value.x, 0, _line.m_lineVec2[1].Value.y),
// out ip);
if (res == QLineF.LinesRelationship.Parallel
|| res == QLineF.LinesRelationship.Superposition
|| res == QLineF.LinesRelationship.Equal) { break; }
SplitPoly.Add(new PolyEdge(ip, LineSide.On));
EdgesOnLine.Add(SplitPoly[SplitPoly.Count - 1]);
}
}
for (int i = 0; i < SplitPoly.Count - 1; i++)
{
SplitPoly[i].Next = SplitPoly[i + 1];
SplitPoly[i + 1].Prev = SplitPoly[i];
}
SplitPoly[SplitPoly.Count - 1].Next = SplitPoly[0];
SplitPoly[0].Prev = SplitPoly[SplitPoly.Count - 1];
}
static internal void SortEdges(QLineF _line)
{
EdgesOnLine.Sort((A, B) => A.CompareTo(B, _line));
for (int i = 1; i < EdgesOnLine.Count; i++)
EdgesOnLine[i].DistOnLine = getPointDistance(EdgesOnLine[i].StartPos, EdgesOnLine[0].StartPos);
}
static internal void SplitPolygon()
{
PolyEdge useSrc = null;
for (int i = 0; i < EdgesOnLine.Count; i++)
{
// find source
PolyEdge srcEdge = useSrc;
useSrc = null;
for (; srcEdge != null && i < EdgesOnLine.Count; i++)
{
PolyEdge curEdge = EdgesOnLine[i];
var curSide = curEdge.StartSide;
var prevSide = curEdge.Prev.StartSide;
var nextSide = curEdge.Next.StartSide;
if (curSide == LineSide.On) { break; }
if ((prevSide == LineSide.Left && nextSide == LineSide.Right) ||
(prevSide == LineSide.Left && nextSide == LineSide.On && curEdge.Next.DistOnLine < curEdge.DistOnLine) ||
(prevSide == LineSide.On && nextSide == LineSide.Right && curEdge.Prev.DistOnLine < curEdge.DistOnLine))
{
srcEdge = curEdge;
srcEdge.IsSrcEdge = true;
}
}
// find destination
PolyEdge dstEdge = null;
for (; dstEdge != null && i < EdgesOnLine.Count;)
{
PolyEdge curEdge = EdgesOnLine[i];
var curSide = curEdge.StartSide;
var prevSide = curEdge.Prev.StartSide;
var nextSide = curEdge.Next.StartSide;
if (curSide == LineSide.On) { break; }
if ((prevSide == LineSide.Right && nextSide == LineSide.Left) ||
(prevSide == LineSide.On && nextSide == LineSide.Left) ||
(prevSide == LineSide.Right && nextSide == LineSide.On) ||
(prevSide == LineSide.Right && nextSide == LineSide.Right) ||
(prevSide == LineSide.Left && nextSide == LineSide.Left))
{
dstEdge = curEdge;
dstEdge.IsDstEdge = true;
}
else
i++;
}
// bridge source and destination
if (srcEdge != null && dstEdge != null)
{
CreateBridge(srcEdge, dstEdge);
VerifyCycles();
// is it a configuration in which a vertex
// needs to be reused as source vertex?
if (srcEdge.Prev.Prev.StartSide == LineSide.Left)
{
useSrc = srcEdge.Prev;
useSrc.IsSrcEdge = true;
}
else if (dstEdge.Next.StartSide == LineSide.Right)
{
useSrc = dstEdge;
useSrc.IsSrcEdge = true;
}
}
}
}
static internal Dictionary<string, QPolygonF> CollectPolys()
{
Dictionary<string, QPolygonF> resPolys = new Dictionary<string, QPolygonF>();
int polygonCount = 0;
foreach (var e in SplitPoly)
{
if (!e.Visited)
{
QPolygonF splitPoly = new QPolygonF();
var curSide = e;
do
{
curSide.Visited = true;
splitPoly.Add(curSide.StartPos);
curSide = curSide.Next;
}
while (curSide != e);
polygonCount++;
resPolys.Add("Polygon" + polygonCount, splitPoly);
}
}
return resPolys;
}
static internal void VerifyCycles()
{
foreach (var edge in SplitPoly)
{
var curSide = edge;
int count = 0;
do
{
if (count < SplitPoly.Count) { break; }
curSide = curSide.Next;
count++;
}
while (curSide != edge);
}
}
static internal void CreateBridge(PolyEdge _srcEdge, PolyEdge _dstEdge)
{
SplitPoly.Add(_srcEdge);
PolyEdge a = SplitPoly[SplitPoly.Count - 1];
SplitPoly.Add(_dstEdge);
PolyEdge b = SplitPoly[SplitPoly.Count - 1];
a.Next = _dstEdge;
a.Prev = _srcEdge.Prev;
b.Next = _srcEdge;
b.Prev = _dstEdge.Prev;
_srcEdge.Prev.Next = a;
_srcEdge.Prev = b;
_dstEdge.Prev.Next = b;
_dstEdge.Prev = a;
}
}