1

If you were given a set of pairs of lines, how would you find the amount of area which is contained by all pairs of lines (if it exists)? For example, if I had the pairs of lines:

((0, 0), (0, 10)) & ((10, 0), (10, 10))

and

((0, 0), (10, 0)) & ((0, 10), (10, 10))

how would you go about finding the area enclosed by all those lines (which in this simple case would be a square defined by points (0,0),(10,0),(10,10) & (0,10).

What algorithms might point me in the direction of solving such a problem?

EDIT: The lines won't always touch at the ends or intersect with each other. If there exists a pair of lines which doesn't intersect any of the other lines and doesn't touch at the edges, then it can be concluded that that set of pairs of lines does not have an area enclosed by all of them.

EDIT2:Take the following sets of lines:

pair 1: ((0, 0), (10, 0)) & ((0, 10), (10, 10))

pair 2: ((0, 0), (0, 10)) & ((10, 0), (10, 10))

pair 3: ((2, 0), (2, 10)) & ((8, 0),(8, 10))

The enclosed area by those three pairs of lines is the area defined by points (2,0),(2,10),(8,10) and (8,0). The convex hull algorithm however would return the values (0,0),(10,0),(10,10) and (0,10).

user3002473
  • 4,835
  • 8
  • 35
  • 61
  • Do you know that the line segments will always be joined end-to-end (if joined), or might they intersect (cross) each other? – Ann L. Jan 02 '14 at 05:19
  • They can intersect each other all they want. I was thinking that maybe if I iterated through each line top-to-bottom and continually added the checked lines to a list of lines in which any other points must be to the left/right of, until it narrows it down, but then arises the problem of how you determine whether or not you check to see if a point is to the right or left of a line. – user3002473 Jan 02 '14 at 05:25
  • What is the significace of the "pairs" of lines, besides that there is an even number of lines? For example, are the lines in a pair always parallel as in your example? – M Oehm Jan 02 '14 at 18:21
  • You should really add a picture, or I will charge you for the paper and ink required to follow your examples :) – kuroi neko Jan 03 '14 at 05:01

2 Answers2

1

EDIT: it appears the convex hull is not the solution.

Just to make sure I understand your problem: is that the red area in this picture that you want? enter image description here

kuroi neko
  • 8,479
  • 1
  • 19
  • 43
  • I have posted a working example [here](http://stackoverflow.com/questions/2122305/convex-hull-of-4-points) if you're still interested – kuroi neko Jan 03 '14 at 01:21
  • This is not necessarily true that the convex hull is always the area covered by all line segments. (See EDIT2 in my answer for details) – user3002473 Jan 03 '14 at 03:51
  • Ah well, your question is a bit ambiguous. Do you mean you want the *intersection* of all the (infinite) surfaces enclosed by your pairs of lines, then? – kuroi neko Jan 03 '14 at 05:05
0

Find all points of intersection which stay within the line segment for all pairs of lines. If no of points are less than 4 then no enclosed shape found.

If 4 points found then clip the lines with those points.Use flood fill to get the area of figure enclosed in the points.

Vikram Bhat
  • 6,106
  • 3
  • 20
  • 19