Какой простой способ заполнить вогнутую геометрию контура, чтобы она была выпуклой (найти вогнутые вершины и удалить их)? - PullRequest
Новая
       55

Какой простой способ заполнить вогнутую геометрию контура, чтобы она была выпуклой (найти вогнутые вершины и удалить их)?

2 голосов
/ 09 июля 2010

У меня есть PathGeometry (многоугольник), построенный из LineSegments на одном PathFigure, и я хотел бы убедиться, что это Выпуклый. У меня есть метод, использующий CrossProduct, чтобы определить, является ли геометрия выпуклой, я предполагал, что могу просто вернуть список точек, которые делают его вогнутым, когда он ложный, и удалить эти точки, чтобы заполнить многоугольник, но он работает не совсем правильно.

Вот код, который я получил: 

    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);
        }

В конечном счете, я бы хотел превратить мою вогнутую геометрию в выпуклую, как это:

альтернативный текст http://i28.tinypic.com/34zhjzm.png

Ответы [ 2 ]

0 голосов
/ 09 июля 2010

Я бы вычислил выпуклую оболочку (также: NTS ) и удалил все вершины внутри получающегося многоугольника выпуклой оболочки (используя точка-точка полигон тест).

0 голосов
/ 09 июля 2010

Вы перебираете каждую тройку смежных вершин (ABC, BCD, CDE и т. Д.).Для каждого триплета вы вычисляете среднюю точку сегмента, связывающего первую и третью вершины (вы подключаете AC в ABC, BD в BCD и т. Д.).Если средняя точка находится внутри многоугольника, вы переходите к следующему триплету.Если он находится снаружи, вы заменяете 2 сегмента, связывающих триплет, одним сегментом, связывающим крайние значения (то есть вы удаляете среднюю точку).Вы продолжаете, пока больше нет замен.

Если вы попробуете это на бумаге, вы получите именно тот результат, который описали.

Если я не ошибаюсь, вы можете проверить, если точкапринадлежит многоугольнику с Polygon.HitTestCore.

...