抓取多边形

可以把long替换成double，按需
想要更更更更更精确，可以自己弄象限和叉积判断Part
Reference:
https://www.geometrictools.com/Documentation/MinimalCycleBasis.pdf
如果要轮廓线，可以去掉所有边有两条的，如果再要去掉内部多边形，可以判断点是否在多边形内
注释的部分别用，没测

using Microsoft.CSharp.RuntimeBinder;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.IO;
using System.Linq;

namespace polygoncircles
{
    public struct nd
    {
        public nd(long x, long y, int v, int oldv, double lng = 0, double lat = 0)
        {
            this.x = x;
            this.y = y;
            this.v = v;
            this.oldv = oldv;
            this.lng = lng;
            this.lat = lat;
        }
        public long x;
        public long y;
        public int v;
        public int oldv;
        public double lng;
        public double lat;
    }

    //public class Mercator
    //{
    //    public static nd toxy(nd nd)
    //    {
    //        var latitude = nd.y; // (φ)
    //        var longitude = nd.x;   // (λ)

    //        var mapWidth = 2000000;
    //        var mapHeight = 1000000;

    //        // get x value
    //        long x = (longitude + 180) * (mapWidth / 360);

    //        // convert from degrees to radians
    //        long latRad = latitude * Math.PI / 180;

    //        // get y value
    //        var mercN = Math.Log(Math.Tan((Math.PI / 4) + (latRad / 2)));
    //        var y = (mapHeight / 2) - (mapWidth * mercN / (2 * Math.PI));
    //        return new nd(x, y, nd.v, nd.oldv,nd.x,nd.y);
    //    }
    //}

    public class Part : IEquatable<Part>
    {
        public nd a;
        public nd b;
      
        public double val()
        {
            nd aa = a;
            aa.x = a.x + 1;
            var p1 = (Math.Atan2(b.y - a.y, b.x - a.x) * 180 / Math.PI + 450) % 360;
            var p2 = (Math.Atan2(aa.y - a.y, aa.x - a.x) * 180 / Math.PI + 450) % 360;
            var val = p1 - p2;
            return val;
        }
        public override int GetHashCode()
        {
            return b.v;
        }
        public bool Equals(Part other)
        {
            if (other == null) return false;
            return (this.b.v.Equals(other.b.v));
        }
    }

    public class Cal
    {
        long N = 1;
        public void init(long n)
        {
            //N = (n + 1) * 2;
            //vert = new List<List<Part>>();
            vert = new Dictionary<int, List<Part>>();
            for (int i = 0; i < n; i++)
            {
                vert.Add(i, new List<Part>());
            }
            result = new List<List<nd>>();
        }

        public Cal()
        {
        }

        public void setinput(List<Tuple<int, int>> inputs, List<nd> vt)
        {
            points = new List<nd>();
            Dictionary<int, nd> tos = new Dictionary<int, nd>();
            for (int i = 0; i < vt.Count; i++)
            {
                if (tos.Values.Any(p => p.x == vt[i].x && p.y == vt[i].y))
                {
                    var v = tos.Values.FirstOrDefault(p => p.x == vt[i].x && p.y == vt[i].y);
                    tos.Add(vt[i].v, v);
                }
                else
                {
                    tos.Add(vt[i].v, vt[i]);
                    points.Add(vt[i]);
                }
            }
            //points = vt;
            n = points.Count;
            init(n);

            vis = new Dictionary<int, bool>();
            for (int i = 0; i < vt.Count; i++)
            {
                vis.Add(vt[i].v, false);
            }

            for (int i = 0; i < inputs.Count; i++)
            {
                var input = inputs[i];
                var x = tos[input.Item1];
                var y = tos[input.Item2];
                if (x.v == y.v)
                    continue;
                if (!vert.ContainsKey(x.v))
                {
                    vert.Add(x.v, new List<Part>());
                }
                if (!vert.ContainsKey(y.v))
                {
                    vert.Add(y.v, new List<Part>());
                }
                if (vert[x.v].Any(p => p.b.v == y.v))
                    continue;
                if (vert[y.v].Any(p => p.b.v == x.v))
                    continue;
                vert[x.v].Add(new Part()
                {
                    a = x,
                    b = y
                });
                vert[y.v].Add(new Part()
                {
                    a = y,
                    b = x
                });
            }

            for (int i = 0; i < points.Count; i++)
            {
                if (points[i].v == 1441)
                {
                    var xx = 5;
                }
                vert[points[i].v] = vert[points[i].v].OrderBy(p => p.val()).ToList();
                //vert[points[i].v].Sort();
            }
        }

