I am trying to create an application to automate the workflow of dam analysis for the geotechnical sector I work in. The app takes as input a DXF file that contains the geometry of the dam section. From this file, we extract data such as points, edges, and so on. One of the requirements for the app to work is that the section must be a closed polygon (see images in the example for reference).
Now, I need to find the upper line that “covers” this polygon (the first two images show what this line should be for each example section) and a base line that starts from the leftmost point and goes to the rightmost point. The intention is to have the dam polygon covered by both lines, essentially creating a “sandwich” with these lines to determine its geometry.
I attempted to create this line using my own logic, but it was not successful. I now need a method to find this upper line that covers all points on the top (and only on the top) of the polygon. I searched for algorithms online, but all I could find were algorithms to determine if a point is inside a polygon (such as the convex hull), which do not help me.
Below is the code I have been using to determine this top_line and base_line (which is incorrect). Does anyone know how to solve this or if there are any libraries that could help? I have tried Shapely, but with no success. Thanks in advance, any help is much appreciated!
import matplotlib.pyplot as plt
from shapely.geometry import LineString
# Dados das arestas
edges = [
((-20.829, 55.53), (-20.829, 53.13)),
((-20.829, 55.53), (34.552, 55.53)),
((-20.829, 55.53), (-20.829, 58.63)),
((-20.829, 53.13), (34.552, 53.13)),
((-20.829, 53.13), (-20.829, 49.73)),
((34.552, 53.13), (34.552, 55.53)),
((34.552, 53.13), (34.552, 49.73)),
((34.552, 55.53), (34.552, 57.376)),
((-14.727, 59.75), (-18.158, 59.75)),
((-14.727, 59.75), (-14.727, 64.737)),
((-14.727, 59.75), (-8.625, 59.75)),
((-18.158, 59.75), (-18.158, 64.737)),
((-18.158, 59.75), (-20.829, 59.75)),
((-18.158, 64.737), (-14.727, 64.737)),
((-2.25, 64.0), (-8.625, 59.75)),
((-2.25, 64.0), (-1.25, 64.0)),
((-8.625, 59.75), (-7.625, 59.75)),
((-7.625, 59.75), (-1.25, 64.0)),
((-7.625, 59.75), (-7.125, 59.75)),
((-1.25, 64.0), (-0.75, 64.0)),
((-7.125, 59.75), (-0.75, 64.0)),
((-7.125, 59.75), (7.125, 59.75)),
((-0.75, 64.0), (0.75, 64.0)),
((7.125, 59.75), (7.625, 59.75)),
((7.125, 59.75), (0.75, 64.0)),
((7.625, 59.75), (8.625, 59.75)),
((7.625, 59.75), (1.25, 64.0)),
((8.625, 59.75), (10.951, 59.75)),
((8.625, 59.75), (2.25, 64.0)),
((10.951, 59.75), (11.613, 59.487)),
((11.613, 59.487), (13.195, 59.11)),
((13.195, 59.11), (13.747, 58.75)),
((13.747, 58.75), (13.75482973669868, 58.745690645800494)),
((13.75482973669868, 58.745690645800494), (13.965006969842744, 58.6300126636222)),
((13.75482973669868, 58.745690645800494), (16.755, 58.746)),
((13.965006969842744, 58.6300126636222), (-20.829, 58.63)),
((13.965006969842744, 58.6300126636222), (15.444, 57.816)),
((-20.829, 58.63), (-20.829, 59.75)),
((0.75, 64.0), (1.25, 64.0)),
((1.25, 64.0), (2.25, 64.0)),
((15.586, 57.75), (15.444, 57.816)),
((15.586, 57.75), (16.034, 57.516)),
((34.552, 57.376), (34.174, 57.271)),
((34.174, 57.271), (33.816, 57.194)),
((33.816, 57.194), (31.833, 56.75)),
((31.833, 56.75), (31.289, 56.716)),
((31.289, 56.716), (30.511, 56.695)),
((30.511, 56.695), (30.095, 56.693)),
((30.095, 56.693), (29.607, 56.699)),
((29.607, 56.699), (29.104, 56.718)),
((29.104, 56.718), (28.437, 56.75)),
((28.437, 56.75), (28.064018072840494, 56.76349934588915)),
((28.064018072840494, 56.76349934588915), (27.691, 56.777)),
((28.064018072840494, 56.76349934588915), (26.505, 58.652)),
((27.691, 56.777), (24.817032481790534, 56.964497880885276)),
((24.817032481790534, 56.964497880885276), (21.943, 57.152)),
((24.817032481790534, 56.964497880885276), (26.505, 58.652)),
((21.943, 57.152), (20.025, 57.067)),
((20.025, 57.067), (19.16600997989089, 57.16608651658138)),
((19.16600997989089, 57.16608651658138), (17.641, 57.342)),
((19.16600997989089, 57.16608651658138), (16.755, 58.746)),
((17.641, 57.342), (16.254, 57.447)),
((16.254, 57.447), (16.034, 57.516)),
((34.552, 37.864), (-20.829, 37.864)),
((34.552, 37.864), (34.552, 40.875)),
((-20.829, 37.864), (-20.829, 40.875)),
((-20.829, 40.875), (34.552, 40.875)),
((-20.829, 40.875), (-20.829, 46.59)),
((34.552, 40.875), (34.552, 46.59)),
((34.552, 46.59), (-20.829, 46.59)),
((34.552, 46.59), (34.552, 49.73)),
((-20.829, 46.59), (-20.829, 49.73)),
((34.552, 49.73), (-20.829, 49.73))
]
# Função para encontrar o ponto mais à esquerda com maior Y
def find_start_point(edges):
start_point = None
for edge in edges:
for point in edge:
if start_point is None or (point[0] < start_point[0]) or (point[0] == start_point[0] and point[1] > start_point[1]):
start_point = point
print("Start Point:", start_point)
return start_point
def find_end_point(edges):
end_point = None
for edge in edges:
for point in edge:
if end_point is None or (point[0] > end_point[0]) or (point[0] == end_point[0] and point[1] > end_point[1]):
end_point = point
print("End Point:", end_point)
return end_point
# Função para encontrar o próximo ponto baseado nas arestas conectadas
def find_next_point(current_point, edges, visited_points):
connected_points = []
for edge in edges:
if edge[0] == current_point:
connected_points.append(edge[1])
elif edge[1] == current_point:
connected_points.append(edge[0])
if not connected_points:
return None
# Filtrar os pontos conectados para remover os pontos já visitados
connected_points = [p for p in connected_points if p not in visited_points]
if not connected_points:
return None
# Verifica se há pontos com Y maior que o do ponto atual
has_higher_y = any(p[1] > current_point[1] for p in connected_points)
last_visited_point = visited_points[-2] if len(visited_points) > 1 else current_point
print("Current Point:", current_point)
print("Connected Points:", connected_points)
print("Has Higher Y:", has_higher_y)
print("Last Visited Point:", last_visited_point)
if has_higher_y:
# Priorizar pontos com maior Y e, em caso de empate, menor X
potential_next_point = max(connected_points, key=lambda p: (p[1], -p[0]))
print("Potential Next Point (Higher Y):", potential_next_point)
if potential_next_point[1] > last_visited_point[1]:
print("Last Visited Point used in comparison", last_visited_point)
next_point = potential_next_point
else:
next_point = max(connected_points, key=lambda p: (p[0], p[1]))
else:
# Priorizar pontos com maior Y e maior X
next_point = max(connected_points, key=lambda p: (p[1], p[0]))
print("Chosen Next Point:", next_point)
print("-" * 40)
return next_point
# Função principal para encontrar a linha de topo
def find_top_line(edges):
top_line = []
visited_points = []
start_point = find_start_point(edges)
end_point = find_end_point(edges)
top_line.append(start_point)
visited_points.append(start_point) # Adicionar o ponto inicial à lista de pontos visitados
current_point = start_point
while True:
next_point = find_next_point(current_point, edges, visited_points)
if next_point is None or next_point == start_point or next_point == end_point:
break
top_line.append(next_point)
visited_points.append(next_point) # Adicionar o próximo ponto aos pontos visitados aqui
current_point = next_point
print("Top Line So Far:", top_line)
print("Visited Points So Far:", visited_points)
print("=" * 40)
# Adicionar o ponto final à linha de topo
if next_point == end_point:
top_line.append(end_point)
return top_line
# Função para encontrar o próximo ponto baseado nas arestas conectadas para a linha de fundação
def find_next_point_base(current_point, edges, visited_points):
connected_points = []
for edge in edges:
if edge[0] == current_point:
connected_points.append(edge[1])
elif edge[1] == current_point:
connected_points.append(edge[0])
if not connected_points:
return None
# Se houver mais de um ponto conectado, priorize mover para a direita
if len(connected_points) > 1:
connected_points = [p for p in connected_points if p not in visited_points and p[0] > current_point[0]]
next_point = None
for point in connected_points:
if point in visited_points:
continue
if next_point is None:
next_point = point
elif point[1] < next_point[1]:
next_point = point
elif point[1] == next_point[1] and point[0] > next_point[0]:
next_point = point
return next_point
# Função principal para encontrar a linha de fundação
def find_base_line(edges):
base_line = []
visited_points = set()
start_point = find_start_point(edges)
end_point = find_end_point(edges)
base_line.append(start_point)
visited_points.add(start_point)
current_point = start_point
while True:
next_point = find_next_point_base(current_point, edges, visited_points)
if next_point is None or next_point == start_point or next_point == end_point:
break
base_line.append(next_point)
visited_points.add(next_point)
current_point = next_point
# Adicionar o ponto final à linha de fundação
if next_point == end_point:
base_line.append(end_point)
return base_line
# Encontrar a linha de topo e a linha de fundação
top_line = find_top_line(edges)
base_line = find_base_line(edges)
# Função para plotar todas as arestas, a linha de topo e a linha de base
def plot_edges_and_lines(edges, top_line, base_line):
plt.figure(figsize=(10, 8))
# Plotar todas as arestas
for edge in edges:
x_values = [edge[0][0], edge[1][0]]
y_values = [edge[0][1], edge[1][1]]
plt.plot(x_values, y_values, 'b-', linewidth=1)
# Plotar a linha de topo
top_x = [point[0] for point in top_line]
top_y = [point[1] for point in top_line]
plt.plot(top_x, top_y, 'r-', linewidth=2, label='Linha de Topo')
# Plotar a linha de fundação
base_x = [point[0] for point in base_line]
base_y = [point[1] for point in base_line]
plt.plot(base_x, base_y, 'g-', linewidth=2, label='Linha de Fundação')
# Configurar o gráfico
plt.xlabel('X')
plt.ylabel('Y')
plt.title('Arestas, Linha de Topo e Linha de Fundação')
plt.legend()
plt.grid(True)
plt.show()
# Plotar todas as arestas e as linhas de topo e fundação
plot_edges_and_lines(edges, top_line, base_line)
I have tried creating my own logic, explicitly specifying which points the line should pass through. This approach worked for the first image in the reference but not for the second. From this, I realized that the logic will vary greatly depending on the polygon.
2