Finding the boundary polygon from a set of gridded points (no hole)

Question

Let us consider a set of a 2-D points (longitude, latitude) each of which is centre of square grid (intersect point of the diagonals of the square).

I try to make you understand what I want to do in a graphical manner.

Sample data (point set):

lon<-c(88.56630, 88.62501, 88.60013, 88.57499, 88.65879, 88.63392, 88.60879)


lat<- c(21.03517, 21.01287, 21.05434, 21.09610, 21.03207, 21.07354, 21.11531)

Plots:

Figure 1: First one is the scatter plot of the point set.

Figure 2: All the points are bilinear (this is known).

Figure 3: Each point is centre of a square of size (approx.) 4km by 4km (we need construct those squares from the given centre point).

Figure 4: This is what I want to have, The polygon obtained by the outer sides of the squares (black lines).

Note: I have lots of point sets of arbitrary shapes like the above sample with maximum cardinality of the sets as 100.

How can this get this polygon (no hole)?

Answer 1

I generated points using lines with 4000m spacing in one direction and 4050m in another direction. Pseudo-code to process:

1. Create TIN using any field. Get triangles and edges from TIN using TIN edge and TIN triangle:

2. Sort edges in descending order, sort field shape_length. Calculate their midpoints, shown in red, labelled by OBJECTID:

3. Iterate through points and select triangles, using selected points. Break when number of selected triangles=2

4. Union (arcpy geometry, not a tool) of this 2 triangles is rectangular shape to multiply. You have to create a copy of rectangle, so that it's centre coincides with every next point. It involves moving (no rotation) of the shape, i.e. changing coordinates of all 5 points, using difference in coordinates of target point and rectangle's centroid.

Yes, you have to code this. Of course points to be projected and grouped first.

Answer 2

I was able to achieve the following, using the buffer and Minimum Bounding Geometry (extracting the envelope of the buffers) then some manual intervention with the rotate tool. You can then do a final dissolve to return a single polygon. You give no indication how of many of these you need to resolve, a few like your screen shot or hundreds of thousands?

If manual intervention is not an option then you need to rotate the envelope for each. I do not know of a geoprocessing tool that can do this and to my knowledge rotating geometries not exposed to arcpy. If you know a little bit of VBA you could knock up a simple script to do this using the interface ITransform2D.