Editing Point in polygon (section)

==Point in polygon queries==
The point in polygon problem may be considered in the general repeated [[geometric query]] setting: given a single polygon and a sequence of query points, quickly find the answers for each query point. Clearly, any of the general approaches for planar [[point location]] may be used. Simpler solutions are available for some special polygons.

===Special cases===

{{expand section|date=August 2013}}

Simpler algorithms are possible for [[monotone polygon]]s, [[star-shaped polygon]]s, [[convex polygon]]s and [[triangle]]s.

The triangle case can be solved easily by use of a [[barycentric coordinate system]], [[parametric equation]] or [[dot product]].<ref>[https://totologic.blogspot.com/2014/01/accurate-point-in-triangle-test.html Accurate point in triangle test] "''...the most famous methods to solve it''"</ref> The dot product method extends naturally to any convex polygon.