Re: Interior of a polygon
- To: mathgroup at smc.vnet.net
- Subject: [mg28767] Re: Interior of a polygon
- From: "Mariusz Jankowski" <mjkcc at usm.maine.edu>
- Date: Fri, 11 May 2001 20:00:45 -0400 (EDT)
- Organization: University of Southern Maine
- References: <9d85uu$862@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Thank you to all who responded!
Andrzej's suggestion to use a polygon triangulation package by Martin Kraus
immediately led me to a solution, since I already had a solution for convex
polygons. However, in the meantime, Alan quickly came up with a solution
that does not require an explicit triangulation step (see his earlier post).
It works and is faster than the example I will show below. Therefore the
only reason I am demonstrating an alternative solution is that it may be
easier for most to understand.
Sincerely, Mariusz
Load PolygonTriangulation package.
<<PolygonTriangulation`SimplePolygonTriangulation`
The following code finds all points along the border of a polygon:
borderPoints[v:{{_, _}..}] :=
Union[Join @@ getPoints /@ Partition[v, 2, 1, 1, v]]
getPoints[{{a_, b_}, {c_, d_}}] :=
Transpose[If[Abs[a - c] >= Abs[b - d],
({#1, Round[Interpolation[{{a, b}, {c, d}},
InterpolationOrder -> 1] /@ #1]} & )[
Range[a, c, If[a <= c, 1, -1]]],
({Round[Interpolation[{{b, a}, {d, c}},
InterpolationOrder -> 1] /@ #1], #1} & )[
Range[b, d, If[b <= d, 1, -1]]]]];
Given the function borderPoints the interior (and border) points of a convex
polygon can be obtained using the following:
regionPointsConvex[v:{{_, _}..}] := Join @@ fillPoints /@
findExtremalPoints[ borderPoints[v]];
findExtremalPoints[pts:{{_, _}..}] := ({#1[[1]], #1[[-1]]} & ) /@
Split[pts, #1[[1]] === #2[[1]] & ];
fillPoints[{{x_, y0_}, {x_, y1_}}] := ({x, #1} & ) /@ Range[y0, y1];
To find the points in any simple polygon use:
regionPoints[v:{{_, _}..}] := Union @@ regionPointsConvex /@ (v[[#1]] & ) /@
SimplePolygonTriangulation[v]