You are here: > ESRI Forums > arcgis desktop discussion forums > Thread Replies

ArcGIS Desktop Discussion Forums

ArcGIS Desktop - Data Editing forum

Editing buildings, squaring edges   aaron reyna Mar 18, 2010
Re: Editing buildings, squaring edges   William Huber Mar 19, 2010
Re: Editing buildings, squaring edges   aaron reyna Mar 19, 2010
Report Inappropriate Content • Top • Print • This Forum is closed for replies.    
Subject Editing buildings, squaring edges 
Author aaron reyna 
Date Mar 18, 2010 
Message Hi Everyone,

I have a polygon that was created from a 1-foot cell raster. The polygon represents a building.

What I would like to do is find a way to square up the edges to 90 degree angles while straightening the individual line segments. I've tried generalization, but with less than adequate results (typically it removes points, which is what I want to avoid). Ideally, the centroid and area would stay the same.

Here is the process as I see it in my mind:

Step 1. Identify contiguous edges, with a start point and an end point per line segment. Feed that to an array.

step 2. Calculate the best fit for that array, and draw that line.

Step 3. From a 90 degree angle, process the next contiguous line segment in that polygon until all line segments in that polygon are processed.

Step 4. Process the next polygon

If anyone has any ideas, or some script that does something sort of similar, it would be greatly appreciated. I have code to iterate through all polygons and change them to Minimum Bounding Rectangles, but I'd actually like to preserve area, centroid, and general shape of the polygon.

attached you will find a jpg of the unedited polygon and an idea of a desired outcome for the polygon I wish to create.

Thanks so much!

aaron
GIS Analyst
Watershed Sciences, Inc. 
  square_up_a_poly.JPG (opens in new window)
 
Report Inappropriate Content • Top • Print • This Forum is closed for replies.    
Subject Re: Editing buildings, squaring edges 
Author William Huber 
Date Mar 19, 2010 
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). 
  --Bill Huber
Quantitative Decisions (http://www.quantdec.com )
More GIS Q&A at http://gis.stackexchange.com/q/3083/664 
   
Report Inappropriate Content • Top • Print • This Forum is closed for replies.    
Subject Re: Editing buildings, squaring edges 
Author aaron reyna 
Date Mar 19, 2010 
Message Great!

Thanks Bill! I appreciate it. Your methodology makes sense, especially the constraints. I'm going to try and write out a prog to do this, so I'll keep you posted on how it comes out. Thanks again!

aaron