algorithm - saber - punto interior de un triangulo

Crea un polígono no intersecante que pase por todos los puntos dados.

Question

Supongamos que tengo una serie de puntos en orden aleatorio, y necesito encontrar un polígono (ordenándolos, de modo que cada par adyacente represente un lado) que pase por todos los puntos, y sus lados no se intersectan, por supuesto.

Intenté hacerlo seleccionando un punto y agregando todos los puntos a la matriz final que están debajo, ordenados de izquierda a derecha. Luego, agregando todos los puntos que están arriba, ordenados de derecha a izquierda.

Me han dicho que puedo agregar un punto adicional y ordenar de forma natural para evitar las auto-intersecciones. Sin embargo, no puedo entenderlo. ¿Qué es una forma simple de hacer esto?

Answer 1

Nuestra estrategia es hacer un plan en el que estemos seguros de que el polígono incluya todos los puntos, y que podamos encontrar un orden para conectarlos donde ninguna de las líneas se interseca.

Algoritmo
1. Encuentra los puntos más a la izquierda p
2. Encuentra el punto más a la derecha q
3. Particione los puntos en A, el conjunto de puntos por debajo de pq y B, el conjunto de puntos por encima de pq [puede usar la prueba de giro a la izquierda (p, q ,?) para determinar si un punto está por encima de la línea] .
4. Ordenar A por la coordenada x (aumentando)
5. Ordenar B por la coordenada x (disminuyendo).
6. Devuelva el polígono definido por p, los puntos en A, en orden, q, los puntos de B en orden.

Tiempo de ejecución :
Los pasos 1,2,3 llevan tiempo O (n).
Pasos 4,5 toman O (nlogn) tiempo.
Paso 6 toma O (n) tiempo.
El tiempo total de ejecución es O (nlogn).

Corrección
Por construcción, todos los puntos, además de p, q, están en el conjunto A o en el conjunto B. Nuestro polígono de salida de la línea 6 genera un polígono con todos los puntos. Ahora debemos argumentar que ninguno de los segmentos de línea en nuestro polígono de salida se intersecta entre sí.

Considere cada segmento en el polígono de salida. El primer borde desde p hasta el primer punto en A no puede intersecar ningún segmento (porque todavía no hay un segmento). A medida que avanzamos en orden por la coordenada x a través de los puntos en A, desde cada punto, el siguiente segmento va a la derecha y todos los segmentos anteriores están a la izquierda. Así, a medida que pasamos de p, a través de todos los puntos de A, al punto q, no tendremos intersecciones.

Lo mismo ocurre cuando pasamos de q atrás a través de los puntos B. Estos segmentos no pueden intersecarse entre sí porque se mueven de derecha a izquierda. Estos segmentos tampoco pueden intersecar nada en A porque todos los puntos en A están debajo de la línea pq, y todos los puntos en B están por encima de esta línea.

Por lo tanto, ningún segmento se intersecta entre sí y tenemos un polígono simple.

Fuente: http://www.cs.wustl.edu/~pless/546/homeworks/hw1_selectedProblems.pdf

Entiendo que esto es muy tarde, pero podría ser útil para futuros espectadores.

Answer 2

Aquí está el código de Python 3.6 (se requieren bibliotecas: matplotlib, numpy) según la answer

Descripción de las imágenes:

• Arriba a la izquierda - polígono predefinido, otros polígonos se generan aleatoriamente.
• Línea de puntos: conecta los puntos de polígono verde (extremo izquierdo) y rojo (extremo derecho).
• Los puntos negros se establecen en la línea de puntos.
• Los puntos naranjas quedan debajo de la línea de puntos.
• Los puntos azules están por encima de la línea de puntos.

=========

import random
from operator import itemgetter
import numpy
import matplotlib
import matplotlib.pyplot