        public void setsubs(List<nd> vt, ref Dictionary<int, List<Part>> verts)
        {
            points = vt;
            //n = points.Count;
            //init(n);
            result = new List<List<nd>>();
            vis = new Dictionary<int, bool>();
            for (int i = 0; i < vt.Count; i++)
            {
                vis.Add(vt[i].v, false);
            }

            this.vert = verts;

            for (int i = 0; i < points.Count; i++)
            {
                //vert[points[i].v].Sort();
                vert[points[i].v] = vert[points[i].v].OrderBy(p => p.val()).ToList();
            }
        }

        long n;
        Dictionary<int, bool> vis;
        List<nd> points;
        List<List<nd>> result;
        List<nd> subs;
        Dictionary<int, List<Part>> vert;

        public int getIndex(ref List<Part> list, int v)
        {
            for (int i = 0; i < list.Count; i++)
            {
                if (list[i].b.v == v)
                    return i;
            }
            return -1;
        }

        public void sub4(int q, int u, int v, ref List<nd> list)
        {
            var op = list.FirstOrDefault(p => p.v == u);
            //var ind = list.Select(p => p.v).ToList().IndexOf(u);
            nd cp = new nd(op.x, op.y, vert.Count, op.v, op.lng, op.lat);
            var oplist = vert[u].ToList();
            var cplist = new List<Part>();
            //var culist = oplist.ToList();
            var lindex = getIndex(ref oplist, q);
            var rindex = getIndex(ref oplist, v);
            //var lindex = oplist.Select(p => p.b.v).ToList().IndexOf(q);
            //var rindex = oplist.Select(p => p.b.v).ToList().IndexOf(v);
            if (lindex < rindex)
                lindex = lindex + vert[u].Count;

            if (lindex > rindex + 1)
            {
                for (int i = rindex + 1; i < lindex; i++)
                {
                    int ii = i % vert[u].Count;
                    var mv = oplist[ii];
                    var index = oplist.Select(p => p.b.v).ToList().IndexOf(mv.b.v);
                    oplist.RemoveAt(index);
                    index = vert[mv.b.v].Select(p => p.b.v).ToList().IndexOf(u);
                    vert[mv.b.v].RemoveAt(index);
                    cplist.Add(new Part() { a = cp, b = mv.b });
                    vert[mv.b.v].Add(new Part() { a = mv.b, b = cp });
                    //vert[mv.b.v].Sort();
                }
                //cplist.Sort();
                vert[u] = oplist;
                vert.Add(vert.Count, cplist);
                points.Add(cp);
                //if (vis[cp.v])
                //    return;
                var ret = resub(cp);
                result.AddRange(ret);
            }
        }

        public void sub3(nd u, nd v, ref List<nd> list)
        {
            nd cp = new nd(u.x, u.y, vert.Count, u.v, u.lng, u.lat);
            var oplist = vert[u.v].ToList();
            var cplist = new List<Part>();
            var mv = v;
            //var index = getIndex(ref vert[u.v], mv.v);
            var index = vert[u.v].Select(p => p.b.v).ToList().IndexOf(mv.v);
            vert[u.v].RemoveAt(index);
            //index = getIndex(ref vert[mv.v], u.v);
            index = vert[mv.v].Select(p => p.b.v).ToList().IndexOf(u.v);
            vert[mv.v].RemoveAt(index);
            cplist.Add(new Part() { a = cp, b = mv });
            vert[mv.v].Add(new Part() { a = mv, b = cp });
            vert.Add(vert.Count, cplist);
            points.Add(cp);
            var ret = resub(cp);
            result.AddRange(ret);
        }

