How Neighbor Contiguity Algorithm actually works

I want to identify neighbors based on queen or rook contiguities in a programming language that does not have the feature yet. I know that tools like `spdep`, `pysal`, `geoda`, and ArcGIS all implement this, but how? I cannot find any papers online that describe the process.

Is there a general algorithm for this?

By using the Neighbor Contiguity algorithm, data points are grouped based on their proximity. As you mentioned, it is commonly used in GIS software such as ArcGIS for geographical data analysis.

This is how the algorithm works:

1. The data points are first divided into cells, each representing a small area on the map.

2. Next, the algorithm determines which cell each data point belongs to. It is considered a neighboring cell if it contains more than one data point.

3. A cluster of adjacent data points is created by grouping all data points that are neighbors together.

4. A map showing the relative proximity of data points is then created by repeating this process until all data points are assigned to clusters.

There are several ways you can identify neighbors based on queen or rook contiguities in a programming language that does not have this feature. In one approach, a nested loop would be used to iterate over all elements in the grid or matrix, and then a set of if statements would be used to check whether each element is a neighbor of the current element. Rook contiguities, for example, check whether the current element is in the same row or column as the element being checked. The element being checked is a neighbor if it is.

Another approach would be to use a graph data structure to represent the grid or matrix, and then use graph algorithms to find neighbors based on the rules of queen or rook contiguities. When searching for neighboring nodes in the same row or column as the current node, you could use a breadth-first search algorithm.

In general, the specific approach you choose will be based on the specifics of your implementation and the requirements of your project. However, using a nested loop or a graph data structure and algorithms can both be effective ways.

• bro did you just chat gpt for reputation? Commented Dec 13, 2022 at 19:30
• No, I tried to be helpful with references from here: geodacenter.github.io/workbook/4a_contig_weights/…
– Viv
Commented Dec 13, 2022 at 19:52
• Also more information on how it is used in ArcGIS Pro/ArcMap: pro.arcgis.com/en/pro-app/latest/tool-reference/…
– Viv
Commented Dec 13, 2022 at 20:45
• Contiguity is generally defined as the state of being in contact with or bordering something. Yes, polygons are not points, and your question seeks a general algorithm for NCA, which is a technique for identifying spatial relationships between features (points, lines, or polygons). With points, it works as I mentioned in my answer, while with polygons, it considers the edges or vertices as mentioned in the supporting references shared. I assume you have your answer already, or perhaps you could broaden your question to describe your focused problem.
– Viv
Commented Dec 20, 2022 at 4:38
• I do not have my answer. There is no such concept of contiguity for points given that points are infinitesimally small and do no have sides or vertices—contiguous points would be identical points. The answer gives the feeling of authoritative answer but lacks any actual substance. Commented Dec 20, 2022 at 14:20