Re: Interior of a polygon
- To: mathgroup at smc.vnet.net
- Subject: [mg28564] Re: [mg28543] Interior of a polygon
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Fri, 27 Apr 2001 03:56:19 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
I have not seen this done anywhere (but then this sort of thing is not
something I am an expert in) but I think can suggest one scheme. I do not at
this moment have the time to implement it as a Mathematica function or
package (and anyway, quite likely someone will offer a much better solution)
but I am pretty sure that doing so is fairly straight forward.
The scheme is as follows. If your polygon is convex you can start by
representing its interior as the set of points satisfying several linear
inequalities (obtained by finding the linear equations of the lines along
the sides of the polygon and replacing the == sign by > or <). You have to
be careful to correctly determine the sign you need to take but the
algorithm for that is clear. Once you have got your system of inequalities
you apply Experimental`CylindricalAlgebraicDecomposition to it. It will
represent the solution in cylindrical form which is suitable for applying
Table[{x,y},{x,a,b},{y,c[x],d[x]}. (Actually you need to apply Table several
times, once for each of the expressions ei in the output of
CylindricalAlgebraicDecomposition which will have the form Or[e1,e2,...en])
If your polygon is not convex than you need to represent it as a union of
convex polygons before applying the above method. One way would be to use a
package for triangulating non-convex polygons, for example the one due to
Martin Kraus which can be found on MathSource.
Of course there is also the most obvious "brute force method", which is
easier to implement but generally less efficient (I think!). All you need to
do is to find the smallest rectangular integer lattice containing your
polygon (a straight forward task) and then select from the list of points
within the lattice the ones lying within your polygon. This can be done
using one of the "point inside a polygon" criterion which was discussed
(with several implementations) on this list last year.
--
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
http://sigma.tuins.ac.jp/
on 01.4.26 8:21 AM, Mariusz Jankowski at mjkcc at usm.maine.edu wrote:
> Hello,
>
> I am trying to solve the following problem:
>
> Assume you are given a list of integer pairs (coordinates of points on a
> integer grid) denoting the border of a closed contour. I want a list of ALL
> the interior points (again, in the form of integer pairs).
>
> Thanks for any suggestions, solutions, etc. References to literature are
> also welcome. Please cc my email if posting to newsgroup.
>
> Mariusz
>
>
> ======================================================
> Mariusz Jankowski
> University of Southern Maine
> mjkcc at usm.maine.edu
>
>
>
>