        public void tra(nd u, ref List<nd> subs)
        {
            if (vis[u.v])
            {
                return;
            }
            subs.Add(u);
            vis[u.v] = true;
            for (int i = 0; i < vert[u.v].Count; i++)
            {
                nd v = vert[u.v][i].b;
                tra(v, ref subs);
            }
        }

        public List<List<nd>> resub(nd u)
        {
            subs = new List<nd>();
            vis = new Dictionary<int, bool>();
            for (int i = 0; i < points.Count; i++)
            {
                vis.Add(points[i].v, false);
            }
            tra(u, ref subs);

            Cal cal = new Cal();
            cal.setsubs(subs, ref vert);
            return cal.all().ToList();
        }

        public void find(nd pd, nd ud, ref List<nd> list)
        {
            int p = pd.v;
            int u = ud.v;
            list.Add(ud);
            if (list[0].v == ud.v)
            {
                Dictionary<int, int> circles = new Dictionary<int, int>();
                var cpoints = new List<int>() { 0 };
                for (int i = 1; i < list.Count - 1; i++)
                {
                    var uu = list[i];
                    if (circles.ContainsKey(uu.v))
                    {
                        var skip = circles[uu.v];
                        cpoints.Add(skip);
                        for (int j = skip + 1; j < i; j++)
                        {
                            if (circles.ContainsKey(list[j].v))
                            {
                                circles.Remove(list[j].v);
                            }
                            cpoints.Remove(j);
                        }
                        list.RemoveRange(skip, i - skip);
                        i = i - (i - skip);
                    }
                    else
                    {
                        circles.Add(uu.v, i);
                    }
                }
                if (list.Count > 3)
                {
                    for (int i = 0; i < cpoints.Count; i++)
                    {
                        if (i == 0)
                        {
                            sub4(list[list.Count - 2].v, list[cpoints[i]].v, list[cpoints[i] + 1].v, ref list);
                        }
                        else
                        {
                            sub4(list[cpoints[i] - 1].v, list[cpoints[i]].v, list[cpoints[i] + 1].v, ref list);
                        }
                    }
                }
                else
                {
                    sub3(list[0], list[1], ref list);
                }
                if (list.Count > 3)
                {
                    //if (isok(list))
                    {
                        result.Add(list.ToList());
                    }
                }
                List<int> cnts = list.Select(p => vert[p.v].Count).ToList();
                for (int k = 0; k < list.Count - 1; k++)
                {
                    var jv = list[k];
                    if (cnts[k] <= 2)
                    {
                        for (int j = 0; j < vert[jv.v].Count; j++)
                        {
                            var tv = vert[jv.v][j].b;
                            rm(tv, jv);
                        }
                    }
                    else
                    {
                        break;
                    }
                }
                rm(list[0], list[1]);
                return;
            }
            var index = vert[u].Select(q => q.b.v).ToList().IndexOf(p);
            var v = vert[u][(index - 1 + vert[u].Count) % vert[u].Count].b;
            find(ud, v, ref list);
        }

        public class CompareList : IEqualityComparer<List<nd>>
        {
            public bool Equals([AllowNull] List<nd> x, [AllowNull] List<nd> y)
            {
                var xx = x.Select(p => p.oldv).Distinct().OrderBy(p => p).ToList();
                var yy = y.Select(p => p.oldv).Distinct().OrderBy(p => p).ToList();
                return xx.SequenceEqual(yy);
            }

            public int GetHashCode([DisallowNull] List<nd> obj)
            {
                long hash = 19;
                var list = obj.Select(p => p.oldv).Distinct().OrderBy(p => p).ToList();
                foreach (var foo in list)
                {
                    hash = (hash * 31 + foo) % 100000007;
                }
                return (int)hash;
            }
        }

