python - Create polygons from points representing the corner vertices (ArcGIS)?

I am on ArcGIS 10.3.1. I have a point feature class that represents the corner vertices of the polygons. They are located in a regular grid. The labels represent the OBJECTID. The points can be digitized in a random order with no sequence whatsoever. There are no attributes defined.

What I need to do is to create individual polygons (essentially connecting points with certain nearly located points). If I will be able to connect them as on the figure below, I would create polygons from those lines (ie polygons (17,18,21,22);(18,19,22,23) and so forth). The sequence of vertices in the polygons doesn't matter.

Since those polygons can vary in the shape (can be squares or rectangles with varying side size), I have a hard time finding an algorithm to connect only certain points (in human terms, only horizontally or vertically). Relying on the lat/long is not an option since the points may not lay exactly on the same coordinate lines (ie, may be shifted as below). However, all points in "rows" and "columns" lay on the imaginary line that would go through the edge points of the grid (ie, points 22,23,29 lay on the line that go from 21 to 24).

I am trying to automate the process fully, but if certain steps that don't require much time would be needed to get done manually, it's acceptable. In other words, I am looking for any way to speed up this process.

I use arcpy and Python techniques for finding the 5 nearest points for each points and connect them by creating a new line segment. As you can see, some of the lines created go as diagonals within the rectangles created and should be cleaned up.

Things can get harder when the grid has varying the distance between columns/rows such as on this picture (point 22 gets connected not only to 28, but also to point 27 - outside the rectangle created).

I have looked at Parcel Editor in ArcGIS - couldn't find any option that would let me to create polygons automatically. I have a feeling that finding out the sequence of filtering the lines & resultatnt polygons and re-iterating the output I could get sufficiently good results.

Does anyone have any good tips on how to approach this problem to create polygons from the points representing the corners?

Answer

Let’s try to restore rectangles shown, using corner points (red)

and B.N.Delaunay triangles:

Name triangle edges and calculate their length:

Spatially join triangles to edges:

Sort joined table in descending order using edge length:

Select all non-first occurrences of triangles in joined table

Switch selection and dissolve triangles using longest common edge:

Delete all shapes where point count <> 5. Remaining shapes shown below:

As one can see algorithm won’t work with more than 1 smaller rectangle per bigger. Narrower rows/columns are Ok, thus you are covered.

Note: I used my own scripts to sort table and find ‘duplicates’ because I don’t have advanced license.