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

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

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.