# 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)?

• In your quote is "centre of a square of size (approx.)"- could you clarify the word "approx"- and/or attach some sample data.. Commented Jan 27, 2015 at 12:05
• @msi_g Thanks for your attention. The data given in \$(lat,lon)\$ variable are the real data. These are satellite data. They claim that the distance between two points is 4 km but we can check that the geodesic distance between two points not exactly 4km but little less or more. Commented Jan 27, 2015 at 12:15

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.

• Wouldn't midpoints #20, 19, 9, etc select two triangles that don't form a square though? Commented Jan 28, 2015 at 1:06
• 20 and 19 - not a concern, they are down the descending list. With 9 O-OOPS! Should of include the step of TIN delineation, i.e. removing long edges. Commented Jan 28, 2015 at 1:23
• I see. Pretty cool way to go about it. Commented Jan 28, 2015 at 2:14
• In my post I kept coding in mind. With small set shown there is much easier way to go. Create rectangle using 4 points, move it (center will snap to point), copy-paste etc Commented Jan 28, 2015 at 2:25
• @FelixIP Thank you very much for your attention and effort. The suggested idea of getting the polygon is very interesting and I am trying to coding it. Commented Jan 29, 2015 at 4:28

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.

• Thanks for your attention and a answer. You are right in pointing that I may have a point set with great variety of cardinality. I added this point as a note in the original question. Also,the manual intervention is not an option. I am not familiar with VBA. Could you please guide me to do this rotation part in VBA or could you please provide me the necessary code. Thanks for your time and consideration. Commented Jan 27, 2015 at 18:16