        public void rm(nd x, nd y)
        {
            int rindex = vert[x.v].Select(p => p.b.v).ToList().IndexOf(y.v);
            if (rindex != -1)
                vert[x.v].RemoveAt(rindex);
            rindex = vert[y.v].Select(p => p.b.v).ToList().IndexOf(x.v);
            if (rindex != -1)
                vert[y.v].RemoveAt(rindex);
        }

        public void rrm(nd u, nd v)
        {
            rm(u, v);
            if (vert[v.v].Count == 1)
            {
                rrm(v, vert[v.v][0].b);
            }
        }
        List<nd> list = new List<nd>();

        public void rrrm(List<nd> pps)
        {
            for (int i = 0; i < pps.Count; i++)
            {
                var u = pps[i];
                if (vert[u.v].Count == 1)
                {
                    rrm(u, vert[u.v][0].b);
                }
            }
        }

        public List<List<nd>> all()
        {
            var pps = points.OrderBy(p => p.x).ThenByDescending(p => p.y).ToList();

            for (int i = 0; i < pps.Count; i++)
            {
                var u = pps[i];
                while (vert[u.v].Count > 0)
                {
                    rrrm(pps);
                    if (vert[u.v].Count > 0)
                    {
                        var v = vert[u.v][0].b;
                        list = new List<nd>() { u };
                        find(u, v, ref list);
                    }
                }
            }
            //result = result.Distinct(new CompareList()).ToList();
            return result;
        }

        const double eps = 1e-8;
        //long dcmp(long x)
        //{
        //    if (x < -eps) return -1;
        //    else return (x > eps) ? 1 : 0;
        //}

        //long dot(nd p0, nd p1, nd p2)
        //{
        //    return (p1.x - p0.x) * (p2.x - p0.x) + (p1.y - p0.y) * (p2.y - p0.y);
        //}

        //long cross(nd p0, nd p1, nd p2)
        //{
        //    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
        //}

        //public void check(List<nd> path, int u, ref List<int> clist)
        //{
        //    if (vis[u] || clist.Distinct().Count() >= 2 || path.Any(p => p.oldv == u))
        //    {
        //        return;
        //    }
        //    vis[u] = true;
        //    for (int i = 0; i < vert[u].Count; i++)
        //    {
        //        int oldv = vert[u][i].b.oldv;
        //        bool at = path.Any(p => p.oldv == oldv);
        //        if (!at)
        //        {
        //            check(path, oldv, ref clist);
        //        }
        //        else
        //        {
        //            clist.Add(oldv);
        //        }
        //    }
        //}

        //public bool isok(List<nd> olist)
        //{
        //    var path = olist;
        //    path = path.ToList().Skip(1).ToList();
        //    bool f = false;
        //    for (int j = 0; j < points.Count; j++)
        //    {
        //        vis = new Dictionary<int, bool>();
        //        for (int i = 0; i < points.Count; i++)
        //        {
        //            vis.Add(points[i].v, false);
        //        }
        //        List<int> clist = new List<int>();
        //        if (pinp(points[j], olist) == 1 && !olist.Any(p => p.v == points[j].v))
        //        {
        //            check(path, points[j].oldv, ref clist);
        //            if (clist.Distinct().Count() >= 2)
        //            {
        //                f = true;
        //                break;
        //            }
        //        }
        //    }
        //    for (int i = 0; i < points.Count; i++)
        //    {
        //        for (int j = 0; j < vert[i].Count; j++)
        //        {
        //            int p1 = vert[i][j].a.v;
        //            int p2 = vert[i][j].b.v;
        //            var at = path.Any(p => p.oldv == p1) && path.Any(p => p.oldv == p2);
        //            var index1 = path.Select(p => p.oldv).ToList().IndexOf(p1);
        //            var index2 = path.Select(p => p.oldv).ToList().IndexOf(p2);
        //            if (at && ((index1 + 1) % path.Count != index2) && ((index2 + 1) % path.Count != index1))
        //            {
        //                f = true;
        //            }
        //        }
        //    }
        //    //for (int j = 0; j < points.Count; j++)   //加不加看是否介意不是环的点和边
        //    //{
        //    //    if (pinp(points[j], result[i]) == 1)
        //    //    {
        //    //        f = true;
        //    //        break;
        //    //    }
        //    //}
        //    return !f;
        //}

