오목한 경로 지오메트리를 볼록하게 채우는 쉬운 방법은 무엇입니까(오목한 꼭지점을 찾고 제거)?
-
13-09-2020 - |
문제
나는 하나의 경로 그림에 선 세그먼트로 구성된 경로 기하학(다각형)을 가지고 있으며 그것이 볼록한 지 확인하고 싶습니다.나는 기하학이 볼록한 지 여부를 결정하기 위해 교차 제품을 사용하는 방법을 가지고 있는데,나는 그것이 거짓 일 때 오목하게 만드는 점들의 목록을 되돌려 놓고 그 점들을 제거하여 다각형을 채울 수 있다고 가정했지만 그것은 제대로 작동하지 않습니다.
여기 내가 가진 코드가 있습니다:
public static bool IsConvexPolygon(this IList<Point> polygon, out List<Point> concavePoints)
{
int n = polygon.Count;
List<double> result = new List<double>();
concavePoints = new List<Point>();
for (int i = 0; i < n; i++)
{
result.Add(polygon[i].CrossProduct(polygon[i.RotateNext(n)]));
if (result.Last() < 0.0)
{
concavePoints.Add(polygon[i.RotateNext(n)]);
}
}
return (result.All(d => d >= 0.0));
}
public static double CrossProduct(this Point p1, Point p2)
{
return (p1.X * p2.Y) - (p1.Y * p2.X);
}
public static int RotateNext(this int index, int count)
{
return (index + 1) % count;
}
public static PointCollection ExtractPoints(this Geometry geometry)
{
PointCollection pc = new PointCollection();
if (geometry is LineGeometry)
{
var lg = (LineGeometry)geometry;
pc.Add(lg.StartPoint);
pc.Add(lg.EndPoint);
return pc;
}
else if (geometry is PathGeometry)
{
var pg = (PathGeometry)geometry;
if (pg.Figures.Count > 0)
{
List<Point> points;
if ((pg.Figures[0].Segments.Count > 0) && (pg.Figures[0].Segments[0] is PolyLineSegment))
points = ((PolyLineSegment)pg.Figures[0].Segments[0]).Points.ToList();
else
points = pg.Figures[0].Segments.Select(seg => (seg as LineSegment).Point).ToList();
pc.Add(pg.Figures[0].StartPoint);
foreach (Point p in points)
pc.Add(p);
return pc;
}
}
else if (geometry is RectangleGeometry)
{
var rg = (RectangleGeometry)geometry;
var rect = rg.Rect;
pc.Add(rect.TopLeft);
pc.Add(rect.TopRight);
pc.Add(rect.BottomRight);
pc.Add(rect.BottomLeft);
return pc;
}
return pc;
}
public static Geometry CreateGeometryFromPoints(this List<Point> pts)
{
if (pts.Count < 2)
return null;
PathFigure pFig = new PathFigure() { StartPoint = pts[0] };
for (int i = 1; i < pts.Count; i++)
{
pFig.Segments.Add(new LineSegment(pts[i], true));
}
pFig.IsClosed = true;
PathGeometry pg = new PathGeometry(new List<PathFigure>() { pFig });
return pg;
}
public static Path CreatePolygonFromGeometry(this Geometry geo, Brush fillBrush)
{
Path path = new Path() { Stroke = Brushes.Black, StrokeThickness = 1, Fill = fillBrush };
path.Data = geo;
return path;
}
그리고 여기 제가 체크하고 다각형을 수정하는 곳이 있습니다:
List<Point> outstuff;
if (geo1.ExtractPoints().IsConvexPolygon(out outstuff) == false)
{
// Got to fill it in if it's concave
var newpts = geo1.ExtractPoints().Except(outstuff).ToList();
var z = newpts.CreateGeometryFromPoints().CreatePolygonFromGeometry(Brushes.Purple);
z.MouseRightButtonDown += delegate { canvas.Children.Remove(z); };
canvas.Children.Add(z);
}
궁극적으로 나는 내 오목한 기하학을 다음과 같이 볼록한 기하학으로 만들 수 있기를 원합니다:
해결책
convex hull ( nts ) 및 내부의 꼭지점을 제거합니다.결과 볼록한 선체 다각형 ( 포인트 인 - 폴리곤 테스트).
다른 팁
인접한 정점의 각 삼중 항을 순환합니다.각 삼중 항에 대해 첫 번째 및 세 번째 정점을 연결하는 세그먼트의 중간 지점을 계산합니다.중간 점이 다각형 안에 있으면 다음 삼중항으로 이동합니다.그것이 바깥쪽에 있다면,삼중 항을 연결하는 2 개의 세그먼트를 극단을 연결하는 하나의 세그먼트로 대체합니다(즉,중간 점을 제거합니다).더 이상 대체 할 수 없을 때까지 계속하십시오.
당신이 종이에 그것을 시도하는 경우,당신은 정확하게 당신이 설명하는 결과를 얻을.
내가 틀리지 않는 경우 점이 다각형에 속하는지 테스트 할 수 있습니다. Polygon.HitTestCore
.
제휴하지 않습니다 StackOverflow