Suppose we have random lines made with 2 points. and point has (x,y)
For example:
Now when we draw a random line you will see many lines intersect with each other. This eventually gives rise to bounded regions. How to find the vertex points for each bounded region?
My approach: First we find all the intersection points of the various lines. In some cases multiple lines intersect at the same point.
However I am not sure how to pick the points that make up a bounded region.
Thanks in Advance.
Finding the all the vertices for all of the bounding regions is roughly the same amount of work as creating a doubly connected edge list (DCEL) that represents your regions, so I will show how to construct a DCEL from a set of line segments. After that, finding all the boundary points for each region from a DCEL is a simple operation.
First, we find all line segment intersections between the segments we start with. This can be done efficiently with the standard sweepline algorithm for line segment intersection, which is described in various references, such as in these slides. This can be done in $O(n\log n + K)$ time, where $n$ is the number of line segments and $K$ the number of intersections between these lines.
For the next part, we construct a set of endpoints $P$ and a set of line segments $L$, where for each segment $l\in L$, we also store the pair of points $(p,q)$ from $P$ that are the endpoints of segment $l$. First, add all original line segments to $l$ and the corresponding endpoints to $P$.
Then, at every intersection point $p$, split the segments that intersect at that point into two segments 'separated' by $p$, store the point $p$ in the set $P$, remove the old segment from $L$ and add the new segments to $L$, setting their endpoints accordingly.
In the end, we have represented our regions with a graph $G=(P,L)$, where the vertex set $P$ are all points in our 2D space (including the intersection points) and the set of edges $L$ contains all segments connecting these points. Note that the graph $G$ doesn't have any crossing edges by construction, so it is planar.
From this planar graph, we can construct a DCEL, as shown in this answer, which is mostly bookkeeping.
In the DCEL, each region is associated with a representative half-edge. From that half-edge, we can find all half-edges that form the border of the region. Then, the vertices of the region are all vertices of those half-edges.
It is possible to skip the DCEL and find the vertices directly, but likely you need to do almost the same thing. The main advantage of using a DCEL as an intermediate step is that someone else already has made an algorithm to construct a DCEL.