        //public List<List<nd>> nopoints(List<List<nd>> result)
        //{
        //    var ret = new List<List<nd>>();
        //    for (int i = 0; i < result.Count; i++)
        //    {
        //        var f = isok(result[i]);
        //        if (f)
        //            ret.Add(result[i]);
        //    }
        //    return ret;
        //}

        //long pinl(nd p0, nd p1, nd p2)
        //{
        //    return dcmp(cross(p0, p1, p2)) == 0 && dcmp(dot(p0, p1, p2)) <= 0 ? 1 : 0;
        //}

        //long pinp(nd cp, List<nd> p)
        //{
        //    long len = p.Count - 1;
        //    int i;
        //    long k, d1, d2, wn = 0;
        //    for (i = 0; i < len; i++)
        //    {
        //        if (pinl(cp, p[i], p[i + 1]) == 1) return 2;
        //        k = dcmp(cross(p[i], p[i + 1], cp));
        //        d1 = dcmp(p[i + 0].y - cp.y);
        //        d2 = dcmp(p[i + 1].y - cp.y);
        //        if (k > 0 && d1 <= 0 && d2 > 0) wn++;
        //        if (k < 0 && d2 <= 0 && d1 > 0) wn--;
        //    }
        //    return wn != 0 ? 1 : 0;
        //}

    }
    class Program
    {
        static void Main(string[] args)
        {
            //var pn = Console.ReadLine();
            //List<nd> vt = new List<nd>()
            //{
            //};
            //for (int i = 0; i < int.Parse(pn); i++)
            //{
            //    var input = Console.ReadLine();
            //    var x = int.Parse(input.Split(‘ ‘)[0]);
            //    var y = int.Parse(input.Split(‘ ‘)[input.Split(‘ ‘).Length - 1]);
            //    vt.Add(new nd(x, y, i, i,x,y));
            //}
            //Console.ReadLine();
            //var pe = Console.ReadLine();
            //List<Tuple<int, int>> inputs = new List<Tuple<int, int>>();
            //for (int i = 0; i < int.Parse(pe); i++)
            //{
            //    var input = Console.ReadLine();
            //    int x = int.Parse(input.Split(‘ ‘)[0]);
            //    int y = int.Parse(input.Split(‘ ‘)[input.Split(‘ ‘).Length - 1]);
            //    inputs.Add(new Tuple<int, int>(x, y));
            //}
            List<nd> vt = new List<nd>() {
            new nd(2,0,0,0),
            new nd(2,2,1,1),
            new nd(1,0,2,2),
            new nd(1,1,3,3),
            new nd(1,2,4,4),
            new nd(0,0,5,5),
            new nd(0,2,6,6)};
            List<Tuple<int, int>> inputs = new List<Tuple<int, int>>() {
            new Tuple<int,int>(0,1),
            new Tuple<int,int>(0,2),
            new Tuple<int,int>(1,4),
            new Tuple<int,int>(2,3),
            new Tuple<int,int>(3,4),
            new Tuple<int,int>(2,5),
            new Tuple<int,int>(4,6),
            new Tuple<int,int>(5,6)};
            //List<nd> vt = new List<nd>() {
            //new nd(0,4,0,0),
            //new nd(4,4,1,1),
            //new nd(4,0,2,2),
            //new nd(0,0,3,3),
            //new nd(1,1,4,4),
            //new nd(3,1,5,5),
            //new nd(2,3,6,6)};
            //List<Tuple<int, int>> inputs = new List<Tuple<int, int>>() {
            //new Tuple<int,int>(0,1),
            //new Tuple<int,int>(1,2),
            //new Tuple<int,int>(2,3),
            //new Tuple<int,int>(3,0),
            //new Tuple<int,int>(3,4),
            //new Tuple<int,int>(4,5),
            //new Tuple<int,int>(4,6),
            //new Tuple<int,int>(5,6)};
            //List<nd> vt = new List<nd>() {
            //new nd(-2,3,0,0),
            //new nd(-1,3,1,1),
            //new nd(-3,2,2,2),
            //new nd(-2,2,3,3),
            //new nd(-1,2,4,4),
            //new nd(0,2,5,5),
            //new nd(-3,1,6,6),
            //new nd(-2,1,7,7),
            //new nd(-1,1,8,8),
            //new nd(0,1,9,9),
            //new nd(-2,0,10,10),
            //new nd(-1,0,11,11),
            //new nd(-2,-1,12,12)};
            //List<Tuple<int, int>> inputs = new List<Tuple<int, int>>() {
            //new Tuple<int,int>(0,1),
            //new Tuple<int,int>(0,3),
            //new Tuple<int,int>(2,3),
            //new Tuple<int,int>(3,4),
            //new Tuple<int,int>(1,4),
            //new Tuple<int,int>(4,5),
            //new Tuple<int,int>(2,6),
            //new Tuple<int,int>(3,7),
            //new Tuple<int,int>(4,8),
            //new Tuple<int,int>(5,9),
            //new Tuple<int,int>(6,7),
            //new Tuple<int,int>(7,8),
            //new Tuple<int,int>(8,9),
            //new Tuple<int,int>(7,10),
            //new Tuple<int,int>(8,11),
            //new Tuple<int,int>(10,11),
            //new Tuple<int,int>(1,3),
            //new Tuple<int,int>(10,12)};
            //List<nd> vt = new List<nd>() {
            //new nd(1,2,0,0),
            //new nd(2,3,1,1),
            //new nd(3,4,2,2),
            //new nd(4,5,3,3),
            //new nd(5,6,4,4),
            //new nd(6,1,5,5),
            //new nd(6,4,6,6),
            //new nd(7,8,7,7),
            //new nd(8,9,8,8),
            //new nd(9,10,9,9)};
            //List<Tuple<int, int>> inputs = new List<Tuple<int, int>>() {
            //new Tuple<int,int>(0,1),
            //new Tuple<int,int>(1,2),
            //new Tuple<int,int>(2,3),
            //new Tuple<int,int>(3,4),
            //new Tuple<int,int>(4,5),
            //new Tuple<int,int>(5,0),
            //new Tuple<int,int>(5,3),
            //new Tuple<int,int>(6,7),
            //new Tuple<int,int>(7,8),
            //new Tuple<int,int>(8,9),
            //new Tuple<int,int>(9,6)};
            //List<nd> vt = new List<nd>() {
            //new nd(1,0,0,0),
            //new nd(1,1,1,1),
            //new nd(0,1,2,2),
            //new nd(0,0,3,3)};
            //List<Tuple<int, int>> inputs = new List<Tuple<int, int>>() {
            //new Tuple<int,int>(0,1),
            //new Tuple<int,int>(1,2),
            //new Tuple<int,int>(2,3),
            //new Tuple<int,int>(3,0)};
            Console.WriteLine();
            Cal cal = new Cal();
            cal.setinput(inputs, vt);
            var result = cal.all();
            //var ret = cal.nopoints(result);
            for (int i = 0; i < result.Count; i++)
            {
                var path = result[i];
                for (int j = 0; j < path.Count; j++)
                {
                    Console.Write(path[j].oldv + " ");
                }
                Console.WriteLine();
            }
        }
    }
}

抓取多边形

原文：https://www.cnblogs.com/HaibaraAi/p/Geometry.html