Strategies in finding a rectilinear polygon within a polygon in GIS

What is a Rectilinear polygon?

A rectilinear polygon, according to Wikipedia, is a polygon all of whose edge intersections are at right angles. Thus the interior angle at each vertex is either 90° or 270°.

Use case for a Rectilinear polygon

The use case is for the user to beautify the shape of a polygon for procedural modelling as designing architecture is much easier using a regular-shaped land parcel. In my previous article, I explored similar outcome by finding the largest rectangle within a convex polygon. If that interests you, you can read the article here.

Rules for the algorithm

1. Form a rectilinear polygon without adding additional points.
2. Rectilinear polygon must be within the original polygon
3. As it is done using GIS, the inaccuracy of the angle should be at most 1% away from 90°/270°

Greedy Algorithm

Stage 1: Expanding Options Stage

1. Loop through the points to determine the state of each point based on its angle. Angles (270° < x < 360°) will need the help of its neighbor to make it 90°/270°.
2. Expand on the possible options to make by determining whether the point or one of it’s neighbor should move to make the current corner become 90°/270°.

Stage 2: Execution Stage

1. Based on the possible options explored in stage 1, loop through the points and move points and its dependencies.

Strategies

1. Move along the lines

For angles that are 0° < x < 90°, we could shift the point along both of its lines until it form 90°. This can move the point while not affecting its’ neighbor’s angle by shifting along line connecting to it. Please see the images below for illustration.

Moving along the top line until it forms a right-angle

Moving along the left joint line can also make it right-angle

2. Two-stage movement

In stage 1 —Expanding Options, some points will be marked to assist its neighbor to make them 90°/270°. After the algorithm has determined the dependency sequence, the dependee can perform a double move to first make its dependent 90°/270°, followed by itself. However, it may not always be possible for the point to make the second movement . In such case, the algorithm will assign its following point as its dependee.

The first movement is made by finding the 3rd point in a right-angle triangle, A, B and angle of corner A. Extend this line and try to intersect with the next line in the polygon. If an intersection can be found, we can move the dependent to the intersection. Next, we try to move along this line which will keep the dependee’s angle while making itself 90°/270°. This may not always be possible and when this happens, the algorithm will conclude its action and make its other neighbor the dependee. Please see the images below for illustration.

Form a right angle using dependent, dependee and the angle to make dependent a rectilinear angle (90°/270°). Extend the line until it touches the next polygon line.

In cases it does not touch the next polygon line, move the point to the right angle triangle instead.

Results

I have tested my on several simple land parcel. Green polygon is the input and red polygon is the output. Results so far looks reasonable.

Looks correct.

Looks legit.

Seems correct

Looks correct

Not the largest rectilinear possible. There is gap on the right that can be extended.

This looks almost like a rectilinear but 1 corner does not meet criteria.

This is incorrect. 3 points were skipped to obtain this.

Conclusion

I have tested the algorithm on several existing land parcel. You can find its results below. I can think of a few scenario which the algorithm definitely will fail. As most land parcels are likely to in regular shape so as to attract developers, this simple method should work most of the time.