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

[Вильдар]

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

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

Вообще-то существует множество различных алгоритмов. Например: 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)]

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

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

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

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

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

Совсем неоднозначный.

Понятно, что неоднозначно.
Тут нужно у автора темы уточнить. Какова конечная цель задачи.
1) Получение контура с минимальной площадью.
2) Получение контура с максимальной площадью.
Вот фраза из вопроса "внешний контур"
Внешний это какой если решений несколько, то какой выбрать?
Просто получается что первая картинка это частный случай
по которому мне до конца не понятна конечная цель.

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


Пусть лучше автор скинет набор точек из реального проекта.
Со всякими там дуговыми "красотами" и другими архитектурными решениями.

[Вильдар]

Пока по точкам выпуклого контура строю полилинию, при этом в диагональные сегменты добавляю вершину для получения прямоугольных сегментов.
Получается как на картинке. Т.е. в некоторых случаях работает некорректно. пока это устраивает.
Чувствую что, есть простое решение - блоки стен состовляют внешний контур - но найти его не получается.

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

Думаю, что здесь для получения контура нужно работать не с точками, а с линиями (отрезками, если пренебречь дугами).

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

Нужно получить внешний контур квартиры по стенам

Думаю, что здесь для получения контура нужно работать не с точками, а с линиями

Возможно лучше со штриховкой, что-то типа объединить все штриховки в одну общую штриховку или область(Region), и из штриховки/области извлечь контур с максимальной длинной(или контур с максимальной площадью), он и будет внешним.

[Вильдар]

Возможно лучше со штриховкой

Штриховка это результат, то что нужно получить - контур в виде полилинии и штриховку этого контура.

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

Штриховка это результат, то что нужно получить - контур в виде полилинии и штриховку этого контура.

А если из блоков-стен сделать области(Region) их сложить в общий.
Из региона извлечь контура и по ним сделать штриховку?

[Вильдар]

Привалов Дмитрий,
Я не делал никогда регионы, можете какой-нибудь пример кода показать.   
В блоке стены есть полилиния контура стены. Может эти полилинии стен можно как-то использовать.

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

Я не делал никогда регионы, можете какой-нибудь пример кода показать

я тоже не делал. Вроде что-то есть на том форуме ;-)
http://www.caduser.ru/forum/index.php?PAGE_NAME=message&FID=49&TID=37833&MID=213716#message213716

[Вильдар]

Попробовал регионы

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

При разбивке региона получается набор отрезков.
Как получить внешний контур региона? 

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

При разбивке региона получается набор отрезков.
Как получить внешний контур региона?

программно) ищи на форуме http://www.caduser.ru/forum/ или смотри документацию по классу Region

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

Попробую еще разок намекнуть....
http://through-the-interface.typepad.com/through_the_interface/2010/06/tracing-a-boundary-defined-by-autocad-geometry-using-net.html

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

Как получить внешний контур региона? 

Тебя устраивает в этой задаче внешний контур региона? Если нет, то зачем его искать. А если да, то задача получения внешнего контура региона решается при помощи BREP .NET API.

[Вильдар]

Попробую еще разок намекнуть....

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

[Вильдар]

Александр Ривилис,
Внешний контур региона, как на картинке, устраивает.
Посмотрю на BREP, спасибо.

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

Внешний контур региона, как на картинке, устраивает.

Выложи чертеж с этим Region. Мне интересно глянуть что из него можно получить.

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

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

Никто не мешает обвести (программно) нужную квартиру заведомо большей рамкой (прямоугольником) и точку для boundary указать как раз в этом зазоре, между элементами квартиры и заведомо большей границей. Понятно , что из набора объектов полученного таким образом нужно будет убрать прямоугольник заведомо больших границ.

[Вильдар]

Выложи чертеж с этим Region.

Для тестов оставил только разбитые блоки стен. И регион который получается объединением полилиний стен.

[Вильдар]

Boxa.Shu,
Вокруг квартиры тоже могут быть "помехи".
Наверно можно попробовать копировать квартиру в пустое место на чертеже и вычислять контур.
Мне не очень нравится такой способ.
Попробую.

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

Вокруг квартиры тоже могут быть "помехи".

Вот прям клещами вытягивается из Вас информация и условия задачи меняются на глазах...

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

Для тестов оставил только разбитые блоки стен. И регион который получается объединением полилиний стен.

Вроде бы похоже на то, что тебе нужно:

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

1. using System;
2. using Autodesk.AutoCAD.Runtime;
3. using Autodesk.AutoCAD.ApplicationServices;
4. using Autodesk.AutoCAD.DatabaseServices;
5. using Autodesk.AutoCAD.Geometry;
6. using Autodesk.AutoCAD.EditorInput;
7. using Autodesk.AutoCAD.BoundaryRepresentation;
8. using AcBr = Autodesk.AutoCAD.BoundaryRepresentation;
9.  
10. #pragma warning disable 0618
11. // This line is not mandatory, but improves loading performances
12. [assembly: CommandClass(typeof(Rivilis.RegionExtBoundary))]
13.  
14. namespace Rivilis
15. {
16.  
17.   public class RegionExtBoundary
18.   {
19.     [CommandMethod("REB", CommandFlags.Modal)]
20.     public void MyCommand()
21.     {
22.       Document doc = Application.DocumentManager.MdiActiveDocument;
23.       if (doc == null) return;
24.       Editor ed = doc.Editor;
25.       ObjectId curSpaceId = doc.Database.CurrentSpaceId;
26.       PromptEntityOptions prEnt = new PromptEntityOptions("\nВыберите область: ");
27.       prEnt.SetRejectMessage("Это не область");
28.       prEnt.AddAllowedClass(typeof(Region), false);
29.       PromptEntityResult rsEnt = ed.GetEntity(prEnt);
30.       if (rsEnt.Status != PromptStatus.OK) return;
31.       using (Region reg = rsEnt.ObjectId.Open(OpenMode.ForRead) as Region)
32.       {
33.         AcBr.Brep brep = new AcBr.Brep(reg);
34.         int iFaces = 0;
35.         foreach (AcBr.Face face in brep.Faces)
36.         {
37.           iFaces++;
38.           int iLoop = 0;
39.           foreach (AcBr.BoundaryLoop loop in face.Loops)
40.           {
41.             Point3dCollection pts = new Point3dCollection();
42.             ed.WriteMessage("\nКонтур №{0} Тип контура = {1}", iLoop,
43.               (loop.LoopType == LoopType.LoopExterior) ? "Внешний" : "Внутренний");
44.             int iVertex = 0;
45.             foreach (AcBr.Vertex vert in loop.Vertices)
46.             {
47.               ed.WriteMessage("\n\tВершина №{0} CoorLoopType = {1}", iVertex, vert.Point);
48.               if (loop.LoopType == LoopType.LoopExterior) {
49.                 pts.Add(vert.Point);
50.               }
51.               iVertex++;
52.             }
53.             using (BlockTableRecord btr = curSpaceId.Open(OpenMode.ForWrite) as BlockTableRecord)
54.             {
55.               using (Polyline3d p3d = new Polyline3d(Poly3dType.SimplePoly, pts, true))
56.               {
57.                 btr.AppendEntity(p3d);
58.               }
59.             }
60.             iLoop++;
61.           }
62.         }
63.       }
64.     }
65.   }
66. }

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

Вот так это выглядит:

[Вильдар]

Александр Ривилис, Круто, спасибо. Подходит отлично.