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/