El algoritmo se basa en aplicar una línea horizontal desde el punto de control y comprobar cuantas veces se corta con las aristas del polígono. Si el resultado es un número impar significa que el punto se encuentra en el interior, si es par significa que está fuera.
En este código se controla también la posibilidad de que el punto se encuentre justo en alguna de las aristas, en ese caso también o da como punto interno.
Cuando necesites saber si un punto se encuentra dentro de un polígono, definido por sus vértices, puedes utilizar el siguiente código.
/// <summary>
/// Establece si un punto se encuentra en el interior de un polígono.
/// </summary>
/// <param name=”vertex“>Lista de puntos que componen el polígono</param>
/// <param name=”pt“>Punto a verificar</param>
/// <returns></returns>
public static bool InternalPoint (List<Point3D>vertex, Point3D pt, int precision)
{
try
{
// Primera comprobación. Verificar si el punto se encuentra en alguna de las aristas
List<line> edges = CalculeEdges(vertex); // Obtenemos las aristas del polígono para probar
foreach (line edge in edges)
{
if (PointInLine(pt, edge.StartPoint, edge.EndPoint, precision))
{
return true; //Si está en la línea lo damos por interno. no hace falta seguir
}
}
// Segunda comprobación. Verificar si el punto se encuentra dentro de la caja
// de abarque del polígono.
Point3D minPt = new Point3D();
Point3D maxPt = new Point3D();
if (!BoundBox(vertex, ref minPt, ref maxPt))
{
return false; // falló la obtención de las coordenadas de la caja
}
// Solo operaremos si el punto se encuentra entre las coordenadas mínima y máxima
if (pt.x > minPt.x && pt.y > minPt.y && pt.x < maxPt.x && pt.y < maxPt.y)
{
// Trazamos una línea horizontal hasta el límite de la caja de abarque
line nl = new line(pt, new Point3D(minPt.x, pt.y, 0));
// Declaramos una lista de puntos para almacenar las intersecciones obtenidas
List<Point3D> ListInts = new List<Point3D>();
// Ahora comprobamos la cantidad de intrsecciones que se producen con las aristas
foreach (line edge in edges)
{
Point3D ptInters = Inters2D(nl.StartPoint, nl.EndPoint, edge.StartPoint, edge.EndPoint);
if (ptInters != null)
{
// Comprobamos que no haya puntos duplicados. Eso ocurriría si la proyección
// del punto coincidira con un vértice
if (!ListInts.Contains(ptInters))
{
ListInts.Add(ptInters);
}
}
}
// Ya se han comprobado todas las intersecciones.
// Vamos a resolver el problema.
return (ListInts.Count > 0) && ((ListInts.Count % 2) != 0);
// Si el número de intersecciones es impar significa que está dentro
// En caso contrario o si no hay intersecciones significa que está fuera.
}
else
{
return false;
}
}
catch (Exception ex)
{
MessageBox.Show(“Error:” + Environment.NewLine + ex.Message, “Test”,
MessageBoxButtons.OK, MessageBoxIcon.Error);
return false;
}
}
Para ponerlo a prueba puedes escribir una función parecida a la siguiente:
private void puntoInternoToolStripMenuItem_Click(object sender, EventArgs e)
{
List<Point3D> pts = new List<Point3D>();
pts.Add(new Point3D(10, 5, 0));
pts.Add(new Point3D(10, 10, 0));
pts.Add(new Point3D(12.5, 10, 0));
pts.Add(new Point3D(15, 12.5, 0));
pts.Add(new Point3D(17.5, 12.5, 0));
pts.Add(new Point3D(17.5, 5, 0));
pts.Add(new Point3D(15, 5, 0));
pts.Add(new Point3D(15, 7.5, 0));
pts.Add(new Point3D(12.5, 5, 0));
Point3D pt = new Point3D(12, 6.5, 0);
// Prueba con el punto interno
if (MyClase.InternalPoint(pts, pt, 2))
{
MessageBox.Show(“El punto está dentro”, “Test”,MessageBoxButtons.OK, MessageBoxIcon.Information);
}
else
{
MessageBox.Show(“El punto está fuera”, “Test”,MessageBoxButtons.OK, MessageBoxIcon.Information);
}
// Otra prueba con el punto fuera
pt = new Point3D(18.5, 6.5, 0);
if (MyClase.InternalPoint(pts, pt, 2))
{
MessageBox.Show(“El punto está dentro”, “Test”,MessageBoxButtons.OK, MessageBoxIcon.Information);
}
else
{
MessageBox.Show(“El punto está fuera”, “Test”,MessageBoxButtons.OK, MessageBoxIcon.Information);
}
}
La prueba está basada en el siguiente caso:
Ponlo a prueba, piensa en cómo mejorarlo y comparte con nosotros tus progresos.