Combine adjacent 3D polygons that are in certain order

Question

Given two three-dimensional polygons that are both in the same winding order (counter-clockwise order or in clockwise order):

poly1 = np.array([[120787.075999871, 491779.675000143, -2.0699999332428], [120784.319999829, 491781.831000042, 5.96999979019165], [120784.319999829, 491781.831000042, -2.0699999332428], [120787.075999871, 491779.675000143, -2.0699999332428]])
poly2 = np.array([[120787.075999871, 491779.675000143, -2.03999996185303], [120787.075999871, 491779.675000143, 5.90999984741211], [120784.319999829, 491781.831000042, 5.96999979019165], [120787.075999871, 491779.675000143, -2.03999996185303]])

How can I combine / merge these adjacent polygons into a single polygon (in Python) while keeping the order.

Here is a code to plot the two adjacent polygons:

import matplotlib.pyplot as plt, numpy as np
from mpl_toolkits.mplot3d import Axes3D

fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.plot(poly1[:,0],poly1[:,1],poly1[:,2])
ax.plot(poly2[:,0],poly2[:,1],poly2[:,2])
ax.view_init(45, 45) 
plt.show()

Answer 1

The coordinates of the points in poly1 and poly2 are not an exact match (despite the fact that they look like the same point on the plot).
I guess you want the algorithm to work with "close enough" values (i.e. if the distance between the points is less than a given tolerance, e.g. 0.1, they are considered the same point).

You can join the two polygons by finding a common edge and removing it.

To find the common edge, we first determine which points of the polygons are common to both polygons.
I had a look at this post and chose the cKDTree method to do that. It works by

1. finding for each point of one polygon its closest neighbouring point in the other polygon
2. comparing the distance between those two points. If the distance is less than our set tolerance, we consider them the same point and common to both polygons.

Once you've determined, which points are common, you can verify whether they are adjacent. If they are, you've found the edge to remove.

The resulting polygon will be composed of

• all points from poly1
• those points from poly2 which do not form the common edge

Here is the code:

import matplotlib.pyplot as plt, numpy as np
from mpl_toolkits.mplot3d import Axes3D
from scipy.spatial import cKDTree

poly1 = np.array([[120787.075999871, 491779.675000143, -2.0699999332428], [120784.319999829, 491781.831000042, 5.96999979019165], [120784.319999829, 491781.831000042, -2.0699999332428], [120787.075999871, 491779.675000143, -2.0699999332428]])
poly2 = np.array([[120787.075999871, 491779.675000143, -2.03999996185303], [120787.075999871, 491779.675000143, 5.90999984741211], [120784.319999829, 491781.831000042, 5.96999979019165], [120787.075999871, 491779.675000143, -2.03999996185303]])


def is_close(a, b, tolerance):
    # Get closest distances for each pt in a
    dist = cKDTree(b).query(a, k=1)[0] # k=1 selects closest one neighbor

    # Check the distances against the given tolerance value
    return dist <= tolerance

def find_consecutive_true_values(arr):
    i = 0
    while i < len(arr) - 1:
        if arr[i] and arr[i+1]:
            return i
        i+=1
    raise Exception('No common edge found')

# Find points in poly1, which are closer than given tolerance to any point in poly2
# and vice versa
tolerance = 0.1
points_in_poly1_close_to_poly2 = is_close(poly1, poly2, tolerance)
points_in_poly2_close_to_poly1 = is_close(poly2, poly1, tolerance)

# Scan each array for two adjacent true values (points at those two indices 
# form an edge which is common to both polygons and which we want to remove).
# Idx1 (resp. idx2) will contain the index of the first point of that common edge in poly1 (resp. poly2)
idx1 = find_consecutive_true_values(points_in_poly1_close_to_poly2)
idx2 = find_consecutive_true_values(points_in_poly2_close_to_poly1)

#Split poly1 into two parts:
#  first part contains points from the start up to the first point of the common edge (inclusive)
#  second part contains points from the second point of the common edge to the end
poly1_part1 = poly1[:idx1+1]
poly1_part2 = poly1[idx1+1:]

#Remove common edge from poly2, depending on where it is located, we end up with one or two parts
if idx2 == len(poly2) - 2:
    poly2_part1 = poly2[1:len(poly2) - 2]
    poly2_part2 = None
elif idx2 == 0:
    poly2_part1 = poly2[2:len(poly2) - 1]
    poly2_part2 = None
else:
    poly2_part1 = poly2[idx2+2:]
    poly2_part2 = poly2[1:idx2]

#Create the resulting polygon by concatenating the individual parts (poly2_part2 may be empty)
if(poly2_part2 is None):
    poly = np.concatenate((poly1_part1, poly2_part1, poly1_part2))
else:
    poly = np.concatenate((poly1_part1, poly2_part1, poly2_part2, poly1_part2))


fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.plot(poly[:,0], poly[:,1], poly[:,2])


ax.view_init(45, 45) 
plt.show()

(the code is far from idiomatic, if you know your Python, feel free to edit it :) )

Answer 2

