Estoy buscando un algoritmo que pueda determinar si una superficie en $\mathbb{R}^3$ es cerrado (el volumen está acotado). No estoy familiarizado con el campo, así que no estoy seguro de que esto sea factible en general. Más concretamente, tengo primitivas como bolas, semiespacios, cuádricas, etc. y construyo nuevas primitivas a partir de ellas mediante operaciones de conjunto (intersección, complemento), también conocidas como CSG (geometría sólida constructiva). Busco clasificar las primitivas resultantes como acotadas o no. Por ejemplo, considero que un semiespacio no está acotado, mientras que una bola está acotada. El principal problema es que se pueden construir primitivas acotadas a partir de otras no acotadas (una caja formada por la intersección de medios espacios), pero al mismo tiempo se pueden construir primitivas no acotadas. Me doy cuenta de que mi problema posiblemente no esté muy bien definido, pero no estoy seguro de qué otras restricciones tendrían sentido para hacerlo factible. Así que estoy buscando cualquier cosa realmente, incluso si no se aplica específicamente a la formulación exacta del problema anterior, siempre y cuando pueda clasificar alguna clase de primitivos como acotados no acotados.
Respuesta
¿Demasiados anuncios?
Radost
Puntos
166
Para las desigualdades lineales se puede reducir el problema de la acotación a un problema de programación lineal. Cf. wiki .
Existen múltiples implementaciones de este algoritmo que funcionan. Te interesaría comprobar si el problema es "factible" para un vector objetivo no perpendicular a ninguno de los planos delimitadores. (Lamentablemente, en general este algoritmo puede ser bastante lento).
