¿Cuál es la suma de los segmentos externos de estos rectángulos?

Lo que haría es, rodaría mi bolígrafo / lápiz sobre el borde de la hoja, si es A4, el lado más corto es de 21 cm. Si el número total de rotación de la pluma para cubrir la distancia es N, entonces la circunferencia de la pluma es 21 / N.

Luego, rodaría el lápiz a lo largo de los bordes exteriores de los rectángulos, de modo que el eje del lápiz sea perpendicular al borde. En cada intersección podemos cambiar la dirección de la pluma. Si el número total de rotación de la pluma es M, entonces la longitud total de los segmentos externos sería aproximadamente M * 21 / N cms.

La clave para resolver este tipo de problema es dividirlo en pequeñas funciones que sean fáciles de implementar. A menudo, es útil introducir algún tipo y considerar las operaciones naturales que puede realizar en ese tipo. Aquí hay firmas de tipo de algunas funciones útiles para implementar sin eliminar por completo la diversión de resolver el problema:

(El segmento es de dos puntos, los triángulos se representan como una lista de tres puntos en sentido horario, un polígono significa un polígono simple representado como una lista de n puntos en sentido horario)

Interior (triángulo, punto) -> Bool

Interior (Lista de triángulos, punto) -> Bool

Triangular (Polígono) -> Lista de triángulos

Intersecar (punto, punto, punto, punto) -> Bool (verifica si dos segmentos de línea se cruzan)

Unión (Polígono, Polígono) -> Polígono

Unión (Lista de polígonos) -> Polígono

Circunferencia (polígono) -> Flotador

Donde Triangulate y Union son los más no triviales. Para implementar Triangulate, sigue cortando triángulos que no contienen ningún otro punto en el polígono. Al implementar Union, asegúrese de estar atento al caso en el que obtiene un límite no simple y seleccione el componente externo que contiene todos los demás.

EDITAR: “Perímetro de contorno” es ambiguo. Un comentario señala que esto podría no estar pidiendo el casco convexo, sino solo el perímetro de la figura, la suma de los segmentos de línea “externos”. Eso no parece demasiado difícil. Para cada lado tienes que averiguar qué porciones están dentro de un rectángulo y cuáles no. Luego suma las porciones que no lo son.

El OP confirmó esta interpretación, así que tal vez pueda desarrollar esto un poco. Asumiré que la entrada son los vértices dados como coordenadas.

El concepto básico es un segmento de línea con signo, con un punto inicial y final. La primitiva básica que necesita es saber si un punto está a la izquierda o derecha de (o sobre) un segmento de línea con signo cuando camina de principio a fin. Esto es esencialmente el signo del ángulo entre el segmento y el segmento desde el punto en cuestión hasta el primer punto del segmento. Es lo mismo que el signo del seno del ángulo, por lo que el signo del producto cruzado da + si está a la izquierda, – si está a la derecha, y 0 si está en la línea.

Si ordena los puntos del rectángulo para que la progresión sea consistentemente en sentido antihorario, entonces puede concluir que un punto está dentro de un rectángulo si está a la izquierda de todos los lados.

También necesita saber si dos segmentos se cruzan. Ese es un buen problema de álgebra si nunca lo has hecho. (Sugerencia: use representaciones paramétricas para los segmentos). Una vez que pueda hacer eso, encuentre todos los puntos de intersección, dividiendo cada lado de cada rectángulo en segmentos primitivos.

Luego, para cada segmento primitivo, verifique si el punto medio está dentro de algún rectángulo; si no, agréguelo al perímetro de acumulación.

ANTIGUA RESPUESTA: interpretación del casco convexo

Los rectángulos son un poco de arenque rojo. Básicamente, se trata del casco convexo de un conjunto de puntos que resultan ser los vértices del rectángulo. El casco convexo es uno de los problemas básicos de la geometría computacional, por lo que es bueno si un estudiante de ciencias de la computación tiene alguna exposición a él.

