Implementación del escaneo convexo con Python (versión 2d)

SOURCE 10418 palabras RhinocerosRhinoPython

Instalación de escaneo convexo



Inicio


Esta vez se realizó un escaneo 2d convexo.
El escaneo convexo es un algoritmo para seleccionar el punto más externo de un grupo de puntos dados. (tal comprensión)
Una vez conectado el punto eliminado, se convierte en un polígono (polígono convexo) que no puede ser obtuso.
Creo que esta propiedad parece estar disponible en el procesamiento de nubes puntuales y el diseño arquitectónico del sensor depth, así que inténtalo.
Como ese memo.

Graham Scan


El algoritmo de escaneo convexo utilizado esta vez utiliza un escaneo Graham simple en vivo.
Por cierto, los siguientes algoritmos de escaneo convexo son comunes.
• gift wrapping
• Graham Scan
• quickhul
• División y consulta
Espera un minuto. Referencia
Aunque es un algoritmo bastante esotérico, pero siempre ha sido implementado sin compromiso. Reír

Flujo del algoritmo


Encontrar el punto P con la coordenada más pequeña de
  • x.
  • Los puntos alrededor de
  • p están dispuestos en orden angular alrededor del sentido contrario a las agujas del reloj.
  • Suprímase el vértice del saliente
  • .
  • La corriente es gruesa.
    El truco es eliminar 3 vértices convexos.
    En este caso, el vértice convexo se determina calculando el área marcada.
    En cuanto al área firmada, me gustaría resumir en otras oportunidades.
    En pocas palabras, el área del Triángulo se calcula utilizando el valor de coordenadas de 3 puntos.
    En este caso, el área que no tiene en cuenta el valor absoluto se convierte en un valor negativo. Mirando el área positiva y negativa, podemos ver la disposición de 3 puntos.

    Realización


    Aquí se utilizan estructuras de lista como P = [X, y, Z] para representar puntos de coordenadas.
    P Una List a es una lista de puntos de coordenadas guardados.
    ConvEx Si ejecuta la función Hull, devuelve el valor de las coordenadas que componen la cÃpsula convexa.
    Si conecta puntos y puntos secuencialmente, puede dibujar un gráfico convexo.
    Aunque omití los detalles, los describí yo mismo usando un ad 3D llamado rihinoceros.
    Convexhull. Py
    # coding: utf-8
    
    
    def signed_area(p1, p2, p3):
        '''符号付き面積を計算 '''
    
        area = (((p2[0] - p1[0]) * (p3[1] - p1[1])) - ((p3[0] - p1[0]) * (p2[1] - p1[1]))) / 2
        return area
    
    
    def convex_hull(p_list):
        '''グラハムの凸包走査 '''
    
        p_sort = []
        for i in p_list:
            p_sort.append(i[0])
    
        # x座標が最小のものをリストの先頭に配置。
        min_index = p_sort.index(min(p_sort))
        min_p = p_list.pop(min_index)
        p_list.insert(0, min_p)
    
        # 座標最小の点と他の点との角度順にソート ソートアルゴリズムに選択の余地が有る。
        p_length = len(p_list)
        count = 0
        index = 0
        while True:
            count += 1
            index += 1
    
            area_sign = signed_area(p_list[0], p_list[index], p_list[index + 1])
    
            # 符号付き面積が負ならば点を入れ替え
            if area_sign < 0:
                p_list[index], p_list[index + 1] = p_list[index + 1], p_list[index]
                count = 0
    
            if count == p_length - 1:
                break
    
            if index == p_length - 2:
                index = 0
    
        # 凹部の点を削除する。
        index = -1
        count = 0
        while True:
            index += 1
            count += 1
    
            area_sign = signed_area(p_list[index], p_list[index + 1], p_list[index + 2])
            if area_sign < 0:
                del p_list[index + 1]
                count = 0
    
            if count == len(p_list):
                break
    
            if index >= len(p_list) - 3:
                index = -1
        return p_list
    
    
    
    

    Observaciones finales


    Gracias por leer el final.
    La próxima vez que tenga la oportunidad de organizar los escaneos 3D correspondientes de quickhull en un informe, por favor preste más atención.