2
$\begingroup$

Suppose we have random lines made with 2 points. and point has (x,y)

For example:

this is sample image which i am looking for

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.

$\endgroup$
  • 1
    $\begingroup$ Please share your approach to the problem. This is not a site for solving your homework. Also try to post questions about the algorithm underlying a question, instead of solutions in specific languages. $\endgroup$ – Sagnik Apr 19 '18 at 9:49
  • 1
    $\begingroup$ Hi i am looking for how to do. it's step. or how can i do it looking for suggestion. i think i should add little more what i am trying. $\endgroup$ – Amrit Apr 19 '18 at 10:20
  • 1
    $\begingroup$ When you say line, do you mean a line segment? It seems segments are used in your picture. Also, do you want to find the 'bounding points' for all regions at once, or only for a single specified region? $\endgroup$ – Discrete lizard Apr 19 '18 at 11:21
  • 1
    $\begingroup$ @Sagnik A pair of points is also probably the most natural way of specifying a line. However, the diagram seems to make it clear that they're line segments. $\endgroup$ – David Richerby Apr 19 '18 at 11:53
  • 1
    $\begingroup$ Hi, Yes they are Line Segment, made with 2 points. and i would like to find it all at once. $\endgroup$ – Amrit Apr 19 '18 at 13:26
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.