4
$\begingroup$

Is there an algorithm to construct a polyhedron containing all points in space for which there exists no ray to infinite not intersecting a given polyhedron?

In 2D, we could consider polygons. For example, we have an input polygon on the left with "critical visibility rays"(?) in dashed lines and the expected output polygon on the right (with original, dashed).

polygon and visibility hull

An possibly easier problem is just determining whether input is the output: whether all points on the input can see infinity. To solve that, it seems I'd need an algorithm to determine whether there exists an unobstructed line of sight between two line segments:

line segment visibility

That is, whether a line segment exists connecting any point on one segment to any point on the other without intersecting a given polygon.

I'm really interested in the construction problem, though. And really, I'm interested in 3D where topology problem starts to come into play more.

This seems related to a previous question, a reference is given but I couldn't find a direct solution.

Seems the solution (for the 2D problem) might be lurking in "Linear time algorithms for visibility and shortest path problems inside simple polygons" [Guibas et al. 1986], but I'm failing to see how to put this together into a full solution to my problem, and then how to extend to 3d.

Improve this question
$\endgroup$
1
  • $\begingroup$ As you know from the previous question to which you link, these shapes are called weakly externally visible in the literature. $\endgroup$
    – Joseph O'Rourke
    May 8, 2015 at 0:00

2 Answers 2

Reset to default
5
$\begingroup$

The set of points that can't see out to infinity around a three-dimensional polyhedral obstacle is not itself a polyhedron.

In general, its boundary surfaces will be patches of hyperboloids, curved surfaces through triples of obstacle edges that contain all trisecant lines to those three edges. It should be possible to construct the set you want in polynomial time, despite its curved boundaries, by forming arrangement of all such hyperboloids and testing for each cell in the arrangement whether or not it can see to infinity, but it's not going to be very efficient and it's also likely to be somewhat difficult to implement correctly using exact arithmetic.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Whoa. OK, that's very useful. It's at least a polygon for the 2D case, correct? $\endgroup$
    – Alec Jacobson
    May 8, 2015 at 15:34
  • $\begingroup$ In 2d, yes, it is. $\endgroup$
    – David Eppstein
    May 8, 2015 at 15:59
2
$\begingroup$

Permit me to suggest examining the literature on the visibility complex, starting from the original Pocchiola and Vegter 1996 paper,1 and its subsequent variations, including extensions to 3D.2

            DurandFig2
The visibility complex in 2D can be viewed as a cell complex representing "a partition of the set of maximal free [line-of-sight] segments according to the object they touch." I believe that computing this complex would permit you to extract the "weakly externally visible" polygon/polyhedron you seek.

1 M. Pocchiola and G. Vegter. The visibility complex. Internat. J. Comput. Geom. Appl., 6(3):279-308, 1996.

2 Durand, Frédo, George Drettakis, and Claude Puech. "The 3D visibility complex." ACM Transactions on Graphics (TOG) 21.2 (2002): 176-206. (Google Scholar records subsequent citations by 79 papers.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.