Get the horizon for a point during incremental Convex Hull 3D

Question

I'm implementing incremental CH 3D in c++ with qt, but I can't overcome this problem:

I have to find the view horizon of a given point:

I have a Map with the list of all visible faces of a given point "pr", but i don't know how to get only the horizon without changing algorithm complexity (it's O(nlogn)).

My idea was: for all visible faces' edge, check if the twin's incident face is visible or not. If it's not visible then add it in the horizon edge list, but this change algorithm's complexity (I think).

Note that I have another list where I have the set of all points that can view a given face (maybe it helps).

Really thanks in advance

Answer 1

If you have convex polytopes, only , your idea should do it (It's complexity is O(1), you already have the results). Yep, you would do an extra lookup with complexity O(n).