next »

[celloe]

I have a set of a few line segments (or equally lines / rays, as they're clipped against the bounds of the window) contained within a box, at various angles in 2D. My aim is to find all the open regions created by those lines and treat them as polygons, and see which region has the largest area. This is proving pretty difficult..



My initial idea was to take the line intersections as essentially a point cloud and do some form of triangulation, but of course it's not dealing with triangles! So the polygonisation could only act along the line segments themselves. Is there any way to do this so I could generate a bunch of polygons sharing edges, and depending on where the user clicks it calculates whether it was in the largest area or not?

[BleakProspects]

Lucky for you, what you have here is called a convex decomposition of the space (assuming the segments get cut off at the boundaries). Because of this you may treat each region as an intersection of half-spaces. This is very nice, because it allows you to test any point to see which area it belongs to with one subtraction and a dot product per line. Basically, what you want to compute is which "side" any point belongs to.

So you have a point somewhere

X = (x_0, y_0)

within the bounds that you want to test. For each line segment L_k, find its center

C_k = (x_k, y_k).

Compute its normal

N_k = (n_kx, y_kx).

If you have an angle representation of the lines, each line's normal is simply

(cos(theta_k + 0.5 * pi), sin(theta_k + 0.5 * pi)),

where theta_k is the angle of the line.

For each line segment, transform X such that it is represented relative to the line segment's center. i.e.,

(X_t = X - C_k = (x_0 - x_k, y_0 - y_k)).

Now, the test is simply given by the dot product of this transformed point and the normal of the segment:

d_k = dot(X_t, N_k);

If d is positive, the point X lies on the "left" side of the line. Otherwise, it lies on the "right" side of the line. If d is zero, the point X lies exactly on the line segment. Each area is then a special intersection of these half-spaces.

For instance, for area 1:
d_0 > 0
d_1 > 0

For area 2
d_0 < 0
d_1 > 0

For area 3
d_0 > 0
d_1 < 0

For area 5
d_1 < 0
d_0 < 0


As for converting them into polygons, you can do this too. Underneath, your collision checker will just use the convex test I just described to determine whether they lie in a specific area anyway. To convert into polygons, just take the intersection points of each of the lines, and the vertices which make up the edges of the bounds, and link them as a polygon.



Edit: Oh, you wanted to find the *biggest* area, not whether a particular point lies within an area. In that case you will just need to convert them to polygons. It's not particularly difficult. You just need to know which corner of the box belongs to which area (as I've listed above), and then compute the intersections of each line segment with each edge of the box.

[Gimym JIMBERT]

Looks like a graph problem, you have point (node) and segment (edge) and you want to find space that aren't split by another edge ...

edit:
Ninjaed by bleakprospect

[BorisTheBrave]

I doubt you're going to find a way more efficient than the obvious "constuct a BSP then find largest polygon". There's good docs online about making BSPs.

[celloe]

@BleakProspects Wow, thank you for the in-depth reply! My idea is that I would convert the line segments into a list of polygons, then iterate through them calculating each one's area to find the largest. However this is proving difficult - your idea would work, but I'm not sure of the best approach in the case of lines creating polygons not met by a border:



Instead of using a boundary line, would I use a 3rd line's intersection? It gets complicated here..

@BorisTheBrave Interesting idea, I'm wholly unfamiliar with BSP trees though and researching yields a lot of abstract stuff that I can't quite figure out. Is there an explanation of it that you know of geared to solving these types of problems? It seems to be a lot to do with 3D rendering and collision detection.

Thanks for the help so far guys!

[ralphchapin]

I'd try something like this.  You'll need some classes--Line, Intersection, Segment, and Area.  You'll want 3 lists, one for Lines, one for Intersections, and one for Areas.  Each Intersection will have a four-element list of Segments and and a two element list of Lines each.  Also, you're going to need to ID each intersection by x and y coordinates, and you're going to need to find these things by ID.  That is, you're going to need to do a keyed search.  (Be careful with reals.  You might want to convert them to integers if you can avoid two points ending up with the same ID.)

