Originally Posted by
Immortan
What about irregular shapes? What would be most efficient here? An idea that comes to mind is to just combine TBox objects and designate that as one area, but would this be efficient? I'll look into the libraries anyhow.
Checking if a point is in a polygon is a super interesting problem that a lot of people come up against
Give this a read: https://en.wikipedia.org/wiki/Point_in_polygon
Most people tend to stick to TBoxes (including combining a few as you suggested) for their areas. For our purpose you can generally get away with rectangular search areas. Of course the results using a TBox over a polygon are approximate, but again, generally accurate enough for our needs.
Edit: completely forgot about this but as Harrier mentions, take a look at SimbaExt (an include that provides some additional functions) and you can find implementations of the algorithms discussed in the wikipedia article above.
Code:
{*
Check if a point is within a polygon/shape by the given outline points (poly)
The points must be in order, as if you would draw a line trough each point.
@note: Ray casting combined with Winding number algorithm
*}
function InPoly(x,y:Integer; const Poly:TPointArray): Boolean; Inline;
var
WN,H,i,j:Integer;
RC:Boolean;
begin
WN := 0;
H := High(poly);
j := H;
RC := False;
for i:=0 to H do begin
if ((Poly[i].x = x) and (Poly[i].y = y)) then
Exit(True);
if ((poly[i].y < y) and (poly[j].y >= y) or (poly[j].y < y) and (poly[i].y >= y)) then
if (poly[i].x+(y-poly[i].y) / (poly[j].y-poly[i].y) * (poly[j].x-poly[i].x) < x) then
RC := Not(RC);
if (poly[i].y <= y) then begin
if (poly[j].y > y) then
if (((poly[j].x-poly[i].x)*(y-poly[i].y)-(x-poly[i].x)*(poly[j].y-poly[i].y)) > 0) then
Inc(WN);
end else
if poly[j].y <= y then
if (((poly[j].x-poly[i].x)*(y-poly[i].y)-(x-poly[i].x)*(poly[j].y-poly[i].y)) < 0) then
Dec(WN);
j := i;
end;
Result := (WN <> 0) or (rc);
end;
{*
Check if a point is within a polygon/shape by the given outline points (poly)
The points must be in order, as if you would draw a line trough each point.
@note: Ray casting algorithm
*}
function InPolyR(x,y:Integer; const Poly:TPointArray): Boolean; Inline;
var j,i,H: Integer;
begin
H := High(poly);
j := H;
Result := False;
for i:=0 to H do begin
if ((poly[i].y < y) and (poly[j].y >= y) or (poly[j].y < y) and (poly[i].y >= y)) then
if (poly[i].x+(y-poly[i].y) / (poly[j].y-poly[i].y) * (poly[j].x-poly[i].x) < x) then
Result := not(Result);
j := i;
end;
end;
{*
Check if a point is within a polygon/shape by the given outline points (poly)
The points must be in order, as if you would draw a line trough each point.
@note: Winding number algorithm
*}
function InPolyW(x,y:Integer; const Poly:TPointArray): Boolean; Inline;
var
wn,H,i,j:Integer;
begin
wn := 0;
H := High(poly);
j := H;
for i:=0 to H do begin
//if ((Poly[i].x = x) and (Poly[i].y = y)) then
// Exit(True);
if (poly[i].y <= y) then begin
if (poly[j].y > y) then
if (((poly[j].x-poly[i].x)*(y-poly[i].y)-(x-poly[i].x)*(poly[j].y-poly[i].y)) > 0) then
Inc(wn);
end else
if poly[j].y <= y then
if (((poly[j].x-poly[i].x)*(y-poly[i].y)-(x-poly[i].x)*(poly[j].y-poly[i].y)) < 0) then
Dec(wn);
j := i;
end;
Result := (wn <> 0);
end;
Source: https://github.com/WarPie/SimbaExt/b...e/CoreMath.pas