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 > > > >