<jupyter_start><jupyter_text>Marching SquaresMarching Squares is a computer graphics algorithm that computes contours for a 2D scalar field, that is, a rectangular array of individual numerical values (“Marching squares”, 2019). It can be used to generate the contours of a kernel density map (Lu et al., 2020). Material- [Wikipedia page](https://en.wikipedia.org/wiki/Marching_squares) (“Marching squares”, 2019).- ["Isosurfaces: Geometry, Topology, and Algorithms" book](http://web.cse.ohio-state.edu/~wenger.4/publications/) (Wenger, 2013). - [*scikit-image* (or *skimage*) library](https://scikit-image.org/) (van der Walt et al., 2014).- [`skimage.measure.find_contours` function](https://scikit-image.org/docs/stable/api/skimage.measure.htmlfind-contours) (van der Walt et al., 2014). ReferencesWikipedia contributors. (2019, December 30). Marching squares. In *Wikipedia, The Free Encyclopedia*.Retrieved 12:13, February 26, 2020, from https://en.wikipedia.org/w/index.php?title=Marching_squares&oldid=933213691<NAME>., <NAME>., <NAME>., <NAME>., <NAME>., <NAME>., & <NAME>. (2020). Winglets: Visualizing Association with Uncertainty in Multi-class Scatterplots. *IEEE Transactions on Visualization and Computer Graphics, 26*(1), 770–779. https://doi.org/10.1109/TVCG.2019.2934811<NAME>. (2013).*Isosurfaces*. New York: A K Peters/CRC Press.https://doi.org/10.1201/b15025van der Walt, S., <NAME>.L., <NAME>., <NAME>., <NAME>., <NAME>., <NAME>., <NAME>., & scikit-image contributors. (2014).scikit-image: image processing in Python. *PeerJ, 2*, e453.https://doi.org/10.7717/peerj.453<jupyter_code>import numpy as np
from skimage import measure
import matplotlib.pyplot as plt
print(f"NumPy: {np.__version__}")
# Generate dummy data (an image).

a = np.zeros((10, 10))

a[1, 8] = 1

for r in range(1,5):
    for c in range(1,5):
        if (r != 4 or c != 4):
            a[r, c] = 1
            a[r + 4, c + 4] = 1

# L-R = same y, different x.
# T-B = same x, different y.
a
# The origin in the graphs below is in the bottom-left corner,
# instead of the top-left corner as usual for images:
# https://matplotlib.org/api/_as_gen/matplotlib.pyplot.imshow.html

# This option for the origin was made so that the axes are ordered
# in the same way as is usual for a scatterplot, for example.

np.flip(a, axis=0) # Flip the image vertically.
# Find contours at a constant value of 0.50.

THRESHOLD = 0.50 # a.k.a. isovalue
contours = measure.find_contours(a, THRESHOLD)

# contours
x = [value for value in range(0, len(a))] * len(a)

# x
y = [item for sublist in [[value] * len(a) for value in range(0, len(a))] for item in sublist]

# y
a_flat = a.flatten()

# a_flat
clrs = ['green' if (x <= THRESHOLD) else 'none' for x in a_flat]

# clrs
# Display the image.

fig, ax = plt.subplots(figsize=(10, 10))
ax.imshow(a, cmap=plt.cm.gray_r, origin="lower")
plt.show()
# Display the image and the binary index.

# The filled points are below the threshold.
# The unfilled points are above the threshold.

fig, ax = plt.subplots(figsize=(10, 10))
ax.imshow(a, cmap=plt.cm.gray_r, origin="lower")

plt.scatter(x, y, c=clrs, edgecolors="green")

plt.show()
# Display the image, the binary index, and the contours.

# Every 2x2 block of pixels (or dots) forms a cell. 
# Marching Squares generates a contour line for each cell 
# according to the following lookup table:
# https://en.wikipedia.org/wiki/Marching_squares#Basic_algorithm

fig, ax = plt.subplots(figsize=(10, 10))
ax.imshow(a, cmap=plt.cm.gray_r, origin="lower")

plt.scatter(x, y, c=clrs, edgecolors="green")

for n, contour in enumerate(contours):
    print(f"Coordinates (contour {n + 1})\nx: {contour[:, 1]}\ny: {contour[:, 0]}\n")
    ax.plot(contour[:, 1], contour[:, 0], linewidth=2, zorder=1)
    
plt.show()<jupyter_output><empty_output><jupyter_text>Linear InterpolationConsidering, for example, the cell in the bottom-left corner, the exact position of the contour line (more specifically, the beginning and the end of the contour line) along the edges of this cell was computed with the following (abbreviated) algorithm (Wenger, 2013):**Input**: - Two points or vertices of a cell (*p* and *q*).- The scalar values associated with the aforementioned points according to the dataset or image (*sp* and *sq*).- The threshold or isovalue (*t*).- **Note**: The coordinates of the points can be checked on the graph axes.    **Output**:- A point lying on [*p*, *q*] (*r*).- **Note**: This point will correspond to the beginning or end of a contour line. **Linear interpolation algorithm**:```pythondef linear_interpolation(p, sp, q, sq, t):    alpha = (t - sp) / (sq - sp)    dimensions = len(p)        r = np.zeros(dimensions)        for d in range(dimensions):        r[d] = (1 - alpha) * p[d] + alpha * q[d]            return(r)```<jupyter_code>def linear_interpolation(p, sp, q, sq, t, verbose=True):
    
    assert (sp != sq), "This algorithm requires sp != sq."
    assert ((t >= sp and t <= sq) or (t <= sp and t >= sq)), "This algorithm requires sp <= t <= sq or sp >= t >= sq."
    assert (len(p) == len(q)), "Both points must have the same dimension."
    
    alpha = (t - sp) / (sq - sp)
    dimensions = len(p)
    
    r = np.zeros(dimensions)
    
    for d in range(dimensions):
        r[d] = (1 - alpha) * p[d] + alpha * q[d]
    
    if(verbose):
        print(f"Coordinates:\nx = {r[0]}\ny = {r[1]}")
    
    return(r)
# Considering, for example, the points or vertices (0, 1) and (1, 1):

p =  np.array([0, 1])
q =  np.array([1, 1])

sp = a[tuple(p)]
sq = a[tuple(q)]

print(f"p: {p}\nq: {q}\nsp: {sp}\nsq: {sq}")
r = linear_interpolation(p, sp, q, sq, THRESHOLD)
# Display the image, the binary index, the contours,
# and a linearly interpolated point (red dot).

fig, ax = plt.subplots(figsize=(10, 10))
ax.imshow(a, cmap=plt.cm.gray_r, origin="lower")

plt.scatter(x, y, c=clrs, edgecolors="green")

for n, contour in enumerate(contours):
    print(f"Coordinates (contour {n + 1})\nx: {contour[:, 1]}\ny: {contour[:, 0]}\n")
    ax.plot(contour[:, 1], contour[:, 0], linewidth=2, zorder=1)
    
plt.scatter(r[0], r[1], c="red", edgecolors="red", zorder=2)

plt.show()
# The choice of the threshold or isovalue is important. 
# This value affects linear interpolation and can yield less accurate contours.

# Check the warning in the notes:
# https://scikit-image.org/docs/dev/api/skimage.measure.html#find-contours

THRESHOLD_2 = 0.25
contours_2 = measure.find_contours(a, THRESHOLD_2)
clrs_2 = ['green' if (x <= THRESHOLD_2) else 'none' for x in a_flat ]
# The same coordinates and values as in the previous example, 
# but now with a different (lower) threshold.

r_2 = linear_interpolation(p, sp, q, sq, THRESHOLD_2)
# Display the image, the binary index, the contours,
# the previous linearly interpolated point (gray dot),
# and a new linearly interpolated point (red dot).

fig, ax = plt.subplots(figsize=(10, 10))
ax.imshow(a, cmap=plt.cm.gray_r, origin="lower")

plt.scatter(x, y, c=clrs_2, edgecolors="green")

for n, contour in enumerate(contours_2):
    print(f"Coordinates (contour {n + 1})\nx: {contour[:, 1]}\ny: {contour[:, 0]}\n")
    ax.plot(contour[:, 1], contour[:, 0], linewidth=2, zorder=1)
    
plt.scatter([r[0], r_2[0]], [r[1], r_2[1]], c=["silver", "red"], edgecolors=["silver", "red"], zorder=2)

plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15796628602501359, 'fraction_numerical': 0.029907558455682437, 'mean_word_length': 4.098406098406098, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 28, 'https://': 10, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '209125', 'license': 'MIT', 'n_tokens_mistral': 2801, 'n_tokens_neox': 2577, 'n_words': 843, 'path': 'marching-squares-demo/Marching Squares demo.ipynb', 'repo_name': 'joaopalmeiro/datavis-python-playground', 'size': '7405'}