Как создавать закрытые зоны (выпуклые многоугольники) от набора сегментов линии? -- c++ поле с участием graph поле с участием geometry поле с участием polygon пол Связанный проблема

How to create closed areas (convex polygons) from set of line segments?


3
vote

проблема

русский

Следующая проблема находится в 2D, поэтому некоторые упрощения могут быть сделаны при предложении ответов.

Мне нужно создать закрытые области (определены либо по линиям отрезки или просто набор точек - выпуклый многоугольник) из набора точек / линейных сегментов.

в основном я использовал Вороной для генерации «дороги». Затем я изменил некоторые данные. Сейчас мне нужен путь, чтобы пройти петлю через эти данные (которые все еще строки сегменты, но не соответствуют Voronoi больше), а генерирует «неигбурственные», которые граничат с «дороги».

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

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

Я пытался реализовать это, но он не получил мне где угодно, так как я не мог понять способ написать код C ++, который мог сделать это. Проблема была с выбором самой линии против часовой стрелки от имеющихся линий из определенной точки. Весь угла математика, которую я сделал неправильные ответы, потому что в C ++ реализован так, как Sin / Cos реализуются в C ++.

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

Редактировать: добавлена ​​картинка, чтобы проиллюстрировать то, что я хочу сделать.

Проверьте изображение здесь - (нужно 10 репутаций, прежде чем я смогу опубликовать его здесь: P)

ALT TEXT

.

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

Спасибо за вашу помощь!

Английский оригинал

The following problem is in 2D, so some simplifications can be made when suggesting answers.

I need to create closed areas (defined either by line segments or just set of points - convex polygon) from a set of points/line segments.

