Algoritmo para implementar una herramienta de selección de lazo?

Estoy desarrollando una aplicación Mac OS X que, como parte de su interfaz de usuario, mostrará muchos elementos visuales en su vista principal que se pueden seleccionar. Estos elementos se pueden ubicar realmente en cualquier lugar dentro de la vista. La interfaz de usuario admitirá varias formas de seleccionar los elementos: selección rectangular de marquesina, selección de marquesina elíptica y selección de lazo 'libre'.Algoritmo para implementar una herramienta de selección de lazo?

Ya tengo el trabajo de selección de marquesina rectangular y elíptica. El algoritmo es bastante simple; un elemento se considera "seleccionado" si el área del elemento se cruza con el área del rectángulo/elipse.

La selección de lazo funcionará tal como lo hace en las aplicaciones modernas de manipulación de imágenes como Photoshop; el usuario puede hacer clic y arrastrar una ruta que se cerrará sola, y los elementos contenidos dentro de la ruta dibujada serán seleccionados.

Este algoritmo probablemente será mucho más complejo que la selección rectangular/elíptica, ya que la forma de la selección no está restringida. Me pregunto si alguien tiene experiencia escribiendo algo como esto, o si puede orientarme en la dirección correcta sobre qué tipo de técnicas de programación son necesarias y cuál es la forma más eficiente en que puede funcionar este algoritmo.

Gracias de antemano.

Fuente

2010-01-16 CJ.

Hola CJ, si has hecho con éxito la codificación de esta función, pega un enlace para el código de muestra. Realmente será de gran ayuda para mí y también para otros. Nos ahorrará mucho tiempo. Esperamos su ayuda. – Gyanendra

La única forma en que puedo pensar es en tratar el contorno de lazo como un polígono. Luego puede usar cualquier estándar point-inside-polygon test para verificar qué elementos seleccionar.

Tendrás que decidir qué hacer cuando el polígono se intersecta (por ejemplo, figura-8).

Al construir el polígono, para evitar que obtenga demasiados puntos, tal vez puede omitir puntos que están demasiado cerca del punto anterior (tal vez 3 píxeles más o menos, dependiendo de su aplicación).

Fuente

2010-01-16 23:20:47 Thomas

Gracias, esto es exactamente lo que necesitaba. De la página de Wikipedia, encontré un recurso que muestra el código de muestra y las matemáticas detrás del problema: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html. Este algoritmo funciona bastante bien para mí, incluso puedo usar el algoritmo progresivamente a medida que el usuario selecciona una región con un rendimiento bastante bueno. Ahora estoy escribiendo algo de lógica para optimizar la frecuencia con la que se agregan puntos al polígono; no solo basado en la distancia entre el último punto sino también comparando las pendientes/diferencia en ángulos de los segmentos de línea previos. –

Estás viendo un problema de punto en el polígono: http://en.wikipedia.org/wiki/Point_in_polygon Si puedes garantizar que el polígono es convexo (no probable), el algoritmo se vuelve más simple.

Fuente

2010-01-16 23:21:29

Las selecciones de lazo generalmente no son necesariamente polígonos, pueden ser cualquier camino cerrado. En Photoshop, por ejemplo, está la herramienta Lazo y la herramienta Lazo poligonal. –

Un camino cerrado es un polígono, con una gran cantidad de puntos. El selector de Photoshop se puede optimizar más fácilmente debido a la cantidad finita de objetos en el polígono, y al hecho de que una unidad de polígono = un objeto. –

Para la herramienta de lazo a mano, puede tomar esta solución muy simple: guarde todos los puntos del borde de selección en un diccionario. Con x como clave y (y1, y2) como valor, donde y1 <= y2. Luego recorra todo x' y vea si hay una entrada en el dict. Si es así, todos los puntos, donde x' = x y y >= y1 and y <= y2, están en la selección.

Puede que no sea la mejor solución, pero debería funcionar.

Fuente

2018-01-31 12:47:27

Algoritmo para implementar una herramienta de selección de lazo?

Respuesta

Cuestiones relacionadas