Comment pouvons-nous détecter efficacement les trous dans les ensembles de points 2D avec une sensibilité réglable ?

Détection de trous de réglage de points bidimensionnels

Question :

Étant donné un ensemble de points bidimensionnel, comment trouver les trous dans l'ensemble de points ? L'algorithme doit avoir une sensibilité réglable pour trouver ces trous.

Solution :

1. Crée une représentation bitmap d'un ensemble de points.

   • Scannez les points et déterminez le cadre de délimitation de l'ensemble de points.
   • Crée un bitmap avec des dimensions égales au cadre de délimitation.
   • Pour chaque point, définissez le pixel correspondant dans le bitmap sur 1.

2. Trouver des composants connectés dans un bitmap.

   • Utilise l'algorithme standard des composants connectés pour identifier les composants connectés dans un bitmap.
   • Chaque composant connecté représente un trou dans l'ensemble de points.

3. Calculez l'enveloppe convexe de chaque composant connecté.

   • Utilisez l'algorithme de coque convexe standard pour calculer la coque convexe de chaque composant connecté.
   • L'enveloppe convexe représente la limite du trou.

4. Sortez la limite du trou.

   • Le résultat de l'algorithme est une liste d'enveloppes convexes, chaque enveloppe convexe représentant la limite d'un trou dans l'ensemble de points.

Algorithme :

<code class="language-python">import numpy as np
from scipy.ndimage import label

def find_holes(points, sensitivity=1):
  """
  查找二维点集中的孔洞。

  参数：
    points: 二维点列表。
    sensitivity: 算法的灵敏度。较高的值将导致找到更多孔洞。

  返回：
    表示孔洞边界的凸包列表。
  """

  # 创建点集的位图表示。

  xmin, xmax, ymin, ymax = get_bounding_box(points)
  bitmap = np.zeros((ymax - ymin + 1, xmax - xmin + 1), dtype=np.uint8)
  for point in points:
    bitmap[point[1] - ymin, point[0] - xmin] = 1

  # 查找位图中的连通分量。

  labeled, num_components = label(bitmap)

  # 计算每个连通分量的凸包。

  holes = []
  for i in range(1, num_components + 1):
    component_mask = (labeled == i)
    component_points = np.where(component_mask)
    convex_hull = compute_convex_hull(component_points)
    holes.append(convex_hull)

  # 输出孔洞的边界。

  return holes</code>

Exemple :

<code class="language-python">import matplotlib.pyplot as plt

# 生成一组随机点。

points = np.random.rand(100, 2)

# 查找点集中的孔洞。

holes = find_holes(points)

# 绘制点和孔洞。

plt.scatter(points[:, 0], points[:, 1])
for hole in holes:
  plt.plot(hole[:, 0], hole[:, 1])
plt.show()</code>

Sortie :

[Diagramme de points 2D, trous marqués]

Discussion :

Le paramètre de sensibilité de l'algorithme contrôle la taille des trous trouvés. Une sensibilité plus élevée entraînera la découverte d'un plus grand nombre de trous, tandis qu'une sensibilité plus faible entraînera la découverte d'un nombre inférieur de trous. La sensibilité optimale dépend de l'application spécifique.

L'algorithme peut être utilisé pour trouver des trous dans une variété de différents types d'ensembles de données, notamment des nuages ​​de points, des images et des maillages. Il s'agit d'un outil polyvalent et puissant pour analyser les données et identifier les modèles.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!