| Message |
A similar question appeared on the ArcView-L list on 8/21/01, Aaron. The solution I suggested works well, so I have included my response below. That question only wanted to create a polygon with right angles to match a given polygon (in effect, "square it up"); you in effect already have those right angles but you want to reduce their number. To do that, calculate the lengths of the sides of the resulting polygon and subtract a multiple of the sum of their squares from the objective function: this penalizes solutions with lots of little edges. I haven't tested this modification, but it looks promising.
I have found in practice that constraints (1) and (2) are helpful and can be satisfied. However, you might want to omit constraint (3) below.
Here is the solution to the "squaring up" problem:
Many people have solved problems like this: it can be viewed as a constrained optimization problem. When formulated correctly, it's computationally pretty simple and there exists a lot of software for solving it.
The idea is to move the polygon's vertices as little as possible while reducing the deviations between its most visible angles and the desired right angles. You can add constraints to fix the polygon's size, position, and orientation if you like.
The building's outline is a sequence of n >= 3 2D points (z0, z1, ..., z(n-1)). To make notation simple, define z(n) = z0, z(n+1) = z1, z(-1) = z(n-1), and z(-2) = z(n-2). The vector v(i) from point i-1 to point i is always z(i) - z(i-1) (-1 <= i <= n+1). The dot product of vectors v(i) and v(i+1), which I will call m(i), is zero exactly when the angle at z(i) is a right angle (-1 <= i <= n). Thus the minimum possible value of m(i)^2 is attained only when the angle at z(i) is a right angle.
Define S to be the sum (over i=0, ..., n-1) of m(i)^2. This sum will be at a minimum of zero exactly when all corners are "squared up." Consequently, "squaring up" a polygon is equivalent to modifying its coordinates in a way that finds a local minimum of S.
Intuitively, because the angles contributing to S are weighted by the lengths of their adjacent sides, S does the right thing by emphasizing the angles formed by major sides of the polygon and de-emphasizing little bumps or "jaggies" that can result from raster-to-vector conversion.
Technically, using the squares of the m(i) makes the problem convex and differentiable, which means you have a good hope of getting nice solutions with most optimization algorithms.
The constraints are imposed by the need to retain the polygon's position and size and to make all sides parallel to the coordinate axes. Otherwise, as soon as you find a local minimum of S, you can find a four-dimensional continuum of minima simply by translating, rescaling, or rotating the minimum you found.
I would propose representing these constraints as follows:
(1) Require the solution to have the same centroid as the original polygon.
(2) Require the solution to have the same area as the original polygon.
(3) Require one side of the solution to be parallel to a coordinate axis.
(The third constraint can readily be incorporated in the objective function by adding a term for the minimum angle between any fixed polygon edge and the coordinate axes.)
The really nice thing about the objective function S is that it and its derivatives are easy and fast to compute. For instance, writing z(i) = (x(i), y(i)), you can compute that the derivative of S with respect to x(i) (0 <= i <= n-1) is
(-m(i-1), m(i-1) + m(i), -2*m(i), m(i) + m(i+1), -m(i+1)) * transpose(x(i-2), x(i-1), x(i), x(i+1), x(i+2))
(this is a matrix multiplication), with a comparable expression for the derivative with respect to y(i).
There will still often be a large continuum of optimal solutions. Consider adding to S a small multiple of the mean squared distance that vertices are moved. This will help you find a minimum-distance solution among all optimal solutions. It also tends to create a global optimum to which most starting solutions converge, which makes the solution very stable. Indeed, using this trick you can probably drop constraints (1) and (2), because they will be approximately satisfied anyway.
Alternatively, you could formulate S=0 as a constraint and minimize the distance the vertices are moved. This would be solved by first finding a solution of S=0 and then minimizing distances subject to maintaining that constraint.
This is enough information to solve the problem efficiently with existing computer packages. ... [Discussion of Avenue coding omitted.]
As a proof of concept, I dropped some simple randomly-jittered building outlines into Excel, set up formulas for S and the constraints, and used Excel's Solver add-in to square up the outlines. It worked nicely in all the formulations discussed above (use S as an objective, use S + multiple of distance as an objective, or use S = 0 as a constraint and distance as an objective). |