Re: Interior of a polygon
- To: mathgroup at smc.vnet.net
- Subject: [mg28682] Re: [mg28543] Interior of a polygon
- From: Andrzej Kozlowski <andrzej at tuins.ac.jp>
- Date: Tue, 8 May 2001 02:51:17 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
I have found a little time to implement the solution to Mariusz Jankowski's
problem which I sketched in an earlier posting in reply to his original
message. It only works for convex polygons but can be easily extended to all
by means of Martin Kraus' Polygonal trianulation package. The main be bugs
because I have tested only for a single polygon (given below). The only
improvement on the original idea which I described is to use the
GenericCylindricalAlgebraicDecomposition instead of
CylindricalAlgebraicDecomposition, which ought to make the function much
faster.
Here is my function:
<<<< Experimental`
PointsInsidePolygon[poly_List] :=
Module[{ineq,
rule1 = {Less[a_, x_, b_] :> {x, Ceiling[a], Floor[b]},
Inequality[a_, Less, x_, Less, b_] :> {x, Ceiling[a], Floor[b]}},
rule2 = {{u_, w_} :> Table[{x, y}, u, w]}},
ineq[{{a_, b_}, {a_, d_}, {e_, f_}}] := If[e > a, x > a, x < a];
ineq[{{a_, b_}, {c_, d_}, {e_, f_}}] :=
If[f > ((d - b)/(c - a))(e - a) + b, y > ((d - b)/(c - a))(x - a) + b,
y < ((d - b)/(c - a))(x - a) + b];
Complement[
Join @@ Join @@ (((List @@@
First[GenericCylindricalAlgebraicDecomposition[
Map[ineq, Partition[poly, 3, 1, {1, 1}]], {x,
y}]]) /. rule1) /. rule2), poly]]
Note that the argument is a list of vertices in which the first and last are
not the same (in other words you do not repeat the starting vetex).
Here is an example:
polyg = {{1, 3}, {2, 5}, {4, 4}, {5, 2}};
In[55]:=
pts=PointsInsidePolygon[polyg]
Out[55]=
{{2,3},{2,4},{3,3},{3,4},{4,3}}
In[56]:=
s1=Graphics[{RGBColor[1,0,0],Polygon[polyg]}];
In[57]:=
s2=Graphics[{PointSize[0.02],Point[#]}&/@pts];
In[58]:=
Show[s1,s2]
Andrzej Kozlowski
Toyama International University
JAPAN
http://platon.c.u-tokyo.ac.jp/andrzej/
http://sigma.tuins.ac.jp/~andrzej/