| If you know (somehow) that you have a fence, can't you extend
the odd-even algorithm to count mod 4, to tell you whether
your point is inside it?
If the final count is 1 or 3, you're "within the wall".
If the final count is 0, you're outside the fence.
If the final count is 2, you're inside the fence.
You need to be careful with the boundary cases, just as for
the normal odd-even algorithm.
|
| Thank you!
I think that will do it...
We expect fence areas to be generally well-behaved...so to test that an area
is a fence, I anticipate that it will be okay to locate areas that have any
segments overlapping or intersecting other segments within the same area.
Thanks again,
-- Eric
|
| (0) With respect, I don't think that the "solution" in .1 works
Just take the example fence given in .0, and draw a line to the
centre starting from approximately the South-West corner. The line will
cross the boundary 4 times, and yet the region in the centre is meant to
be "inside" the fence.
(1) Clarification of problem statement needed.
A closed curve comprising a finite number of straight line segments
partitions the plane into a finite number of regions. All but one of these
regions is a polygon of finite area. The other region (the "outside")
is of infinite area.
.0 tries to define the notion of a fence, distinguishing between
polygons which are "inside" and polygons which are "in the wall". The
definition given of a "fence" is descriptive rather than prescriptive and is
actually circular! :-)
For instance: are the following intended to be examples of fences:
A B C
+----+----+
| / \ |
| D< >E |
| \ / |
+----+----+
F G H
(a) if the closed path is A-B-E-G-H-C-B-D-G-F-A?
(b) if the closed path is A-B-D-G-H-C-B-E-G-F-A?
Anyway, I don't think that's too important. Your basic problem seems
to be identifying those points which are outside. I will leave it to you to
decide which of the other points are inside vs in the wall.
(2) A solution to Part 2.
What you need to do is to remove all the interior edges (e.g.: BD,
BE, DG & EG in the above picture). Then you just apply the odd/even argument
to the edges that remain.
There is a simple way to do this. First find a point on the perimeter
of the shape. Then trace round, identifying all the line segments that you
pass along. To be more formal...
Let p_i = (x_i,y_i) be points for i = 0...n. Specify that p_0 & p_n are
the same. Let A->B be the notation for the directed line segment linking
point A to point B. Let l_i = p_(i-1)->p_i. Then the set of n l_i defines the
closed curve that we are interested in.
Let x = min(x_i) over i. Let X = max(x_i) over i. Similarly define y
and Y. Let d be very small. Then K = (x-d,y)->(X+d,Y) will cross the closed
curve. Find the intersection between K and l_i for each i at point Z_i. Find
the nearest of the Z_i to (x-d,y). Call it Q_0. That is our starting point on
the perimeter.
Q_0 lies on some line segment l_j(0). Find the intersection point
between each l_i and (Q_0,p_j(0)). At least one such point must exist. Find
the nearest of these intersection points to Q_0. Call that point Q_1.
Q_1 lies on some l_j(1). Find the intersection point between each
l_i and (Q_1,p_j(1)). The nearest one to Q_1 is Q_2.
Just iterate this to get Q_3,...Q_m, until you come back to Q_0. Then
the Q_k define the outline of the fence, and you can use the odd/even argument
to find out whether any point lies outside the shape.
Hope this is of use in your work,
Cheers,
Andrew.
|