Получить внешний контур для набора точек

[Вильдар]

Всем привет,
Подскажите пожалуйста какие есть варианты определения внешнего контура по набору точек.
Пример точек показан на картинке.

[Александр Ривилис]

Вообще-то существует множество различных алгоритмов. Например: https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B6%D0%B0%D1%80%D0%B2%D0%B8%D1%81%D0%B0
http://e-maxx.ru/algo/convex_hull_graham

[Вильдар]

Спасибо, попробую реализовать.
Думал есть объект наподобие Extents3d в который можно добавить все точки и получить контур.

[Александр Ривилис]

Думал есть объект наподобие Extents3d в который можно добавить все точки и получить контур.

Нет. Кстати, указанный мной алгоритм даст не тот результат, который нарисован у тебя на картинке. Возможно тебе понадобится какой-то специфический алгоритм. Я вижу, что твой внешний контур прямоугольный, хотя напрашивается совсем другой.

[Привалов Дмитрий]

Подскажите пожалуйста какие есть варианты определения внешнего контура по набору точек.

Я вижу, что твой внешний контур прямоугольный, хотя напрашивается совсем другой.

В свое время смотрел подобные алгоритмы. Алгоритмы обычно находят выпуклую оболочку. Придется вводить дополнительные параметры, например максимального расстояния между точками, или учитывать изменение угла, относительно предыдущего вектора, для построения ожидаемого контура. Плюс визуальный контроль результата.

В Civil 3D для построения контура земной поверхности, операторы выбирают наиболее подходящие параметры, а затем при необходимости вносят коррективы, вручную указывая как должно идти соединение точек на определенных участках, т.к. 100% результата на всех участках не достигнуть.

[Вильдар]

Пока нашел библиотечку https://github.com/NetTopologySuite/NetTopologySuite
получение выпуклой оболочки набора точек:

Код - C# [Выбрать]

1.         using GeoAPI.Geometries;
2.         using NetTopologySuite.Geometries;
3.  
4.         public static List<Point2d> GetContour(List<Point2d> pts)
5.         {
6.             List<Point2d> resVal = new List<Point2d>();
7.             List<Coordinate> coordinates = new List<Coordinate>();
8.             foreach (var P in pts)            
9.                 coordinates.Add(new Coordinate(P.X, P.Y));            
10.             var multiPoint = Geometry.DefaultFactory.CreateMultiPoint(coordinates.ToArray());
11.             multiPoint.Normalize();            
12.             var hullGeom = multiPoint.ConvexHull();
13.             foreach (var c in hullGeom.Coordinates)            
14.                 resVal.Add(new Point2d(c.X, c.Y));            
15.             return resVal;
16.         }

Получается такой контур.
Не очень подходит. (

[Александр Ривилис]

Не очень подходит. (

Вот об этом я и говорил. Этот алгоритм строит выпуклую оболочку.

[Привалов Дмитрий]

Получается такой контур.
Не очень подходит. (

А что вообще планируешь контурить? Это один дом на площадке или оцифровка жилого квартала? А то возможно ты или руководство питаете сверх ожидания от алгоритма...такое тоже бывает).

Для данного случая скорее всего нужно найти точку внешнего контура, например например точку с максимальным Y. Затем обходишь контур по часовой стрелке. Определяешь угол на плоскости первого вектора, а затем определять изменение угла от предыдущего. Изменение угла должно быть только 90, 180, 270, с учетом погрешности.

Убедись что тебе точно нужен подобный не универсальный алгоритм. Как вариант есть готовое решение, подгружаешь точки в Civil 3D, строишь контур поверхности, в цивиле есть инструменты для перестройки контура и ребер, убираешь лишнее, получаешь свой контур.

[Вильдар]

Квартиры ) Стены в виде дин блоков, из которых я беру границы, из границ получаю набор точек, потом по внешним точкам строю полилинию. Нужно получить внешних контур квартиры по стенам.
Мне показалось, что по точкам будет сделать это проще.

[Привалов Дмитрий]

Мне показалось, что по точкам будет сделать это проще.

А на картинках у тебя кажется внешний контур дома. Тогда тебе пришлось бы сначала определить точки внешнего контура, убрать их. и на оставшихся точках строить контур квартиры.
 
Возможно будет проще получить площадные объекты из блоков например область(Region) по контурам блоков, сложить их, в результате должен получится общий площадной объект с внешним и внутренним контуром.

[Владимир Шу]

А если попробовать так:
1. Нарисовать только горизонтальные и вертикальные линии между всеми точками
2. Нарисовать заведомо больший прямоугольный контур вокруг точек и линий
3. Через _boundary получить замкнутую полилинию нужной геометрией.

Извините, вам запрещён просмотр содержимого спойлеров.

....
N. profit

[Алексей (IdeaSoft)]

Я вижу, что твой внешний контур прямоугольный,

Хочу уточнить суть вопроса
1) задача только для прямоугольного контура?
2) или для для произвольного контура набора точек?
И контур нужно соединить по максимально уделенным точкам?
Т.е. обтянуть мнимой веревкой крайние точки так чтобы внутри периметра находились все точки данного набора?

Судя по первой картинке это мне напоминает принцип
"ВАКУУМНОЙ УПАКОВКИ", периметр которой всасывается до крайних точек.

[Александр Ривилис]

И контур нужно соединить по максимально уделенным точкам?
Т.е. обтянуть мнимой веревкой крайние точки так чтобы внутри периметра находились все точки данного набора?

Нет. То, о чем ты говоришь - это получение выпуклого контура. На первой картинке четко видно, что контур невыпуклый.

[Алексей (IdeaSoft)]

Прикрепляю картинку поясняющую предполагаемый результат решения.
с другим набором точек.
На сколько я понял вот такой должен быть результат?

[Александр Ривилис]

На сколько я понял вот такой должен быть результат?

Посмотри внимательно на свою картинку и поймёшь, что результат неоднозначный. Совсем неоднозначный.