I've just made a simple solution which allows to combine two polygons with at least 1 common point and potential created continuous lines.
Now, there is no tolerance (the common points have to be the same) but in the days, I'll add it as function's argument because I'm totally into that. I'm going to add possibility of merging polygons a few common lines but I need time. Probably, I'll push it on GitHub and paste link here.

Modified polygons (in poly2 first and last element are the same as in poly1):

poly1 = np.array([[120787.075999871, 491779.675000143, -2.0699999332428], [120784.319999829, 491781.831000042, 5.96999979019165], [120784.319999829, 491781.831000042, -2.0699999332428], [120787.075999871, 491779.675000143, -2.0699999332428]])
poly2 = np.array([[120787.075999871, 491779.675000143, -2.0699999332428], [120787.075999871, 491779.675000143, 5.90999984741211], [120784.319999829, 491781.831000042, 5.96999979019165], [120787.075999871, 491779.675000143, -2.0699999332428]])

Kinda banal solution and the code isn't beautiful because of this conditions, but it works:

def merge_polygons(p1, p2):
    """
    Simple function that allows to combine two polygons (as numpy arrays) with at least 1 common point
    and potential created continuous lines.
    :return: polygon (merged p1 and p2) as numpy array
    """
    poly1_l = list(p1)[1:]
    poly2_l = list(p2)[1:]
    common_i1 = []
    common_i2 = []

    # looking for common points
    for i, j in ((i, j) for i in range(len(poly1_l)) for j in range(len(poly2_l))):
        if np.all(poly1_l[i] == poly2_l[j]):
            common_i1.append(i)
            common_i2.append(j)
    if not common_i1:
        raise Exception("Can't merge the polygons - no common point!")

    # merging polygons with 1 common point
    if len(common_i1) == 1:
        poly1_l[common_i1[0]:common_i1[0]] = poly2_l[common_i2[0]:] + poly2_l[:common_i2[0]][::-1]
        poly1_l.append(poly1_l[0])
        return np.array(poly1_l)
    else:  # merging polygons with 2+ common points
        start = [None, None]
        end = [None, None]
        # checking, if the common points are creating continuous line
        for iterator, common_l in enumerate((common_i1, common_i2)):
            for i in common_l:
                if not (i - 1) % len(poly1_l) in common_l and not (i + 1) % len(poly1_l) in common_l:
                    raise Exception("Can't merge the polygons - the common part has to be continuous!")
                elif not (i - 1) % len(poly1_l) in common_l:  # marking the start and the end of common part
                    start[iterator] = i
                elif not (i + 1) % len(poly1_l) in common_l:
                    end[iterator] = i
        # merging polygons due to location of common part
        if isinstance(start[0], int) and isinstance(end[0], int):
            poly3_l = []
            if start[0] < end[0]:  # if the common part in the first polygon is not interrupted by the beginning and the end of list
                if start[1] < end[1]:  # if the common part in the second polygon is not interrupted by the beginning and the end of list
                    poly3_l.extend(poly1_l[:start[0]])
                    if np.all(poly1_l[start[0]] == poly2_l[start[1]]):  # if start of chain in first polygon corresponds to start of chain in second polygon
                        poly3_l.extend(poly2_l[:start[1]+1][::-1])
                        poly3_l.extend(poly2_l[end[1]:][::-1])
                    else:
                        poly3_l.extend(poly2_l[end[1]:])
                        poly3_l.extend(poly2_l[:start[1]+1])
                    poly3_l.extend(poly1_l[end[0]+1:])
                    poly3_l.append(poly3_l[0])
                else:
                    poly3_l.extend(poly1_l[:start[0]])
                    if np.all(poly1_l[start[0]] == poly2_l[start[1]]):
                        poly3_l.extend(poly2_l[end[1]:start[1]+1][::-1])
                    else:
                        poly3_l.extend(poly2_l[end[1]:start[1]+1])
                    poly3_l.extend(poly1_l[end[0]+1:])
                    poly3_l.append(poly3_l[0])
            else:
                if start[1] < end[1]:
                    poly3_l.extend(poly2_l[:start[1]+1])
                    if np.all(poly1_l[start[0]] == poly2_l[start[1]]):
                        poly3_l.extend(poly1_l[end[0]+1:start[0]][::-1])
                    else:
                        poly3_l.extend(poly1_l[end[0]+1:start[0]])
                    poly3_l.extend(poly2_l[end[1]:])
                    poly3_l.append(poly3_l[0])
                else:
                    poly3_l.extend(poly1_l[end[0]+1:start[0]])
                    if np.all(poly1_l[start[0]] == poly2_l[start[1]]):
                        poly3_l.extend(poly2_l[end[1]:start[1]+1][::-1])
                    else:
                        poly3_l.extend(poly2_l[end[1]:start[1]+1])
                    poly3_l.append(poly3_l[0])
            return np.array(poly3_l)
        else:
            raise Exception("Polygons are the same - there is no need to merge them.")

This function is tested for all possibilities with two tringles but I'm gonna make more tests for that.

How it's looks like:

---

If you want to just marge the polygons into one shape, you have to just use lists:

poly3 = np.array(list(poly1) + list(poly2))

How it's looks like for your case:

I hope it'll help you!