Existen algoritmos eficientes aunque complicados para calcular el casco convexo. Para una entrevista de CS, es probable que se te ocurra el “algoritmo de envoltura de regalos” más simple, pero menos eficiente. Primero, eliges un punto de partida que se sabe que está en el casco convexo, digamos el punto más a la izquierda. Luego, considera el segmento en cualquier otro punto. Cuando encuentre un segmento tal que todos los puntos estén a la derecha de la línea implícita, ese segmento es parte del casco convexo. Repita desde el otro punto final. Has terminado cuando te unes al primer punto. La pregunta de seguimiento podría preguntar cómo lidiar con los puntos colineales en el casco convexo y cómo probar si los puntos están a la derecha de la línea.

Esta animación de Wikipedia muestra el algoritmo de envoltura de regalos:

Estoy bastante seguro de que este es (una variante de) el problema del casco convexo.

Algoritmos de casco convexo

Las soluciones que estudié en la universidad (algunas de las cuales se enumeran en esa página) funcionan en su mayoría ~ O (N log N) tiempo, O (N * H) en el peor de los casos.

Si intentara escribir el suyo propio, sin utilizar los algoritmos anteriores, podría dibujar un ‘cuadro delimitador’ (delinear toda la estructura para encontrar uno o más puntos que sean verdaderamente ‘externos’), luego proceder a lo largo de las formas desde ese punto externo, ya sea en el sentido de las agujas del reloj (utilizando un método de ‘siempre girar a la izquierda’) o en sentido contrario a las agujas del reloj (‘siempre girar a la derecha’)

También veo que el problema es un poco como un solucionador de laberintos, solo que, en este caso, el “camino más corto a través del laberinto” es, de hecho, el “camino más externo alrededor del laberinto”. Se podría escribir un sistema experto gradualmente resuelva esto mediante el rastreo de rutas aleatorias que no se crucen por sí mismas y luego compare cada ruta con “cuál tiene el mayor número de puntos externos” o “cuál tiene la distancia total más larga” hasta que se encuentre un máximo / óptimo global. Podría ejecutarse en algún lugar del rango O (N ^ 2) u O (N * H), como BubbleSort, pero funcionaría.

La solución más simple: con una regla.

Programa más simple: cuenta los píxeles alrededor del borde.

Programa avanzado: Convierta las líneas en vectores (hardish), luego encuentre las intersecciones y luego encuentre el perímetro.

Dependiendo del caso de uso depende de qué solución trataría de resolver. El último es el más correcto, pero llevará más tiempo. La solución intermedia funcionará con prácticamente cualquier forma y debería ser lo suficientemente buena.

Suponiendo que obtenga la figura anterior como un mapa de bits como entrada.

Crearía un gran rectángulo alrededor de la figura. Rellene el espacio desde el borde con puntos de color (por ejemplo, amarillo) hasta que se encuentre con el borde de un rectángulo dentro (azul en su figura), luego cuente todos los puntos amarillos que se conectan al menos a un punto azul. Es tu perímetro.

Por supuesto, la característica de color es puramente arbitraria. Simplemente etiqueta los puntos que estableciste con alguna característica que los distingue de los bordes azules. Era solo para ser figurativo.

Y, por supuesto, necesita un algoritmo para llenar el espacio vacío desde el borde del rectángulo externo. Se puede hacer fácilmente escaneando la matriz de coordenadas de puntos.

Su pregunta no pide la longitud del perímetro del contorno, pregunta qué es. Es la forma determinada por las secciones de todos los rectángulos que se encuentran fuera de todos los rectángulos reunidos.

La naturaleza aleatoria de la posición de estos rectángulos dificulta el uso de la trigonometría. Dices que esta pregunta se hizo en una entrevista. ¡Haría una estimación basada en lo que veo como las longitudes de los segmentos requeridos, suponiendo que estén dibujados a la misma escala!

Siendo una pregunta de computadora en lugar de matemática, me quedaría con la navaja de afeitar de occam, la respuesta más simple es probablemente la mejor.

Por la ambigüedad de la pregunta, podría significar el perímetro de las formas, o también podría significar cuántos segmentos externos hay.

La respuesta simple es, si los conté correctamente, hay 7 segmentos externos.

Sin las longitudes, no hay forma de que pueda dar una respuesta a esta pregunta, tal vez este diagrama se dibuja en el gráfico que proporciona una base para resolverlo que en el diagrama actual falta.