[Dynamo += Python] Point dans un Polygone ?

•  

Comment vérifier si un point se trouve à l'intérieur d'un polygone fermé ?

#Polygon#RevitAPI #DynamoBIM #IsInside

if this article is not in your language, use the Google Translate widget ⬈ (bottom of page for Mobile version ⬇)

À partir un nuage de points 2D, comment filtrer ceux qui sont à l'intérieur d'une PolyCurve ou d'un Polygone ?
Dans cet article, nous examinerons 4 méthodes différentes pour résoudre ce problème.

• Commençons par générer un polygone aléatoire 

# Load the Python Standard and DesignScript Libraries
import sys
import clr
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import *
import random
import math

n = 8  # Number of vertices
r = 0.7  # Magnitude of unit circle disturbance
N = n * 3 + 1  # Number of points in the path
random.seed(200)

angles = [2 * math.pi * i / (N - 1.0) for i in range(N)]
radii = [2 * r * random.random() + 3 - r for _ in range(N)]
points = [Point.ByCoordinates(radii[i] * math.cos(angles[i]), radii[i] * math.sin(angles[i])) for i in range(N)]
polygon = Polygon.ByPoints(points)
OUT = polygon

Ce code génère un polygone aléatoire en utilisant des coordonnées polaires pour chaque point autour d'un cercle perturbé. Les points sont connectés pour former un polygone aléatoire.

• Puis un nombre aléatoire de 10000 points

• Maintenant voyons les differentes méthodes

1. Méthode avec la librairie Python 'Shapely'

import sys
import clr
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import *

clr.AddReference('Python.Included')
import Python.Included as pyInc
path_py3_lib = pyInc.Installer.EmbeddedPythonHome
sys.path.append(path_py3_lib + r'\Lib\site-packages')

from shapely.geometry import Point, Polygon
import numpy as np

    
polygon = IN[0]
input_pts = np.array(IN[1])

pointCheck = np.array([(p.X, p.Y) for p in input_pts])
polygon = Polygon((p.X, p.Y) for p in polygon.Points)
mask = [polygon.contains(Point(point)) for point in pointCheck ]

OUT = input_pts[mask] 

La bibliothèque Shapely offre une solution simple et efficace pour effectuer des opérations géométriques en Python. La méthode contains de Shapely peut être utilisée pour vérifier si un point est à l'intérieur d'un polygone.

Avantages :

• Efficacité pour des polygones complexes.
• Gestion robuste des cas limites.

Inconvénients :

• Nécessite l'installation d'une bibliothèque externe (pip install shapely).
• compatible seulement avec le moteur CPython3

2. Méthode 'Ray Tracing' + LINQ

import sys
import sys
import clr
import System
from System.Collections.Generic import List
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import Point
clr.AddReference("System.Core")
clr.ImportExtensions(System.Linq)


def ray_tracing_method(pt,poly):
    x,y = pt.X, pt.Y
    n = len(poly)
    inside = False

    p1x,p1y = poly[0]
    for i in range(n+1):
        p2x,p2y = poly[i % n]
        if y > min(p1y,p2y):
            if y <= max(p1y,p2y):
                if x <= max(p1x,p2x):
                    if p1y != p2y:
                        xints = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
                    if p1x == p2x or x <= xints:
                        inside = not inside
        p1x,p1y = p2x,p2y
    if inside:
        return pt
    else:
        return None

polygon = IN[0]
input_pts = IN[1]
polygon = [(p.X, p.Y) for p in polygon.Points]
# with Linq + IronPython
inside_pts = input_pts.Select(lambda pt: ray_tracing_method(pt,polygon)).Where(lambda x : x is not None).ToList()
# for PythonNet(Cpython3)
# inside_pts = [pt for pt in input_pts if ray_tracing_method(pt,polygon) is not None)]
OUT = inside_pts

L'algorithme du test du nombre de rayons 'croisants' est une approche classique pour résoudre ce problème. Cette méthode utilise des rayons qui partent du point à vérifier et compte combien de fois, ils traversent les côtés du polygone.

Avantages :

• Implémentation simple.
• Fonctionne bien pour des polygones simples.
• Compatible avec tous les moteurs Python
  
  

Note :
ici l'utilisation des méthodes LINQ (avec Ironpython) améliore un peu les performances (cela devrait être encore meilleur avec l'arrivée de .Net 7 et plus)

Inconvénients :

• Peut-être moins efficace pour des polygones complexes.
• Gestion des points sur les bords du polygone peut nécessiter une attention particulière.

3. Méthode avec la librairie Python 'Matplotlib'

import sys
import clr
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import *

clr.AddReference('Python.Included')
import Python.Included as pyInc
path_py3_lib = pyInc.Installer.EmbeddedPythonHome
sys.path.append(path_py3_lib + r'\Lib\site-packages')

import matplotlib.path as mplPath
import numpy as np

    
polygon = IN[0]
input_pts = np.array(IN[1])
pointCheck = np.array([(p.X, p.Y) for p in input_pts])

bbPath = mplPath.Path([(p.X, p.Y) for p in polygon.Points])
mask = bbPath.contains_points(pointCheck)

OUT = input_pts[mask]

La bibliothèque matplotlib offre également une méthode pour vérifier si un point est à l'intérieur d'un polygone. Elle utilise la classe Path pour définir le polygone et la méthode contains_point pour effectuer la vérification.

Avantages :

• Pas besoin d'installer de bibliothèque externe si matplotlib est déjà utilisée.

Inconvénients :

• Moins efficace pour des polygones complexes.
• compatible seulement avec le moteur CPython3

4. Méthode par sommation des Angles

import sys
import clr
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import *


def isInsidePolyg(polygon, pointCheck):
    #with Dynamo API
    lstangle =[]
    pointPolyg = polygon.Points
    for idx, pt in enumerate(pointPolyg):
        if idx > 0:
            vecta = Vector.ByTwoPoints(pointCheck, pointPolyg[idx -1])
            vectb = Vector.ByTwoPoints(pointCheck, pt)
            cross = vecta.Cross(vectb).Normalized()
            angle = vecta.AngleWithVector(vectb)
            vecta.Dispose()
            vectb.Dispose()
            lstangle.append(angle * cross.Z)

    return abs(sum(lstangle)) > 180 

polycurve = IN[0]
input_pts = IN[1]


OUT = [p for p in input_pts if isInsidePolyg(polycurve, p)]

Cette approche calcule la somme des angles entre le point à vérifier et les côtés du polygone pour déterminer son emplacement.
Si cette somme est supérieure à 180 degrés, le point est considéré comme à l'intérieur du polygone.

Avantages :

• Implémentation simple.
• Fonctionne bien pour des polygones simples.
• Compatible avec tous les moteurs Python

Inconvénients :

• Moins efficace en termes de performances.

 

Aperçu du résultat avec TuneUp