Как я могу определить, пересекаются ли два полигона?

Question

Представьте, что у меня есть координата 4 точек, которые образуют многоугольник. Эти точки представлены с помощью PointF в C #. Если у меня есть 2 многоугольника (используя 8 точек), как я могу определить, пересекаются ли они?

В классе Rectangle есть метод IntersectsWith, но я не смог найти что-то похожее для GraphicsPath или Region.

Любой совет будет принята с благодарностью.

Мош

Answer 1

Как уже говорил Чарли, вы можете использовать теорему о разделяющей оси.Проверьте эту статью для реализации C # и примера обнаружения столкновений полигонов.

Я также ответил на этот вопрос здесь , который имеет дело с двумерным столкновением в C #.

Answer 2

Строго говоря, другие ответы, предполагающие алгоритм, являются, вероятно, вашим лучшим выбором.Но помимо производительности, вы упомянули, что не можете найти ничего подобного IntersectsWith для GraphicsPath или Region.Однако существует метод Intersect, который обновляет область, чтобы она стала пересечением самой себя и другой области или пути.Вы можете создать две области: Пересечь () одну с другой, а затем проверить на Region.IsEmpty ().

Но я думаю, что это довольно медленноспособ сделать это и, вероятно, приведет к большому количеству выделений, если сделать в цикле.

Answer 3

Это старый вопрос, но я подумал, что тоже поделюсь своим решением.Region.IsEmpty () требует графического контекста и, насколько я понимаю, предназначен только для тестирования на точность пикселей.Это не идеально для многих ситуаций.Гораздо лучшим решением является использование библиотеки Clipper Ангуса Джонсона.По моему опыту это быстро хорошо проверенная библиотека.Вы можете обеспечить свою точность и обрабатывать чрезвычайно сложные многоугольники.

http://www.angusj.com/delphi/clipper.php

Существует реализация на C #.Вам нужно будет выполнить операцию пересечения, как метод System.Drawing.Region.Затем изучите результат операции.Если он пуст, пересечения не было.Если он содержит данные, то данные являются пересекающимися точками.

http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/ClipType.htm

Некоторые методы, которые вы найдете для этого полезными.

private static int scale = 1000; //your desired precision

        public static List<List<IntPoint>> ConvertToClipperPolygons(GraphicsPath path)
    {
        var Polygon = new List<IntPoint>();
        var Polygons = new List<List<IntPoint>>();

        var it = new GraphicsPathIterator(path);
        it.Rewind();
        bool isClosed;
        int startIndex;
        int endIndex;
        for (int i = 0; i < it.SubpathCount; i++)
        {
            var PointCount = it.NextSubpath(out startIndex, out endIndex, out isClosed);

            var Points = new PointF[PointCount];
            var Types = new byte[PointCount];
            it.CopyData(ref Points, ref Types, startIndex, endIndex);
            Polygons.Add(new List<IntPoint>(Points.Select(x => new IntPoint(Convert.ToInt64(x.X * scale), Convert.ToInt64(x.Y * scale)))));

        }
        it.Dispose();
        return Polygons;
    }

И для выполнения пересечения

        public static GraphicsPath intersect(ref GraphicsPath p1, ref GraphicsPath p2)
    {
        List<List<IntPoint>> polygonB = ConvertToClipperPolygons(p1);
        List<List<IntPoint>> polygons = new List<List<IntPoint>>();
        List<List<IntPoint>> polygonA = ConvertToClipperPolygons(p2);

        Clipper c = new Clipper();
        c.AddPolygons(polygonB, PolyType.ptSubject);
        c.AddPolygons(polygonA, PolyType.ptClip);
        c.Execute(ClipType.ctIntersection, polygons, PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd);

        return ConvertClipperToGraphicsPath(polygons);
    }
        public static GraphicsPath ConvertClipperToGraphicsPath(List<List<IntPoint>> path)
    {
        GraphicsPath returnPath = new GraphicsPath();

        for (int i = 0; i < path.Count; i++)
        {
            returnPath.AddPolygon(ToPointList(path[i]).ToArray());
        }
        return returnPath;
    }
        private static List<PointF> ToPointList(List<IntPoint> pointList)
    {

        List<PointF> newList = new List<PointF>();
        foreach (IntPoint pt in pointList)
        {
            newList.Add(new PointF(((float)pt.X / (float)scale), ((float)pt.Y / (float)scale)));
        }

        return newList;
    }

Answer 4

Если ваши многоугольники выпуклые, то вы можете использовать теорема о разделяющей оси .Демоверсия доступна здесь (она в ActionScript, но код должен легко переноситься на c #)

Это действительно не моя область, но я надеюсь, что она все равно поможет.