Intereting Posts
c # Абстрактный class, реализующий интерфейс Атрибут Outputcache на клиентских компьютерах с частичными страницами, Нужна функция C # для преобразования оттенков серого в черно-белый (monoхромный / 1BPP) TIFF PDF Печать в формате Itextsharp добавляет поля в правой и нижней части страницы при печати настройка файловой системы, так что она создает созданное событие только тогда, когда файл полностью скопирован TcpListener: Как я могу обнаружить разрыв клиента? Сопоставление отношений «многие-ко-многим» с атрибутом в инфраструктуре Entity Framework Разница между GetValue, GetConstantValue и GetRawConstantValue Меньше общих дженериков? Возможное решение для арифметики в C # generics Windows Phone 7 Mango Development Links Как отличить версию компилятора с помощью препроцессорной директивы Как установить положение windows WPF во вторичном дисплее Передача параметров в действие из jsonresult Может ли System.Web использоваться с kernelм ASP.Net с полной структурой? DateTime.ToOADate – Только время

Библиотека выпуклых корпусов

Я новичок в C # и с трудом вычисляет выпуклый корпус. У C # есть какая-то математическая библиотека для этого? Если нет, то, я думаю, мне просто нужно реализовать свои собственные.

MIConvexHullhttps://designengrlab.github.io/MIConvexHull/ – это высокопроизводительная выпуклая реализация корпуса в C #, поддерживающая также выпуклые корпуса с большими размерами. Лицензия LGPL.

Вот 2D-алгоритм с выпуклым корпусом, который я написал с использованием алгоритма Monotone Chain , так называемого алгоритма Андрея.

 public static IListSource ComputeConvexHull(List points, bool sortInPlace = false) { if (!sortInPlace) points = new List(points); points.Sort((a, b) => aX == bX ? aYCompareTo(bY) : aXCompareTo(bX)); // Importantly, DList provides O(1) insertion at beginning and end DList hull = new DList(); int L = 0, U = 0; // size of lower and upper hulls // Builds a hull such that the output polygon starts at the leftmost point. for (int i = points.Count - 1; i >= 0 ; i--) { Point p = points[i], p1; // build lower hull (at end of output list) while (L >= 2 && (p1 = hull.Last).Sub(hull[hull.Count-2]).Cross(p.Sub(p1)) >= 0) { hull.RemoveAt(hull.Count-1); L--; } hull.PushLast(p); L++; // build upper hull (at beginning of output list) while (U >= 2 && (p1 = hull.First).Sub(hull[1]).Cross(p.Sub(p1)) <= 0) { hull.RemoveAt(0); U--; } if (U != 0) // when U=0, share the point added above hull.PushFirst(p); U++; Debug.Assert(U + L == hull.Count + 1); } hull.RemoveAt(hull.Count - 1); return hull; } 

Он полагается на некоторые вещи, которые, как предполагается, существуют, см. В моем сообщении в блоге для подробностей.

Я сравнил многие алгоритмы / реализации Convex Hull со всем предоставленным кодом. Все включено в статью CodeProject .

Сравнительный алгоритм:

  • Монотонные цепи
  • MiConvexHull (триангуляции Делоне и Вороные сетки)
  • Сканирование Грэма
  • Chan
  • Уэлле (мой)

Статьи:

  • 2017-10-13 – Испытательный стенд с алгоритмом / реализациями: быстрый и улучшенный алгоритм 2D-выпуклого корпуса и его реализация в O (n log h)
  • 2014-05-20 – Объясните мой собственный алгоритм: Алгоритм выпуклого корпуса и его реализация в O (n log h)

Ниже представлена ​​транслитерация на C # того же источника Java, что и в ответе Qwertie, но без зависимости от нестандартных classов за пределами classа Point с двойными полями.

 class ConvexHull { public static double cross(Point O, Point A, Point B) { return (AX - OX) * (BY - OY) - (AY - OY) * (BX - OX); } public static List GetConvexHull(List points) { if (points == null) return null; if (points.Count() <= 1) return points; int n = points.Count(), k = 0; List H = new List(new Point[2 * n]); points.Sort((a, b) => aX == bX ? aYCompareTo(bY) : aXCompareTo(bX)); // Build lower hull for (int i = 0; i < n; ++i) { while (k >= 2 && cross(H[k - 2], H[k - 1], points[i]) <= 0) k--; H[k++] = points[i]; } // Build upper hull for (int i = n - 2, t = k + 1; i >= 0; i--) { while (k >= t && cross(H[k - 2], H[k - 1], points[i]) <= 0) k--; H[k++] = points[i]; } return H.Take(k - 1).ToList(); } }