Алгоритм точки в полигоне (с отверстиями) ⇐ C++

[Anonymous]

Я работаю над дополнением к программному обеспечению САПР, и мне нужно было решение, позволяющее узнать, находится ли точка внутри многоугольника или нет. Я нашел несколько хороших решений здесь (ссылка), но ни одно из них не сработало, когда в многоугольнике были дыры! Я понял это, поэтому хочу поделиться кодом, если он кому-нибудь понадобится.

Код: Выделить всё

struct Point2D
{
double x;
double y;
};

struct PolygonData
{
std::vector
 coords;  // list of 2d coordinates, coordinates are duplicated for the end-nodes for each subcontour!
// for example a triangle: (1) 0,0; (2) 1.2,3.5; (3) 2.4,7.7; (4) 0,0;
int nSubPolys;                // number of polyongs, the first is always the main polygon
std::vector pends;       // contour ends, indicates the vertices which are closing the subcontours
};

bool IsPointInsidePolygon(const Point2D& p, const PolygonData& polygonData)
{
double minX = 0.0;
double maxX = 0.0;
double minY = 0.0;
double maxY = 0.0;

for (int i = 0; i < polygonData.pends[1]; i++)
{
minX = std::min(polygonData.coords[i].x, minX);
maxX = std::max(polygonData.coords[i].x, maxX);
minY = std::min(polygonData.coords[i].y, minY);
maxY = std::max(polygonData.coords[i].y, maxY);
}

if (p.x <  minX || p.x > maxX || p.y <  minY || p.y > maxY)
return false;

// check main polygon
bool inside = false;
for (int i = 0, j = polygonData.pends[0] - 1; i < polygonData.pends[0]; j = i++)
{
if ((polygonData.coords[i].y > p.y) != (polygonData.coords[j].y > p.y) &&
p.x < (polygonData.coords[j].x - polygonData.coords[i].x) * (p.y - polygonData.coords[i].y) /
(polygonData.coords[j].y - polygonData.coords[i].y) + polygonData.coords[i].x)
{
inside = !inside;
}
}

// check subpolygons too if point is inside main polygon
bool subInside = false;
if (inside == true && polygonData.nSubPolys > 1)
{
int ind = 0;
int prevPolySize = polygonData.pends[0];
int actPolySize = 0;

// skip 1st, because its the main polygon himself
for (int ii = 2; ii  

Подробнее здесь: [url]https://stackoverflow.com/questions/78409174/point-in-polygon-with-holes-algorythm[/url]