¿Alguien sabe una manera de hacer una ordenación rápida con trivalued lógica?
El problema que estoy tratando de resolver es este: estoy tratando de mostrar una vista de un complejo de objetos 3d a partir de un determinado ángulo de visión. He roto el objeto en muchas superficies 2d que puedo dibujar por separado, pero para mostrar la imagen correctamente, necesito determinar el orden z de la superficie – un clásico del dibujo en el ordenador de problema. Se garantiza que ninguna de las superficies se cruzan, por lo que el problema es solucionable. Sería sencillo si en la comparación de las dos superficies, siempre se podía determinar que uno es en la parte delantera – un simple mergesort sería suficiente. Pero muy a menudo, si puedo comparar dos superficies, se verá que, con el ángulo que estoy viendo, no hay coincidencia en todos los. Una superficie es más de aquí, y el otro de la superficie es de allí, así que es imposible decir que uno está en frente.
En términos matemáticos, lo que yo estoy tratando de hacer es ordenar un conjunto de entidades, a llamar a, b, c, etc. La transitividad es garantizado: Si a < b es verdadera y b< c es verdadera, entonces a < c es siempre cierto. Pero el factor que complica la situación es el trivalued lógica: a < b podría ser desconocido. Una consecuencia de ello es el final de la lista ordenada puede contener pequeños conjuntos de elementos dentro de la cual el orden no importa, por ejemplo. El resultado puede ser un < (b, c) < d, etc.
Tenga en cuenta que incluso si a < b es desconocido, otras comparaciones que pueden obligar indirectamente a un cierto orden de a, b. Por ejemplo. Si a < b es desconocida, pero resulta que a < c = true y b < c es falsa, entonces el orden debe ser a < c < b.
Me puede resolver el problema con una especie de burbuja, pero que malo, porque O(N^2) comparaciones, y cada comparación es muy caro (ya que consiste en averiguar si dos superficies pueden bloquear cada uno de los otros cuando se ve desde un cierto ángulo). Es allí una manera de resolver esto con un rápido tipo? (por ejemplo. Algunos de adaptación de un mergesort)?