The Area list will need to be keyed also, to prevent adding duplicates to it.

Start with all your lines in the Lines list.  And add the top, bottom, and sides of the window to the list as four extra lines.

Next generate Intersections by comparing every combination of two lines.  If they intersect outside the window forget about them.  Otherwise, add them to the Intersection list.  Fill the Intersections' Line list at this time.

You can probably fill each segment element at this time too.  Each line may give many intersections with other lines.  Keep the shortest two for each of the two intersection lines that go in different directions.  Note that each segment must be added to the next intersection along the line also.  The segment from Intersection 5 to Intersection 8 must also be the segment from Intersection 8 to 5.

Now you have a nice graph.  Pick an Intersection.  Pick one of the four segments.  Follow that path, turning left (or right, but be consistent!) at each intersection you arrive at.  When you get back to the one you've started at, you've marked off one area.  You can uniquely identify it by using it's Intersection list as its identifier.  Use the highest Intersection you passed through as the first in the ID.  I think most times one Inter will provide a unique ID, but you might need 2 sometimes.  I don't think you'll need 3.  (If more than one is highest, pick the one farthest to the left.)

So for each Intersection, can get the four Areas it's associated with.  Add them to the Area list, which should reject duplicates.

Now you have a list of unique, non-overlapping Areas, and can find their defining intersections easily.  Do what you want from there.

I haven't tried this, and it may not work, but I think the best answer will look something like this (if it isn't something really clever).  At any rate, this should get you started.

[BorisTheBrave]

Ok, I guess you need a bit more explanation.

Simple algo:

First off, write a function that splits a convex polygon by an arbitrary line. This can be done very simply with one iteration over the points of the polygon. It returns one or two polygons, depending on if there was a successful split.

Then start with a list of size one containing the starting square. For each intersecting line, split every polygon by it, and put the results together into the next list to be processed.

Finally, pick the largest polygon in the list.

Code:

l = [starting_square]
for line in intersecting_lines:
    new_list = []
    for poly in l:
      new_list.extend(split_poly(poly, line))
    l = new_list

# Find max in list:
max_poly = max(l, key=poly_area)

Advanced algo (using BSPs):
The former will run really slowly if you have a lot of intersecting lines. To avoid this, we construct a tree as we go. Each node has a polygon associated with it and two or zero children. We ensure that the polygons of the children are a complete partition of of their parent.

Start with the tree of one node, the starting square, then split the entire tree by each intersecting line. It is quicker to split the tree than the original list, because we can skip many leaf nodes at once if their common ancestor doesn't intersect with the line.

Code:

def split_polygon(polygon, line):
    # 2 polygons if split,
    # Otherwise, returns None and the original polygon,
    # In an order indicating which side of the line the polygon is on
    ...

def make_node(poly, child_a, child_b):
    if child_a is not None:
        if child_b is not None:
            return Node(poly, child_a, child_b)
        else:
            return child_a
    else:
        if child_b is not None:
            return child_b
        else:
            assert False

def split_tree(node, line):
    # 2 nodes if split,
    # Otherwise, returns None and the original nodes ,
    # In an order indicating which side of the line the polygon is on
    poly1, poly2 = split_polygon(node.poly, line)
    if poly1 is None:
        return None,node
    if poly2 is None:
        return node, None
    if node.is_leaf
        return Node(poly1), Node(poly2)

    node1_a, node2_a = split_tree(node.child_a)
    node1_b, node2_b = split_tree(node.child_b)
    node1 = make_node(poly1, node1_a, node1_b)
    node2 = make_node(poly2, node2_a, node2_b)
    return node1, node2

tree = Node(starting_square)
for line in intersection_lines:
    node1, node2 = split_tree(tree, line)
    tree = make_node(tree.poly, node1, node2)

# Find max in tree:
def find_max(node):
    if node.is_leaf:
        return node.poly
    poly_a = find_max(node.child_a)
    poly_b = find_max(node.child_b)
    return max(poly_a, poly_b, key=poly_area) 

max_poly = find_max(tree)