Ray Tracing for Points in a Polygon

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

This Demonstration uses the ray tracing method to determine whether points on a plane lie inside or outside a given polygon.

Contributed by: Raja Kountanya (June 2016)
Open content licensed under CC BY-NC-SA


Snapshots


Details

In computational geometry, there is a classical problem of partitioning a set of points in 2D into those enclosed by a polygon and those outside. Currently, the best known way is a ray-tracing method, in which a ray is drawn from a candidate point in the positive direction and the number of intersections with the polygon is counted. If the number is odd, the point is inside, if it is even, it is outside.

In this Demonstration, starting with a simple triangle, you can add vertices to a polygon and drag them to see how the points are classified to be inside (green) or outside (red). Notice, however, that the ordering of the vertices is important, since the polygon is shaped by both position and ordering of the vertices.

References

[1] Wikipedia. "Point in Polygon." (Jun 1, 2016) en.wikipedia.org/wiki/Point_in_polygon.

[2] R. Kountanya. "Ray Tracing for Point in Polygon Problem" from Wolfram Library Archive—A Wolfram Web Resource. (Jun 1, 2016) library.wolfram.com/infocenter/MathSource/7780.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send