Checking the validity of a rectilinear shape

Question

Given a rectilinear shape, how do I efficiently check if it is valid and point out the part that is not valid?

The validity here means a width constraint, i.e., each part of the shape should have a width no less than some value d. Formally, if you sweep a line vertically from top to bottom of the shape, all the intersections between the line and the shape should have length no less than d. The vertical situation is similar. (Note that there may be holes inside the shape. But for simplicity, we can ignore that first.)

Can anyone suggest an efficient algorithm or show me some pointer to this problem?

Answer 1

I think you can attack this with a fairly typical scan-line approach.

Consider the horizontal scan-line first, sweeping from the top of the figure to the bottom. Observe that the width crossed by the scan-line can only change as it passes across the endpoint of a vertical segment.

So for the horizontal scan-line, you can ignore horizontal segments. Take all of the endpoints of the vertical segments and sort them by their vertical location. (Each endpoint knows whether it is the "top" endpoint or the "bottom" endpoint of its segment).

Process that sorted list in order to simulate the scan line. Maintain an "active set" S, initialized to empty. When you hit a "top" endpoint, add its segment to S. When you hit a "bottom" endpoint, remove its segment from S. Verify that the width of the active set meets your constraint at all times, and you are done.

Use a balanced binary tree (like a C++ std::set) to represent the active set, using the horizontal position for the comparison function. This allows O(1) retrieval of the leftmost and rightmost segment in the set, so the width calculation is O(1). It also allows O(log n) insertion and removal, and since you insert and remove each vertical segment exactly once, the entire sweep takes O(n log n).

Repeat symmetrically for the vertical scan-line.

Each sort is O(n log n), each scan is O(n log n), times two for each orientation... So the overall algorithm is O(n log n).

Answer 2

Here's a kind of brute force method that's about O(n^2).

First check to see if there are any self crossings. A crossing in a polygon has a width of 0, so it fails automatically.

There are two parts to the rest of the solution, depending on if your constraint is really only horizontal and vertical or if it's any angle. For either case, start by iterating every point of the polygon.

If the constraint is horizontal/vertical, check each segment of the polygon to see if it intersects a line drawn through x or y of the point. If it intersects, calculate the distance from the intersection to the point; if it's less than the constraint, you have a failure.

If the constraint is any angle, check each segment of the polygon that is not adjacent to the point and calculate the closest distance from the segment to the point; you might get come help from this question Shortest distance between a point and a line segment. If the distance is less than the constraint, you have a failure.