larry@pylos.cchem.berkeley.edu (Raymond L. June) (07/11/90)
Hello,
I have a problem I'd like to see if has been solved before and
therefore appeal to this group for a little help. I have a point (call
it the origin) and a number of lines (not colinear) in the same plane.
What I'd like to compute is the smallest polygon formed from the
intersection of the aforementioned lines which encloses the origin.
The 'physics' of the problem says pretty strongly that the lines
will always 'surround' the origin so that I will be rendering a
closed polygon.
Anybody have an idea about some references? Of course, code would
be wonderful. Email or post - I'll summarize if interest is generated.
Thanks,
Larry June
+--------+-------------------------------------------------------------+
U.Snail: | Larry June, 201 Gilman Hall, Dept. of Chemical Engineering, |
| University of California, Berkeley, Berkeley CA 94720 |
ATT: | 415 642-5927 (worknet) 415 848-3705 (homenet) |
Internet:| larry@pylos.cchem.berkeley.edu or zeorlj@violet.berkeley.edu|
+--------+-------------------------------------------------------------+gordon@cs.tamu.edu (Dan Gordon) (07/11/90)
In article <1990Jul11.010350.10088@agate.berkeley.edu< larry@pylos.cchem.berkeley.edu (Raymond L. June) writes:
<
< I have a problem I'd like to see if has been solved before and
<therefore appeal to this group for a little help. I have a point (call
<it the origin) and a number of lines (not colinear) in the same plane.
<What I'd like to compute is the smallest polygon formed from the
<intersection of the aforementioned lines which encloses the origin.
<The 'physics' of the problem says pretty strongly that the lines
<will always 'surround' the origin so that I will be rendering a
<closed polygon.
For every line, consider the half-plane defined by the line and the
side on which the origin lies. What you are looking for is the
intersection of all these half-planes. This can be done in optimal
time theta(N log N) - see "Computational Geometry" by Preparata &
Shamos, Section 7.2.4, pp. 279-282.