class Create_random_polygon:

    def __init__(self, array, min_rand_coord = None, max_rand_coord = None, points_num = None):        
        self.array = array
        self.min_rand_coord = min_rand_coord 
        self.max_rand_coord = max_rand_coord
        self.points_num = points_num

    def generate_random_points(self):
        random_coords_list = []
        for x in range(self.points_num):
            coords_tuple = (random.randint(self.min_rand_coord, self.max_rand_coord),
                            random.randint(self.min_rand_coord, self.max_rand_coord))
            random_coords_list.append(coords_tuple)
        self.array = random_coords_list
        return random_coords_list

    def close_line_to_polygon(self):
        a = self.array[0]
        b = self.array[len(self.array)-1]
        if a == b:
            pass
        else:
            self.array.append(a)    

    def find_leftmost_point(self):
        leftmost_point = None
        leftmost_x = None
        for point in self.array:
            x = point[0]
            if leftmost_x == None or x < leftmost_x:
                leftmost_x = x
                leftmost_point = point
        return leftmost_point

    def find_rightmost_point(self):
        rightmost_point = None
        rightmost_x = None
        for point in self.array:
            x = point[0]
            if rightmost_x == None or x > rightmost_x:
                rightmost_x = x
                rightmost_point = point
        return rightmost_point

    def is_point_above_the_line(self, point, line_points):
        """return 1 if point is above the line
           return -1 if point is below the line
           return  0 if point is lays on the line"""
        px, py = point
        P1, P2 = line_points
        P1x, P1y = P1[0], P1[1]
        P2x, P2y = P2[0], P2[1]
        array = numpy.array([
            [P1x - px, P1y - py],
            [P2x - px, P2y - py],
            ])
        det = numpy.linalg.det(array)
        sign = numpy.sign(det)
        return sign

    def sort_array_into_A_B_C(self, line_points):
        [(x_lm, y_lm), (x_rm, y_rm)] = line_points
        A_array, B_array, C_array = [], [], []
        for point in self.array:
            x, y = point
            sing = self.is_point_above_the_line( (x, y), line_points)
            if sing == 0:
                C_array.append(point)
            elif sing == -1:
                A_array.append(point)
            elif sing == 1:
                B_array.append(point)
        return A_array, B_array, C_array

    def sort_and_merge_A_B_C_arrays(self, A_array, B_array, C_array):
        A_C_array = [*A_array, *C_array]
        A_C_array.sort(key=itemgetter(0))
        B_array.sort(key=itemgetter(0), reverse=True)        
        merged_arrays = [*A_C_array, *B_array]
        self.array = merged_arrays

    def show_image(self, array, line_points, A_array, B_array, C_array):
        [(x_lm, y_lm), (x_rm, y_rm)] = line_points        
        x = [x[0] for x in array]
        y = [y[1] for y in array]
        Ax = [x[0] for x in A_array]
        Ay = [y[1] for y in A_array]
        Bx = [x[0] for x in B_array]
        By = [y[1] for y in B_array]
        Cx = [x[0] for x in C_array]
        Cy = [y[1] for y in C_array]          
        matplotlib.pyplot.plot(Ax, Ay, ''o'', c=''orange'') # below the line
        matplotlib.pyplot.plot(Bx, By, ''o'', c=''blue'') # above the line
        matplotlib.pyplot.plot(Cx, Cy, ''o'', c=''black'') # on the line
        matplotlib.pyplot.plot(x_lm, y_lm, ''o'', c=''green'') # leftmost point
        matplotlib.pyplot.plot(x_rm, y_rm, ''o'', c=''red'') # rightmost point
        x_plot = matplotlib.pyplot.plot([x_lm, x_rm], [y_lm, y_rm], linestyle='':'', color=''black'', linewidth=0.5) # polygon''s division line
        x_plot = matplotlib.pyplot.plot(x, y, color=''black'', linewidth=1) # connect points by line in order of apperiance        
        matplotlib.pyplot.show()

    def main(self, plot = False):
        ''First output is random polygon coordinates array (other stuff for ploting)''
        print(self.array)
        if self.array == None:
            if not all(
                [isinstance(min_rand_coord, int),
                 isinstance(max_rand_coord, int),
                 isinstance(points_num, int),]
                ):
                print(''Error! Values must be "integer" type:'', ''min_rand_coord ='',min_rand_coord, '', max_rand_coord ='',max_rand_coord, '', points_num ='',points_num)
            else:                
                self.array = self.generate_random_points()            

        print(self.array)
        x_lm, y_lm = self.find_leftmost_point()
        x_rm, y_rm = self.find_rightmost_point()
        line_points = [(x_lm, y_lm), (x_rm, y_rm)]

        A_array, B_array, C_array = self.sort_array_into_A_B_C(line_points)
        self.sort_and_merge_A_B_C_arrays(A_array, B_array, C_array)
        self.close_line_to_polygon()
        if plot:
            self.show_image(self.array, line_points, A_array, B_array, C_array)
        return self.array

