5
$\begingroup$

Given a set of segments, I would like to compute the set of closed polygons inside the convex hull of the set of the end of those segments. The vertices of the polygons are the intersections of the segments. For example, if you draw the 6 lines restricted which equations are: $x=-1$, $x=0$, $x=1$, $y=-1$, $y=0$, $y=1$, I would like the algorithm to output the four unit squares around the origin.The polygons I'm trying to compute

$\endgroup$

migrated from math.stackexchange.com Jul 13 '12 at 4:16

This question came from our site for people studying math at any level and professionals in related fields.

  • $\begingroup$ Are all your closed polygons lattice squares? For examples, the square $[-1,1]\times [-1,1]$ , triangle $(-1,-1), (1,0), (-1,1)$ and a small hexagon around the origin are within your region as well. $\endgroup$ – Ross Millikan Apr 16 '12 at 17:23
  • $\begingroup$ I chose those lines in my question to make a minimalistic example, but there are no restrictions on the coordinates of the ends. I'm looking for the set of non overlapping polygons that we intuitively see. $\endgroup$ – Antoine Apr 16 '12 at 17:34
  • $\begingroup$ I was trying to see if you really are asking how to find all the lattice squares that are within the convex hull. When you talk about all polygons there are an infinite number of those. $\endgroup$ – Ross Millikan Apr 16 '12 at 17:50
  • $\begingroup$ Infinite? Only if you include non-simple (self-intersecting) polygons. $\endgroup$ – JeffE Jul 13 '12 at 15:51
  • $\begingroup$ I will upload a picture a soon as I have 10 reps. For example, with a self-intersecting 5 branch star, I would like to output the central pentagon and the 5 outer triangles. Please help me reformulate the question if you see what I mean. $\endgroup$ – alecail Jul 13 '12 at 16:22
8
$\begingroup$

You're trying to compute something called the arrangement of the line segments. The arrangement is a planar straight-line graph whose vertices are either endpoints or intersection points of line segments. The vertices partition the lines segments into smaller segments, which are the edges of the arrangement. Finally, the vertices and edges partition the plane into several components; these are the faces of the arrangement.

Suppose you are given $n$ line segments, and $k$ pairs of those line segments intersect. (You don't know $k$ in advance.) The intersection points can be computed in $O((n+k)\log n)$ time using the Bentley-Ottmann sweep-line algorithm. (The running time can be reduced to $O(n\log n + I)$ using a more complicated algorithm, where $I\le k$ is the number of intersection points, but the additional effort is probably not worth it.) The algorithm can be modified to report, for each intersection point, which segments intersect at that point. Then it is simply a matter of careful bookkeeping to construct a standard data structure that represents the arrangement.

A few caveats to keep in mind:

  • The faces of the arrangement are not necessarily simple polygons. If the union of the line segments is connected, each bounded face is a weakly simple polygon, but a single edge can be incident to the face no both sides. If the union of the segments is disconnected, then faces can have holes, which are either trees or weakly simple polygons.

  • Most textbook (and Wikipedia) descriptions of the Bentley-Ottmann algorithm assume that the input segments are in general position. In this context, "general position" means that at most two segments intersect at any point; no segment endpoint lies on another segment (in particular, the intersection of two segments is either empty or a single point); and no two endpoints have the same $x$-coordinate. In practice, however, this assumption does not hold. As usual in computational geometry, handling degenerate cases correctly and robustly is the most difficult part of implementing the algorithm. (What does your implementation do when the input contains 42 copies of the segment [(0,0),(1,1)], 17 copies of the segment [(0,0),(2,2)], and 9 copies of the zero-length segment [(1,1),(1,1)]?)

  • For small numbers of segments (at most a few dozen), it's probably faster to use a brute-force $O(n^2)$-time algorithm to compute the intersection points.

$\endgroup$
  • 4
    $\begingroup$ I have found a complete discussion on this topic in the chapter 15 of Algorithmic Geometry by Jean-Daniel Boissonnat (IBSN:9780521565295). $\endgroup$ – alecail Jul 18 '12 at 11:06

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.