Q E P C A D - 2D Adjacency Documentation


I'm trying to build an adjacency algorithm for 2D CAD's which will work quickly and be easy to implement. I won't guarantee a solution, but I will guarantee that any solution given is correct. When adjacencies cannot be decided, the algorithm will enumerate the possible adjacencies so that a future extension could use other methods to make these decisions.

The real world -- Partial CAD's and Infallible adjacency

There are two problems that my adjacency method can encounter: in a partial CAD we might not have constructed all of the three adjacent stacks we need for my adjacency method, and in some situations this method fails to provide a unique adjacency assignment, and a decision muct somehow be made between the several alternatives it returns.

In the case of a "missing" stack, i.e. a stack which has not been constructed but which is needed by my adjacency method, I take the easy way out: I simply construct the stack. The missing stack will always be a stack over an open interval, so the time required for constructing that stack should b pretty small. Another alternative would be a modified algorithm which deals with two adjacent stacks and not three. The function which determines adjacencies in any situation is:

L <- ADJ_2D(_PARTc,c_l,c_r,P,J)
It calls:
to construct missing stacks. To decide between multiple possible adjacency assignments it uses: