凹面軌道計を凸になるように埋める簡単な方法（凹面頂点を見つけ、それらを取り除く）？

Question

私は1つの経路上にラインセッグを構築したPATHGEOMETER（POLYGON）を持っています、そしてそれが凸であることを確認したいと思います。私は、幾何学的形状が凸状であるかどうかを判断するためにクロス製品を使用している方法があり、私はそれが偽のときにそれを凹状にし、それらのポイントを埋めるためにそれらのポイントを削除することができたばかりであると仮定していましたが、非常に正しく機能していません。

これが私が持っているコードです：

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

.

最終的には、このような凸形状を凸形状にすることができたいと思います。

Answer 1

凸包hull （ nts ）および内部の頂点を削除結果として生じる凸殻多角形の（ポイントインポリゴンテスト）。

Answer 2

隣接する頂点の各トリプレットを循環させる（ABC、BCD、CDEなど）。トリプレットごとに、最初と3番目の頂点をリンクするセグメントの中点を計算します（AUC、BCDのB-DなどのA-Cを接続します）。中点が多角形の内側にある場合は、次のトリプレットに移動します。外部の場合は、トリプレットと極値をリンクする1つのセグメントとリンクします（つまり、中点を削除します）。これ以上の置換が可能ではないまで続きます。

紙の上で試してみると、あなたが説明する結果を正確に手に入れます。

誤解していない場合、ポイントがPolygon.HitTestCoreを使用してポリゴンに属するかどうかをテストできます。