RE: Point inside a plygon?

• To: mathgroup at smc.vnet.net
• Subject: [mg25322] RE: [mg25239] Point inside a plygon?
• From: "David Park" <djmp at earthlink.net>
• Date: Sat, 23 Sep 2000 03:35:46 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

```Adriano,

Here is a different solution for the point inside a polygon question.

PointInPolygon::usage =
"PointInPolygon[point, polygonvertices] will determine if a point is \
within a polygon defined by its vertices. Its method is to calculate the \
cross product of each leg of the polygon with the vector from the base of
the \
leg to the point. If there is a change in sign of the z component going \
around the polygon, the point is outside the polygon.";

PointInPolygon[pt : {_, _}, polypoints : {{_, _} ..}] :=
Module[{pt3D, polypoint3D, case},
polypoints3D = PadRight[#, 3] & /@ polypoints;
polypoints3D =
polypoints3D = Partition[polypoints3D, 2, 1];
polypoints3D =
Sign[Dot[Cross[#\[LeftDoubleBracket]2\[RightDoubleBracket] - #\
\[LeftDoubleBracket]1\[RightDoubleBracket],
pt3D - #\[LeftDoubleBracket]1\[RightDoubleBracket]], {0, 0,
1}]] & /@ polypoints3D;
case = Which[
MemberQ[polypoints3D, 0], "on",
Length[Split[polypoints3D]] == 1, "inside",
True, "outside"];
SequenceForm["Point ", case, " polygon."]
]

Needs["Geometry`Polytopes`"]
polypoints = Vertices[Square]
{{0, 1}, {-1, 0}, {0, -1}, {1, 0}}

PointInPolygon[{0, 0}, polypoints]
"Point inside polygon."

PointInPolygon[{1, 1}, polypoints]
"Point outside polygon."

PointInPolygon[{1/2, 1/2}, polypoints]
"Point on polygon."

David Park

> -----Original Message-----
To: mathgroup at smc.vnet.net
> Hi,
>
> I need a routine to check if a point is inside or outside a polygon
> (simple polygon non self-intersecting).
> Any help appreciated.
>