dwu@alcor.usc.edu (07/10/90)
I'm very new to and computer graphics, so if I can elicit some help for this
following problem, I'd appreciate it. Here it goes:
Suppose in our program, we represent all polygons by their vertices.
Eg, for a rectangle, we need only list its 4 vertices
(0,2) (4,2)
. .
(0,0) (4,0)
. .
Let's further suppose that we allow polygons to have "holes", where holes
are themselves polygons inside an outer polygon.
A
+----------------------------+
| |
| B |
| +------------+ |
| | | |
| | | |
| | | |
| +------------+ |
| |
+----------------------------+
Here polygon A is the outer polygon, while polygon B is the hole. To
represent a polygon with a hole we can do the obvious thing and simply list
2 sets of vertices: the outer polyon and the hole(s). (A polygon can have
multiple holes).
Now here's the rub. Let's suppose that our database or our data structure
does not permit keeping track of 2 sets of polygons (Eg, the CALMA layout
system does not), and in order to draw that polygon with a hole, we have to
insert a "false edge" C, and pretend that there is only 1 polyon.
A
+---------------------------+
| C / |
| / |
| B / |
| +------------+ |
| | | |
| | | |
| | | |
| +------------+ |
| |
+---------------------------+
I'll split that false edge into 2, and draw arrows so that we can see how we
traverse this single polygon:
A
+---<-------<-------<--- + +
| / /|
| ^ / |
v B / / |
| +---->------+ v ^
| | + |
| ^ | |
v | V ^
| +-------<----+ |
| |
+----->--------->-----------+
No doubt this reminds us of those complex analysis problems, when we took
contour integrals to integrate an anullus.
Basically, we have collapsed the polygon and hole into a single polygon.
Challenge to the net: Can you come up with an algorithm that inserts false
edges so that all polygons with holes are collapsed into a single polygon?
Let me elaborate a little on this.
My preliminary thoughts were these:
STEP 1. 2 holes can be made into 1 hole by insertion of a false edge
between them
+----------------+=========+--------------------+
| | | |
| | | |
| | | |
| | | |
| | | |
+----------------+ +--------------------+
So by induction, any n holes can be made into 1 big hole by false
edge insertion.
STEP 2. Finally, 1 hole and an outer polygon can be made into 1 polygon
by insertion of a false edge, as seen above.
Thus an algorithm can be based on these 2 facts. Or so I thought.
There are some details that I neglected:
RULE I. If at all possible, we want the false edge insertion to span
from vertex to vertex. Ie, a false edge between the middles of 2
vertices should be avoided.
+-----------------++-------------------+
| || |
| || |
| +----------++----------+ |
| | | |
| | | |
| | | |
| | | |
| +----------------------+ |
| |
+--------------------------------------+
The reason why is because we would have to implant a "false vertex"
into each of the 2 polygons in order to represent this false edge.
We would have to disturb each original polygon in order to do this,
and at a later time when we want to remove all the false edges, we
must also remove the false vertices as well. It just makes the
problem ever more complicated.
RULE II. False edge insertions cannot cross any hole or the outer polygon or
another false edge.
Eg, things like these are prohibited:
+----------------------------+
| \ +----+ |
| \| | | Can't cross segments of
| |\ | | another hole
| +--\-+ |
| \ +-----+ |
| \ | | |
| \ | | |
| +-----+ |
+----------------------------+
+-------------+
| |
| +----+ | Can't cross segments of
| +----+ | outer polygon
| \ |
| +----\-+
| | \
| | \
| +-------+
| |
| |
+--------------+
Can't cross another false edge
+-------------------------------+
| |
| +-------+ +------+ |
| | | | | |
| +-------+ +------+ |
| \ / |
| \ / |
| / \ |
| / \ |
| +-------+ +------+ |
| | | | | |
| +-------+ +------+ |
| |
+-------------------------------+
We note that inductive STEP 1 above may be impossible, if we obey RULES I, II.
Eg, there is no way to place a false edge between the 2 holes' vertices
without violating RULES I or II here:
+-----------------------+
| +-----+ |
| | | |
| +-----+ |
| |
| +----------------+
| |
| |
| +----------------+
| |
| +-----+ |
| | | |
| +-----+ |
+-----------------------+
So perhaps I should abandon STEP 1 altogether, and simply try to insert false
edges between every hole and the outer polygon?
That won't work either.
+
/ \
/ \
/ \
/ +--+ \
/ | | \
/ +--+ \
/ \
/ +--+ \
/ | | \
/ +--+ \
/ +--+ +--+ \
/ | | | | \
/ +--+ +--+ \
+--------------------------------------------------+
I didn't draw that too well, but you get the idea. We can construct a polygon
with holes such that trying to connect every hole to the outer polygon violates
RULE II (false edges would cross each other).
Now I'm stumped. This strikes me as more of a routing problem. (Ie channel
definiton and ordering in VLSI routing), but I'm afraid I don't know enough
about it to go on.
If anybody has any ideas, or can recommend a text please email me.
Thank you,
Daniel
dwu@castor.usc.edu