Basically I used Voronoi to generate "roads". Then I changed some of the data. Now I need a way to loop through that data (which is still line segments but doesn't comply with Voronoi anymore) and generate "neigbourhoods" that are bordered with the "roads".

I looked at some graph diagrams and shortest path theories, but I could not figure it out.

Logically it could be done by starting at left edge from one point, finding the way back to that point using the shortest path with available lines (using only clockwise directions). Then mark this line set down and remove from the data. Then you can repeat the same process and get all the areas like that.

I tried to implement that but it did not get me anywhere as I could not figure out a way to write a C++ code that could do that. Problem was with choosing the most counterclockwise line from available lines from a specific point. All angle based math I did gave wrong answers because the way sin/cos are implemented in c++.

So to summarize - if you can help me with a totally new approach to the problem its good, if not could you help me find a way to write the part of the code that finds the shortest clockwise path back to the beginning point using the line segment set as paths back.

EDIT: Added a picture to illustrate what I want to do.

Check the image here - (need 10 reputations before I can post it here :P)

alt text

I have a set of points (purple small dots). Another array defines what points make up a line (road). I want a way to define the area that is surrounded by roads so I can put buildings or smaller roads inside that and test against the edges so every region is separated. Hope this gives you more info on how to solve this problem.

Thank you for your help!

</div
           
     
     

Список ответов

1
 
vote

Бадовка на ваш разъяснение:

Возможно, вы можете попробовать это:

У вас, вероятно, уже есть список «соседних» очков для любого данного Purple синей точки из-за вороной. Теперь дал фиолетовый точку P, с соседом Q, вы можете рассмотреть дорогу, которая пересекает сегмент линии PQ. Все такие дороги (то есть варьируются q среди соседей P), вероятно, сформируют замкнутый регион вокруг с.

Даже если у вас не было «соседней» информации, вы, вероятно, можете попробовать все возможные пары черных точек Purple и увидеть, какие сегменты линии пересекаются ровно одной дорогой. Для данного момента набор таких дорог сформирует замкнутую область вокруг него.

Это может быть не оптимально, но, вероятно, работает, хотя я не пытался его доказать.


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

Если вы хотите, чтобы «Области» не пересекают «зоны», вы можете попробовать найти разделительную линию и запустить выпуклый корпус отдельно.

 

Basded on your clarification:

Perhaps you can try this:

You probably already have a list of 'neighbouring' points for any given purple blue point because of the Voronoi. Now given a purple point P, with a neighbour Q, you can consider the road which intersects line segment PQ. All such roads (i.e. vary Q among the neighbours of P) will likely form the closed region around P.

Even if you didn't have the 'neighbour' information, you can probably try all possible pairs of purple blue points and see which line segments are intersected by exactly one road. For a given point, the set of such roads will form a closed region around it.

This might not be optimal, but probably works, though I haven't tried proving it.


Sorry your question is not really clear, but I presume Convex Hull will come in handy. You can use the endpoints of a segment when calculating the hull.

If you want mutiple disjoint 'areas' you could try finding a separating line and running convex hull separately.

</div
 
 
         
         
0
 
vote

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

, и вы можете найти эту строку без звонок Sin / COS.

Идея идет так:

Предположим, что у вас есть две строки на выбор. Позвоните в точку, где линии соответствуют A (например, ваша текущая позиция). Конечные точки ваших двух строк называются B и C.

Эти три точки строят треугольник. Теперь посмотрите, как ориентированы три очка. Если вы следите за точками от A до B до C, направление будет либо по часовой стрелке или против часовой стрелки. Очевидно, что приказ по часовой стрелке, линия, которая идет от A до C, будет больше всего по часовой стрелке. В противном случае это линия, которая идет от A до b.

Если у вас есть более двух строк, чтобы выбрать только для выбора первых двух, отбросьте строку, которая попадает в неправильное направление и выполнит тот же тест, пока не заканчиваете одну линию. Это самый часовой стрелки.

Сейчас о математике: как вы узнаете обмоток на три точки, не вызывая греха / COS или даже хуже: Atan:

Вы можете сделать это с поперечным продуктом. Сначала постройте двух векторов, которые дают вам направление от A до B и от A до C:

 <код>    u.x = B.x - A.x    u.y = B.y - A.y     v.x = C.x - A.x    v.y = C.y - A.y   

Теперь мы можем рассчитать подписанную область параллелограммы, порожденной этими двумя векторами:

 <код>    signed_area = (u.x * v.y) - (u.y * v.x);   

Обмотка - это знак области. например.

 <код>   if (signed_area > 0)   {       // order is clockwise. Pick Line B   }   else if (signed_area < 0)   {       // order is counter-clockwise. Pick Line A   }   else    {     // the lines are colinear.   }   

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

 

Your idea to follow the line segments along the shortest path (e.g. follow the most clockwise one if you have multiple choices) is good.

And you can find this line without any sin/cos calls.

The idea goes like this:

Assume that you have two lines to choose from. Call the point where the lines meet A (e.g. your current position). The endpoints of your two lines are called B and C.

These three points build a triangle. Now take a look how the three points are oriented. If you follow the points from A to B to C the direction will either be clockwise or counter-clockwise. Obviously if the order is clockwise, the line that goes from A to C will be the most clockwise one. Otherwise it's the line that goes from A to B.

If you have more than two lines to choose from just pick the first two, discard the line that goes into the wrong direction and do the same test until you end up with a single line. That's the most clockwise one.

Now about the math: how do you find out the winding-order of three points without calling sin/cos or even worse: atan:

You can do this with the cross product. First build two vectors that give you the direction from A to B and from A to C:

   u.x = B.x - A.x    u.y = B.y - A.y     v.x = C.x - A.x    v.y = C.y - A.y 

Now we can calculate the signed area of the parallelogram spawned by these two vectors:

   signed_area = (u.x * v.y) - (u.y * v.x); 

The winding is the sign of the area. e.g.

  if (signed_area > 0)   {       // order is clockwise. Pick Line B   }   else if (signed_area < 0)   {       // order is counter-clockwise. Pick Line A   }   else    {     // the lines are colinear.   } 

Note: I haven't tied the code and the decision on the sign could be exactly the other way around. That's a detail of the math that I will never get into my head. I always have to try it out with known data.

</div
 
 
   
   
0
 
vote

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

вместо этого у вас должно быть два флага для каждого сегмента, для того, вы построили ли вы многоугольник к «левому» и «правильному» сегменте. Если у вас есть граничная зона, сегменты границы должны иметь свой «внешний» боковой флаг, чтобы начать с тех пор, как вы не хотите использовать эту сторону в многоугольнике. Затем найдите сегменты с флагом unset, и используйте ответ Nils, чтобы работать вокруг полигона. Некоторые сегменты будут «изменены»; Если вы собираетесь по часовой стрелке, вы хотите установить флаг «левый» на сегментах «вперед» и «правый» флаг на «обратно», и наоборот. (Вы можете строить все многоугольники в одном заказе, он просто не имеет значения, который вы выберете.) Обратите внимание, что первый сегмент может быть интерпретирован как либо в зависимости от того, какой из его флагов вам нужно установить. Когда все сегменты помечены в обоих направлениях, вы закончите.

Если вы разбиваете самолет, а не ограниченную область, некоторые сегменты будут лучами; Вам также понадобится какой-то специальный код для подключения лучей, которые соседствуют при сортировке по склону к поддельным «многоугольникам».

псевдокод для ограниченный корпус:

 <код> foreach seg in boundary segments {     if left of seg is outside region {          seg.leftDone = true     } else {          seg.rightDone = true     } } while any seg.leftDone or seg.rightDone is false {     seg = pick a segment with either flag unset     start = seg     polygon = new Polygon()     reversed = not start.rightDone     do {         if reversed {             seg.rightDone = true             endpoint = seg.start             polygon.addSegment(seg.reverse())         } else {             seg.leftDone = true             endpoint = seg.end             polygon.addSegment(seg)         }          next = findNextClockwiseSeg(seg, endpoint); // Nils's answer works          seg = next         reversed = (seg.end == endpoint)     } while start != seg;     result.addPolygon(polygon) }   
 

It sounds like you want to partition the some region into non-overlapping convex polygons. If I'm understanding you correctly, you can't just toss segments after using them to form a polygon, because each internal segment will border on two polygons.

Instead, you should have two flags for each segment, for whether you have built a polygon to the segment's "left" and "right". If you have a bordered area, the border segments need to have their "outer" side flag set to start with since you don't want to use that side in a polygon. Then find segments with either flag unset, and use Nils's answer to work your way around the polygon. Some segments will be "reversed"; if you're going clockwise, you want to set the 'left' flag on the 'forward' segments and the 'right' flag on the 'backward' ones, and vice versa. (You can build all the polygons in one order, it just doesn't matter which you choose.) Note that the first segment can be interpreted as either depending on which of its flags you need to set. When all segments are flagged in both directions, you are done.

If you're partitioning the plane rather than a bounded region, some segments will be rays; you'll also need some special code to connect rays that are adjacent when sorted by slope into fake "polygons".

Pseudocode for the bounded case:

foreach seg in boundary segments {     if left of seg is outside region {          seg.leftDone = true     } else {          seg.rightDone = true     } } while any seg.leftDone or seg.rightDone is false {     seg = pick a segment with either flag unset     start = seg     polygon = new Polygon()     reversed = not start.rightDone     do {         if reversed {             seg.rightDone = true             endpoint = seg.start             polygon.addSegment(seg.reverse())         } else {             seg.leftDone = true             endpoint = seg.end             polygon.addSegment(seg)         }          next = findNextClockwiseSeg(seg, endpoint); // Nils's answer works          seg = next         reversed = (seg.end == endpoint)     } while start != seg;     result.addPolygon(polygon) } 
</div
 
 
       
       

Связанный проблема

0  Libusb_Bulk_Transfer добавляет CRC?  ( Does libusb bulk transfer add crc ) 
Я пишу программу пользовательского интерфейса для устройства USB в C ++, используя Visual Studio 2019. Я использую библиотеку Libusb. Я хочу сделать объемную ...

501  Как использовать постоянную PI в C ++  ( How to use the pi constant in c ) 
Я хочу использовать постоянные и тригонометрические функции PI в некоторой программе C ++. Я получаю тригонометрические функции с помощью <код> include <math....

-4  Петля, которая компилирует и работает в INT основной функции не скомпилируется при введении в отдельную функцию [закрыто]  ( Loop that compiles and runs in int main function wont compile when put into a se ) 
<в сторону CLASS = "S-NEWACTS S-WELTIVE__info JS-Post-New Imide MB16« Роль = «Статус»> закрыто. Этот вопрос нуждается в Детали отладки . В настоящее вр...

57  Как сделать макрос C ++ вести себя как функция?  ( How do i make a c macro behave like a function ) 
Допустим, по какой-то причине вам нужно написать макрос: <код> MACRO(X,Y) . (давайте предположим, что есть веская причина, по которой вы не можете использова...

1  Шаблон статических классов через динамические связанные библиотеки  ( Template static classes across dynamic linked libraries ) 
У меня есть классовый класс со статическим значением, как это: <код> template <class TYPE> class A{ static TYPE value; }; в коде dll I назначаю ст...

-1  Бросить исключение, когда неправильный тип введен в  ( Throw exception when a wrong type is keyed in ) 
Я должен написать программу C ++, в которой функция состоит в том, чтобы прочитать два номера double Тип чисел из клавиатуры и добавить <код> try BLOCK, чт...

2  Создание хеша для данных больше, чем память (без зарядки)  ( Generating a hash for data larger than memory without getting arrested ) 
Добрый послеобеденный переполнец! ;) Что я хочу сделать: Я заинтересован в проверке передаваемой целостности файлов. Как я подошел к нему: Я рассм...

0  Как настроить VS2008 для эффективного развития C ++  ( How to setup vs2008 for efficient c development ) 
Обычно I Программируйте в C #, но были вынуждены выполнять работу в C ++. Похоже, что интеграция с Visual Studio (2008) действительно плохо по сравнению с C #...

0  Правильный способ использования вариационного шаблона функции вызова со строковыми аргументами C ++  ( Proper way of using variadic template function call with string arguments c ) 
Здравствуйте, что не то, что я здесь делаю, используя вариадические шаблоны через строку? Как правильно использовать его для достижения заданий ниже? <код> ...

-1  C ++ DO В то время как проблемы с петлей [закрыто]  ( C do while loop issues ) 
<в сторону CLASS = "S-NEWACTS S-WELTIVE__info JS-Post-New Imide MB16« Роль = «Статус»> <Путь d = "M15 6.38A6.48 6.48 0 007.78. 04H-.02A6.49 6.49 0 002.05 ...

1  Почему 64-битное целое расширение C ++ называется «долгим долгом»?  ( Why is the 64bit integer extension of c called long long ) 
В отличие от других типов: «int», "логический", "двойной" и т. Д. И даже таможенные классы, есть только одно слово. Однако только одно слово для их типа тольк...

-1  Приложение C ++ в массивах с использованием арифметического указателя  ( C app on arrays using pointer arithmetic ) 
Вопрос: как я могу генерировать случайное животное из массива, используя эту функцию? <код> const int MAX =12; //12 animals const int MAXSTR = 10; ...

-1  Неожиданный идентификатор ошибки - не уверен, почему (C ++)  ( Unexpected error id not sure why c ) 
IM Реализация программы C ++, по соображениям проекта оно должно быть включено в один файл, поэтому я не могу поставить то, что вы обычно в отдельном файле за...

6  Singleton & Multi-Threading  ( Singleton multi threading ) 
У меня есть следующий класс <код> class Singleton { private: static Singleton *p_inst; Singleton(); public: static Singleton * instance()...

5  Что такое "для (x: y)"?  ( What is for x y ) 
Итак, я оглянулся на межпубки о нитках, и я пришел в блог / учебную вещь о нитках, но то, что меня смущено, была эта линия, которую он использовал <код> for...

Связанный проблема

0  Libusb_Bulk_Transfer добавляет CRC? 
501  Как использовать постоянную PI в C ++ 
-4  Петля, которая компилирует и работает в INT основной функции не скомпилируется при введении в отдельную функцию [закрыто] 
57  Как сделать макрос C ++ вести себя как функция? 
1  Шаблон статических классов через динамические связанные библиотеки 
-1  Бросить исключение, когда неправильный тип введен в 
2  Создание хеша для данных больше, чем память (без зарядки) 
0  Как настроить VS2008 для эффективного развития C ++ 
0  Правильный способ использования вариационного шаблона функции вызова со строковыми аргументами C ++ 
-1  C ++ DO В то время как проблемы с петлей [закрыто] 
1  Почему 64-битное целое расширение C ++ называется «долгим долгом»? 
-1  Приложение C ++ в массивах с использованием арифметического указателя 
-1  Неожиданный идентификатор ошибки - не уверен, почему (C ++) 
6  Singleton & Multi-Threading 
5  Что такое "для (x: y)"?