if __name__ == "__main__":
    # predefined polygon
    array = [ 
        (0, 0),
        (2, 2),
        (4, 4),
        (5, 5),
        (0, 5),        
        (1, 4),
        (4, 2),
        (3, 3),
        (2, 1),
        (5, 0),
        ]    
    array = None # no predefined polygon
    min_rand_coord = 1
    max_rand_coord = 10000
    points_num = 30

    crt = Create_random_polygon(array, min_rand_coord, max_rand_coord, points_num)
    polygon_array = crt.main(plot = True)    

==========

Answer 3

Bueno, si realmente no te importa la minimalidad o algo así, puedes simplemente colocar un nuevo punto dentro del casco convexo y luego ordenar los otros puntos por ángulo a este nuevo punto. Obtendrás un polígono que no se intersecta.

Answer 4

Como alguien dijo, la solución de duración mínima es exactamente el problema del vendedor ambulante. Aquí hay un enfoque no óptimo pero factible:

Calcula una triangulación de Delauney de tus puntos. Elimine sucesivamente los segmentos de límite hasta que quede con un límite que interpola todos los puntos o no se pueden eliminar más segmentos. No elimine los segmentos de límite si todos los puntos del triángulo que usan ese segmento están en el límite. Toma este límite como tu camino.

Implementé esto en Mathematica usando 40 puntos al azar. Aquí hay un resultado típico:

La objeción obvia es que puede llegar a un punto donde no todos sus puntos son puntos de límite, pero no puede eliminar un segmento de límite sin que el límite se intercepte. Esta es una objeción válida. Me tomó docenas de carreras para ver un caso donde esto sucedió, pero finalmente consiguió este caso:

Probablemente pueda ver algunas formas obvias de solucionar este problema utilizando la topología local, ¡pero le dejaré los detalles a usted! Una cosa que podría ayudar es "voltear el borde" donde toma dos triángulos que comparten un lado, diga el triángulo (p, q, r) y (q, p, s) y reemplácelos con (r, p, s) y ( r, s, q) (todas las coordenadas en sentido antihorario alrededor del triángulo). Esto se puede hacer siempre que los triángulos resultantes en esta transformación también estén ordenados en sentido contrario a las agujas del reloj.

Para reducir la necesidad de reparaciones, tendrá que tomar buenas decisiones de los segmentos para eliminar en cada paso. Utilicé la relación de la longitud del segmento del límite a la suma de las longitudes del otro lado del triángulo candidato (el triángulo formado por el punto potencialmente entrante con el segmento).

Answer 5

Creo que puedes usar el algoritmo de escaneo de Graham para resolver tu problema.

Edición: en general, los algoritmos de casco convexo son algo para mirar.

Answer 6

Lo que buscas se llama una simple poligonización en la literatura. Ver, por ejemplo, esta página web sobre el tema. Es fácil generar una poligonización en star-shaped , como dice Miguel, pero es difícil de encontrar, por ejemplo, una poligonización mínima del perímetro, que es un TSP mínimo, como menciona Axel Kemper. En general, hay un número exponencial de diferentes poligonizaciones para un conjunto de puntos dado.

Para la poligonización en forma de estrella, hay un problema que requiere cierta atención: el punto extra x (en el "núcleo" de la estrella) no debe coincidir con un punto existente. Aquí hay un algoritmo para garantizar x . Encuentre el par de puntos más cercano ( a, b ) y sea x el punto medio del segmento ab . Luego proceda según la publicación de Miguel.

Answer 7

Probar si dos segmentos se intersecan es simple y rápido. Mira that por ejemplo.

Con eso podrías construir tu polígono de forma iterativa:

Puntos de origen: S = {S0, ... Si, Sj,...}

Polígono final: A = {A0, ... Ai, Aj,...}

Comienzas con S lleno y A vacío.

Toma los primeros 3 puntos de S y muévelos a A Este triángulo no es, por supuesto, intersección propia.

Luego, hasta que S esté vacío, tome su primer punto restante, que llamaremos P , y buscaremos una posición en A donde podría insertarse.

Esta posición es i+1 para la primera i verificando que ni [Ai-P] ni [Ai+1-P] intersectan con ningún otro segmento [Ak-Ak+1] .

Tu nuevo polígono A es, por lo tanto, {A0, ... Ai, P, Ai+1, ...}