[GIS] Looking for a region growing algorithm

arcobjects

I work with a raster set representing land values and I would like to automatically create polygons with random shape but with certain size and/or land value given a centroid point of each polygon. The centroid point will act as the initial raster cell (a pixel called as a seed cell) that will belong in that certain polygon and then a region growing algorithm will begin adding pixels around a centroid pixel until the constraint of size and/or land value of a polygon will be satisfied.

Is anybody who has any idea about an existing region growing algorithm? or at least which is the class of ArcObjects or Interfaces that I may work with, so as to read the value of each pixel, create a new polygon by adding new pixel to it?

I hope that the above make sense and somebody may help me.

Edit

Basically I intend to automatically create polygons with regular shapes and a series of constraints such as size, land value etc. using a genetic algorithm (GA). But first I need to create a set of random solutions in order to feed the GA.So, for instance on land block which is an area enclosed by roads I have already saying 4 centroid points. Each centroid point represents the approximate location of each new land parcel. In addition, each centroid is associated with attributes of each parcel i.e. size and land value. So, I want to begin by each centroid as a seed point of the region growing algorithm to starting creating a random shape for each parcel based on each centroid.

I hope that the above make sense. I look forward how can I create this region growing algorithm or if there is already one in VBA and ArcObjects.

Best Answer

A cost distance analysis is one approach: classify the raster based on land value starting from the seed point, then thresholding that result will give you the cumulative cost area as a raster. Just translate that classified raster into a polygon, and you should get your result. Depending on the specifics of what you're trying to do, you may be able to get away with using the Cost Allocation function with your seed locations and land value raster to achieve your desired output.

Related Solutions

[GIS] Creating a new layer from query results

The AO-API has got an example. This would mean that you would have to extent your code by the following lines:

IFeatureDataset featureDataset = featureWorkspace.OpenFeatureQuery("MyJoin", queryDef);
IFeatureClassContainer featureClassContainer = (IFeatureClassContainer)featureDataset;
IFeatureClass featureClass = featureClassContainer.get_ClassByName("MyJoin");

And just assign that feture class to a feature layer. Assuming you really want to create a new shapefile in the filesystem, you can export the created feature class with a geoprocessor like FeatureClassToShapefile.

ArcGIS 10 – Create Weighted Thiessen Polygons with VBA and VB.NET

There are many ways to weight distances for constructing Thiessen polygons. The basic idea in constructing them is based on comparing the distance between an arbitrary point x and two fixed points p and q; you need to decide whether x is "closer" to p than to q or not. To this end--at least conceptually--we consider the distances dp = d(x, p) and dq= d(x, q). The weighting usually occurs in two ways: the points can be given positive numeric weights wp and wq and the distances themselves can be transformed.

To make sense, the transformation (which I will write as f) should increase as the distances increase; that is, f(d') > f(d) whenever d' > d >= 0. Examples of such transformations are f(d) = d+1, f(d) = d^2 (Reilly's Law of Retail Gravitation), f(d) = 1 - 1/d (assuming all distances are less than 1), f(d) = log(d), f(d) = exp(d)-1.

We would then say x is "closer" to p than to q exactly when

f(d(x, p)) / wp < f(d(x, q)) / wq.

Notice the division by the weights, rather than multiplication: this means large weights will tend to "pull in" points at larger distances. You will see this in the running example below.

Here's the beautiful thing, and the whole point of this somewhat abstract exposition: although the resulting Thiessen regions can have complex, extremely difficult to calculate boundaries, they are relatively easy to compute using a grid-based representation. Here's the recipe:

For each input point p, compute its Euclidean distance grid [d(p)].
Use Map Algebra to apply f and the weights, thereby re-expressing each distance grid as

[fp] = f([d(p)]) / wp.

Here is an example using f(d) = 100 + d^(3/2); the scale is 400 by 600.

As f(d) increases the value gets darker. Evidently the distance in this example is with respect to the central red point; the other four points get their separate distance calculations (not shown). The areas of the dots are proportional to their weights, which are 2, 10, 3, 4, and 5.
Compute the local minimum of all these grids [fp]. Call this [f]. Here is an example.
By comparing [f] to each [fp], to each grid cell assign the identifier of the first p for which [f] >= [fp]. (This can be done in one step with a lowest position operation, for instance.)

(I doubt there exists an algorithm anywhere that will compute a vector-format solution for this weighting function f.)

Obviously if you have more than a handful of points p you will script this, and if their number runs into thousands you will probably abandon the attempt as being computationally impracticable (although there are ways to expedite the calculation by tiling it).

Another example, showing Thiessen polygons on an ellipsoid, appears at https://gis.stackexchange.com/a/17377/.

Edit

Best Answer

Related Solutions

[GIS] Creating a new layer from query results

ArcGIS 10 – Create Weighted Thiessen Polygons with VBA and VB.NET

Related Question