determine if a region of space is empty

Question

I have a region of space, 2 dimensions, from (0,0) to (MAX_X, MAX_Y).

Inside this region of space, I draw some lines, they intersect the perimeter of the region and they may intersect one another. In this way, these lines partition my region of space in subregions which, if summed, give the entire region of space.

Inside this region of space, there are some points (x,y). I have to determine

1. the coordinates of all the vertices composing all the subregions of space created by the lines
2. if a given subregion of space contains or not one or more of the points

I'm trying to code this in java, but the language is not really important. I don't have any idea about how to accomplish these two tasks. If anybody can give me an hint I'd really appreciate it.

Answer 1

This is a rather difficult problem of computational geometry. A possible approach could be to represent the resulting regions by a planar subdivision of the original rectangle. The subdivison would be represented by doubly connected edge list (DCEL). This consists of a list of directed half-edges, a list of regions (faces) and a list of vertexes (intersections of the lines). All these data are completely inerconnected, such that finding any data given some other data is very efficient.

The DCEL would be built iteratively, starting with one region which is the original rectangle and adding one line after another. Adding a line means to cut the current DCEL by this line and to obtain a more refined DCEL.

When the final DCEL is constructed, it can be used for finding and marking regions that contain a point. Testing whether a point is in a region can be done efficienly because the regions are convex polygons.

A good book on DCEL is M. de Berg, et.al.: Computational Geometry. You can also find many resources on the Web. You will also find implementations and various software packages.

Answer 2

That is indeed quite a math question. Thinking about the problem I assume that the solution will be quite complicated and/or expensive (computation-wise).

You start with a list R of subregions, starting with one element: the whole region. Next you loop over your list of lines. For every line you loop every R. If the line intersects the Region you divide it into two. Help on the line-area intersection check should be easily available on the net. Just look for intersections between a line and a convex area. The problem with this algorithm is that it will have a runtime of about O(n^3). O(n) for n lines times O(n) for the areas times O(n) for the intersection checks (however you might be able to speed that last part up significantly, bringing you down to O(n^2) in the end).

Checking which of your areas contains a specific point is classical problem of convex analysis. There should be algorithms available for that. I guess what you will be wanting to do is loop over your lines and check if your point is "left or right" of that line. If you link your subregions to your lines in the first step, this will give you the appropriate subregion in O(n).

The first problem can be solved considerably quicker with a more sophisticated algorithm and, like I said, the one I explained could be sped up significantly.

Basically if you want more information on the subject you are looking at convex analysis.

However, if all that doesn't help you at all, you are probably in over your head (no offense intended, you are handling really complicated math here).