Wednesday, February 12, 2014

Placing Point Models into Parcels

Part 1 - Aligning Points to Transportation

Imagine that you have a finite but bounded number of polygons.  Each polygon represents an area that can be occupied by a building.  What you would like to do is automatically place a point within each of these polygons that would completely define the location and orientation of a specific building model.  The selected building model must fit completely within the provided region.  The polygons below are reasonable examples of these polygon regions:

These polygons will have irregular shapes; some of them will be pointed, rounded or elongated.  If we need to place a point in these geometries, where should it be placed?  The first-place one would attempt to place a point is at the polygons "center".  Unfortunately, the definition of center is not always clear; consider the example geometry below:

Simply summing the x and y values of this geometry and then averaging will result in a point that is positioned in the upper-left hand corner.  This is due to the geometries point density in this area.  Naturally, we would expect our point to be placed somewhere towards the center of the whole-geometry, as observed in the example below:

This is more along the lines of what we would expect.  If we were to place a 3D model in-and-around this point, we would have lots of wiggle room.  Unfortunately, a position like this is not always guaranteed to exist, as is the case with many concave geometries.  This topic will be discussed in a future posting.  For now, let's consider a large area that contains many of these simple cases:

If we wish to assign building models to these points, we will need to know which way they should face.  After all, it would be nice if our building models were facing the street.  Lets consider some examples and see if we can come up with a generalized approach for selecting an orientation angle.

Let's start our analysis by making some general observations of the input:

  1. More than one valid orientation may exist for each area of interest
  2. If an orientation can not be established by examining an individual area, we could use neighboring areas to make a good guess.

The most trivial approach to point orientation can be realized by aligning a point to the nearest transportation feature.  This is a poor choice for most cases but it is reasonably trivial to implement and worth some discussion.  I have roughly 400k areas in my test data set and it takes a minute to generate these sample points and orient them to the roads.  The screenshot below illustrates the types of anomalies that are produced when you align to the closest point on the transportation feature.

It should be noted that we are not aligning to an existing vertex on the geometry but rather to the closest point (which may or may not be an existing vertex).  Notice how most of the orientation segments are not centered within the areas.  We may (or may not) prefer for these angles to be chosen in a way that preserves the relative straightness within the surrounding area.

We can see how the results may vary with this approach when more than one orientation exists.  The screenshot below highlights some of the obvious complexities.

This method does not provide a general purpose solution but it does illustrate most of the fundamental issues that are involved with choosing an orientation for building model placement.  In part 2, I will discuss how to improve the alignment of the orientation segment and greatly simplify the resulting model fitting process.  Below are some screenshots of different sample areas.

Sample 1
Large area, generally acceptable results

Sample 2
Generally acceptable results

Sample 3
The closest vert is not always where you think it is...

Sample 4
What do we do when multiple solutions exist?

No comments: