Polygon inside polygon
Tomas Berglund
tb at sm.luth.se
Mon Feb 7 21:38:04 PST 2005
Dear all,
Excuse me for not explaining what I mean with a "street". A street is a
simple polygon with two distinguished points s and g, which are located
on the polygon boundary and the part of the polygon boundary from s to g
is weakly visible to the part from g to s and vice versa. Thus, a street
is a polygon for which the two boundary chains from start to target are
mutually weakly visible.
Another version of the definition; On the edge of a simple polygon P we
select two points s (start) and t (target). These two points devide the
polygon P into two disjoint polygonal chains L (left) and R (right). L
is the polygonal chain starting at s following the edge of P clockwise
to t. R is the polygonal chain starting at s and following the edge of P
counterclockwise. P together with s and t is a street if and only if
each point on R can see at least one point on L and each point on L can
see at least one point on R. In this case L and R are said to be weakly
visible. Streets have some interesting properties. When walking along
any path contained in P that starts at s and ends at t, one will have
seen the complete edge of P, thus mapping all of P. Due to the
definition of streets, you can not have a part of the polygon -a cave-
that is not able to see the other side of the polygon.
Hence, the problem I am especially interested in is to decide whether a
street is inscribed in another street. Is there anyone who knows an
effective algorithm that solves this particular problem? What is the
complexity of the algorithm? Can we achieve faster algorithms when we go
from the more general problem of deciding whether a simple polygon is
inscribed in simple polygon to the problem of deciding whether a street
is inscribed in a street?
Thanks once again for your time, respectfully,
/Tomas
--
Tomas Berglund |Office: A3412|Cell.Ph. :+46 (0)706-770205
Div. Computer Science|URL:www.sm.luth.se/~tb|Home Ph. : +46 (0)920-68830
Lulea Univ. of Tech. |Ph.: +46 (0)920-492047|Home Adr.: Bruksvagen 1A
S-97187 LULEA/SWEDEN |Fax: +46 (0)920-492831| S-97594 LULEA/SWEDEN
-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce
mailing list