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

Question

The next problem is 2D, so some simplifications can be made when you offer answers.

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

Mostly I used Voronoi to create roads. Then I changed some data. Now I need a way to iterate over this data (which are still linear segments, but no longer match Voronoi) and generate “neighborhoods” bordering on “roads”.

I looked at some chart diagrams and shortest paths, but I could not figure it out.

Logically, this can be done by starting from the left edge with one point, finding the path back to this point, using the shortest path with available lines (using only clockwise). Then check this line and delete the data. Then you can repeat the same process and get all such areas.

I tried to implement this, but it didn’t bother me, because I could not figure out how to write C ++ code that could do this. The problem was choosing the line itself counterclockwise from the available lines from a certain point. All the corner-based math, I gave the wrong answers, because the sin / cos method is implemented in C ++.

, - , , , , .

EDIT: , , .

- ( 10 , : P)

( ). , (). , , , , . , , .

!

Answer 1

:

, :

, , "" purple - Voronoi. , P, Q, , PQ. (.. Q P), , P.

"" , , , purple , . .

, , , , .

---

, , , Convex Hull . .

"", . a >

Answer 2

(, , ).

- sin/cos.

:

, . , A (, ). B C.

. , . , , . , , , , . , A B.

, , , , , . .

: sin/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.
  }

. , . , . .

Answer 3

, . , , , .

, "" "". , "" , , . Nils . ""; , "" "" "" "", . ( , , .) , , . , .

If you break a plane, and not a limited area, some segments will be rays; You will also need a special code to connect the rays adjacent when sorting by slope into fake "polygons".

Pseudo-code for a limited 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 answer works

        seg = next
        reversed = (seg.end == endpoint)
    } while start != seg;
    result.addPolygon(polygon)
}