Un polígono simple, o polígono de Jordan, define un interior y un exterior (véase el artículo ¿Qué es un polígono?). ¿Qué algoritmo permite determinar si un punto del plano está en el interior o en el exterior del polígono? Esta pregunta parece trivial para un polígono no demasiado complicado, como el de la figura siguiente:
Al cerebro humano le basta un cuarto de segundo para decirnos que el punto M está en el interior del polígono, mientras que el punto N está en el exterior. Pero ¿cómo hacerlo mediante un algoritmo? Esta cuestión es recurrente en los sistemas de información geográfica, las interfaces gráficas, la infografía, los sistemas de diseño asistido por ordenador y los sistemas de robótica. Además, hay casos más complejos en los que el ojo puede ser engañado.
El polígono es efectivamente simple, pero ¿está el punto M en el interior o en el exterior del polígono?
El método de «cruce de rayos» ---------------------------------
El algoritmo más sencillo para determinar si un punto está dentro de una región es el método de cruce de rayos, surgido de los trabajos de los cartógrafos Stig Nordbeck y Bengt Rystedt en 1967. Consiste en trazar una recta que pase por el punto cuya posición queremos conocer. A continuación, partiendo del exterior, se cuenta el número de intersecciones con el polígono. Siempre que ese número es impar, estamos en el interior del polígono. El uso de una recta horizontal o vertical permite simplificar los cálculos.
Este algoritmo es sencillo de implementar. Hay que tener cuidado cuando la recta pasa por un vértice. Si el punto que se desea identificar está muy cerca de un lado, también puede plantear problemas. Existen numerosos refinamientos de este algoritmo, muy utilizado, para reducir su complejidad computacional.

El punto M está en el interior del polígono porque la semirrecta

corta el polígono un número impar de veces.