Recent

Author Topic: Inpolygon function  (Read 1307 times)

BobDog

  • Sr. Member
  • ****
  • Posts: 394
Inpolygon function
« on: May 21, 2023, 02:39:25 pm »
Might be of some use, a raw inpolygon function using an array of points to form a polygon.
Example:
Code: Pascal  [Select][+][-]
  1.  
  2. {$mode fpc}
  3. {$RANGECHECKS ON}
  4. uses
  5. sysutils,ptcGraph,ptcCrt,math;
  6.  
  7.  
  8. Type PointF=object
  9. x,y:double;
  10. End;
  11.  
  12.  
  13. type aop=array of PointF;
  14.  
  15. function rgb(r,g,b:smallint) :longword;
  16.    begin
  17.    exit(((r Shl 16) Or ((g) Shl 8) Or (b) Or $FF000000)- $FF000000)
  18.    end;
  19.  
  20.  
  21. Function inpolygon(const p1:aop;const mx,my:double):boolean;
  22.  
  23. function Winder(L1,L2,p:PointF):integer;
  24. begin
  25.   exit (-Sign((L1.x-L2.x)*(p.y-L2.y)-(p.x-L2.x)*(L1.y-L2.y)));
  26. end;
  27.  
  28. var
  29. index,nextindex,wn,k,n:integer;
  30.  const p2:pointf=(x:0;y:0);
  31.     begin  
  32.              p2.x:=mx;p2.y:=my;      
  33.              k:=length(p1);
  34.              wn:=0;
  35.             For n :=0 To high(p1) do
  36.             begin
  37.                 index:=n Mod k;nextindex:=(n+1) Mod k;
  38.                 If (p1[index].y<=p2.y) Then
  39.                     If (p1[nextindex].y>p2.y) And  (Winder(p1[index],p1[nextindex],p2)>0) Then wn:=wn+1;
  40.                 If (p1[index].y>p2.y) Then
  41.                     If (p1[nextindex].y<=p2.y) And (Winder(p1[index],p1[nextindex],p2)<0) Then wn:=wn-1;
  42.             end;
  43.             exit( boolean(wn));
  44.      End;
  45.        
  46.   procedure swap(var a, b: longword);
  47.       var temp: longword;
  48.      begin
  49.      temp := a; a := b; b := temp;
  50.    end;
  51.        
  52.  function circulate(var p:aop):pointF;
  53.        procedure swap(var a, b: pointF);
  54.        var temp: pointF;
  55.      begin
  56.      temp := a; a := b; b := temp;
  57.      end;
  58.    
  59.     var
  60.     p1,p2,i:integer;
  61.     c:pointF;
  62.  begin
  63.     c.x:=0;c.y:=0;
  64.    for i:=0 to high(p) do
  65.     begin
  66.     c.x:=c.x+p[i].x;
  67.     c.y:=c.y+p[i].y;
  68.     end;
  69.     c.x:=c.x/length(p);
  70.     c.y:=c.y/length(p);
  71. For p1 := 0 To high(p)-1 do
  72.     begin
  73.     For p2 := p1 + 1 To high(p) do
  74.       begin
  75.         if arctan2(p[p1].y-c.y,p[p1].x-c.x)< arctan2(p[p2].y-c.y,p[p2].x-c.x) then
  76.          begin
  77.             swap (p[p1],p[p2]);
  78.          end;
  79.        end;
  80.      end;
  81.          exit(c);
  82. end;
  83.  
  84.    function range(mymin:int64;mymax:int64):int64;
  85.          begin
  86.       exit(trunc(int((Random*(Mymax-mymin+1)))+MyMin));
  87.    end;
  88.  
  89.     procedure drawpolygon(ret:aop;linecol:longword);
  90.     var
  91.     n:integer;
  92.     getc:longword;
  93.     begin
  94.     getc:=getcolor;
  95.     setcolor(linecol);
  96.     circulate(ret);
  97.     for n:=0 to high(ret)-1 do
  98.     line(trunc(ret[n].x),trunc(ret[n].y),trunc(ret[n+1].x),trunc(ret[n+1].y));
  99.     line(trunc(ret[high(ret)].x),trunc(ret[high(ret)].y),trunc(ret[0].x),trunc(ret[0].y));
  100.     setcolor(getc);
  101.     end;
  102.    
  103.   function rainbow( x:single):longword;
  104.     const pi=4*arctan(1);
  105.     var
  106.     r,g,b:single;
  107.   begin
  108.   r := sin( ( x*pi/180 ) ) * 127 + 128;
  109.   g := sin(( x - 120 )*pi/180 ) * 127 + 128;
  110.   b := sin( ( x + 120 )*pi/180 ) * 127 + 128;
  111.   exit( rgb( trunc(r) and 255 , trunc(g) and 255 ,trunc( b) and 255));
  112.   end;
  113.            
  114.        
  115.         var
  116.  a:aop=nil;
  117.  gd, gm: SmallInt;
  118.  ch:char;
  119.  i,j:integer;
  120.  col1,col2:longword;
  121.  dv,sv:integer;
  122.   begin
  123.    {==========  set up graph =========}
  124.       gd := D24bit;
  125.       gm :=  m1024x768;
  126.       InitGraph(gd, gm, '');
  127.       if GraphResult <> grok then  halt;
  128.       settextstyle(BoldFont,HorizDir,2);
  129.     {=================================}
  130.       randomize;
  131.       repeat
  132.         setlength(a,range(3,15));  
  133.       for i:=0 to high(a) do
  134.       begin
  135.       a[i].x:=(range(0,800));
  136.       a[i].y:=range(0,600);
  137.       end;
  138.      
  139.        circulate(a);
  140.        
  141.       dv:=range(100,2500);
  142.       sv:=range(0,100);
  143.       for i:=0 to 1024 do
  144.       begin
  145.        for j:= 0 to 768 do
  146.        begin
  147.        col1:=rgb(i,i xor j,j);
  148.        col2:=rainbow(((768-i)*j)/dv);
  149.       if (sv < 50) then swap(col1,col2);
  150.      if inpolygon(a,i,j) then putpixel(i,j,col1) else putpixel(i,j,col2); //<--- crunch line
  151.       end;
  152.       end;
  153.       setcolor(rgb(255,255,255));
  154.       outtextxy(10,10,'Pascal inpolygon demo');
  155.       outtextxy(10,40,'Press esc key to end.');
  156.       drawpolygon(a,rgb(255,255,255));
  157.      
  158.       if KeyPressed then ch:=readkey;
  159.       sleep(1000);
  160.       until (ord(ch)= 27);      
  161.   end.
  162.  
« Last Edit: May 21, 2023, 04:24:37 pm by BobDog »

Handoko

  • Hero Member
  • *****
  • Posts: 5149
  • My goal: build my own game engine using Lazarus
Re: Inpolygon function
« Reply #1 on: May 21, 2023, 03:30:59 pm »
It might be useful for my future projects. Bookmarked.
Thank you for sharing it.

jamie

  • Hero Member
  • *****
  • Posts: 6128
Re: Inpolygon function
« Reply #2 on: May 21, 2023, 03:58:43 pm »
There was code worked on in one of these channels that was doing such things, determining if a point was within a enclosed area of a random shape, like land masses etc.

  Also, there was time studies being done on speed of such function.

 I believe I may have a test project for such code.
The only true wisdom is knowing you know nothing

jamie

  • Hero Member
  • *****
  • Posts: 6128
Re: Inpolygon function
« Reply #3 on: May 21, 2023, 04:07:05 pm »
here is one of them..

 Grab the apex of the polygon so you can move the shape around.

 The results is in the caption.
The only true wisdom is knowing you know nothing

loaded

  • Hero Member
  • *****
  • Posts: 825
Re: Inpolygon function
« Reply #4 on: May 21, 2023, 09:43:46 pm »
here is one of them..

Jamie thank you so much for sharing these codes.
I was using Postgresql + Postgis for a solution similar to this.
Code: MySQL  [Select][+][-]
  1. 'ST_AsText(ST_Centroid(GEOM)) as CENTER,';
I'm sure I wouldn't be so happy if I found gold on the road.  ;D
Check out  loaded on Strava
https://www.strava.com/athletes/109391137

Boleeman

  • Sr. Member
  • ****
  • Posts: 433
Re: Inpolygon function
« Reply #5 on: June 28, 2023, 05:40:19 am »
Came across some open source code for regular polygon creation which may also be useful for someone to get certain properties from them.

and also here for regular polygon maker:
https://forum.lazarus.freepascal.org/index.php/topic,61720.msg465839.html#msg465839




« Last Edit: June 28, 2023, 05:43:51 am by Boleeman »

Boleeman

  • Sr. Member
  • ****
  • Posts: 433
Re: Inpolygon function
« Reply #6 on: June 28, 2023, 07:13:19 am »
and also a Russian open source Vector Editor for regular Polygons, straight lines and ellipses from GitHub.

This has features like:

Selecting the bounds of a regular polygon when the shape is clicked after selecting the move tool (the pentagon in the screen shot illustrates what I mean).
Rotating a regular polygon while drawing it.
Moving a polygon (translating it) and rotating it manually.
Drawing a FreeHand polygon line
Border thickness and color section
Various fill options for the shapes.
Drawing Regular Polygons, rectangles, straight lines, ellipses.

The workspace is a bit small.
Would be nice to perhaps also replace the canvas with a BgraBMP and have a save to transparent graphic feature or even save to SVG.
Also would be nice to adjust the rotation point, instead of just using a default central point.
Anyhow, it's free an open source for everyone to use and learn from.
« Last Edit: June 28, 2023, 08:55:49 am by Boleeman »

VTwin

  • Hero Member
  • *****
  • Posts: 1215
  • Former Turbo Pascal 3 user
Re: Inpolygon function
« Reply #7 on: June 28, 2023, 06:07:36 pm »
Here is a function I use:

Code: Pascal  [Select][+][-]
  1.  
  2. type
  3.   TVector = array of double;
  4.  
  5. { InPolygon
  6.   Determine if point x,y lies in the polygon xs, ys. A polygon
  7.   with n segments is defined by n points.
  8.   Ref: http://www.paulbourke.net/geometry/ (Randolph Franklin) }
  9. function InPolygon(x, y: double; xs, ys: TVector): boolean;
  10. var
  11.   n, i, j: integer;
  12.   c: boolean = false;
  13. begin
  14.   n := Length(xs);
  15.   if (n < 3) then
  16.     c := false
  17.   else begin
  18.     for i := 0 to n-1 do begin
  19.       j := i+1;
  20.       if j = n then
  21.         j := 0;
  22.       if ((((ys[i] <= y) and
  23.         (y < ys[j])) or ((ys[j] <= y) and (y < ys[i]))) and
  24.         (x < (xs[j] - xs[i]) * (y - ys[i]) / (ys[j] - ys[i]) + xs[i])) then
  25.         c := not c;
  26.     end;
  27.   end;
  28.   result := c;
  29. end;
  30.  
“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

Thaddy

  • Hero Member
  • *****
  • Posts: 14358
  • Sensorship about opinions does not belong here.
Re: Inpolygon function
« Reply #8 on: June 28, 2023, 06:28:01 pm »
@VTwin
I would replace the c var with Result everywhere. IOW:
Code: Pascal  [Select][+][-]
  1. {$mode objfpc}
  2. type
  3.   TVector = array of double;
  4.  
  5. { InPolygon
  6.   Determine if point x,y lies in the polygon xs, ys. A polygon
  7.   with n segments is defined by n points.
  8.   Ref: http://www.paulbourke.net/geometry/ (Randolph Franklin) }
  9. function InPolygon(x, y: double; xs, ys: TVector): boolean;
  10. var
  11.   n, i, j: integer;
  12. begin
  13.   n := Length(xs);
  14.   if (n < 3) then
  15.     Result := false
  16.   else begin
  17.     for i := 0 to n-1 do begin
  18.       j := i+1;
  19.       if j = n then
  20.         j := 0;
  21.       if ((((ys[i] <= y) and
  22.         (y < ys[j])) or ((ys[j] <= y) and (y < ys[i]))) and
  23.         (x < (xs[j] - xs[i]) * (y - ys[i]) / (ys[j] - ys[i]) + xs[i])) then
  24.         Result := not Result;
  25.     end;
  26.   end;
  27. end;

But your code is anyway you see it more elegant than the original.
« Last Edit: June 28, 2023, 06:30:15 pm by Thaddy »
Object Pascal programmers should get rid of their "component fetish" especially with the non-visuals.

wp

  • Hero Member
  • *****
  • Posts: 11906
Re: Inpolygon function
« Reply #9 on: June 28, 2023, 06:28:16 pm »
For standard TPoint values, there is
Code: Pascal  [Select][+][-]
  1. function IsPointInPolygon(AX, AY: Integer; const APolygon: array of TPoint): Boolean;  
in unit LazRegions (similar to that presented by VTWin). Like VTWin's function, it only takes care of the even-odd rule in case of non-regular polygons; the non-zero winding rule is not handled (https://wiki.freepascal.org/Developing_with_Graphics#Self-overlapping_polygons).

birin

  • New member
  • *
  • Posts: 9
Re: Inpolygon function
« Reply #10 on: June 28, 2023, 07:01:40 pm »
@VTwin
I would replace the c var with Result everywhere. IOW:
Code: Pascal  [Select][+][-]
  1. {$mode objfpc}
  2. type
  3.   TVector = array of double;
  4.  
  5. { InPolygon
  6.   Determine if point x,y lies in the polygon xs, ys. A polygon
  7.   with n segments is defined by n points.
  8.   Ref: http://www.paulbourke.net/geometry/ (Randolph Franklin) }
  9. function InPolygon(x, y: double; xs, ys: TVector): boolean;
  10. var
  11.   n, i, j: integer;
  12. begin
  13.   n := Length(xs);
  14.   if (n < 3) then
  15.     Result := false
  16.   else begin
  17.     for i := 0 to n-1 do begin
  18.       j := i+1;
  19.       if j = n then
  20.         j := 0;
  21.       if ((((ys[i] <= y) and
  22.         (y < ys[j])) or ((ys[j] <= y) and (y < ys[i]))) and
  23.         (x < (xs[j] - xs[i]) * (y - ys[i]) / (ys[j] - ys[i]) + xs[i])) then
  24.         Result := not Result;
  25.     end;
  26.   end;
  27. end;

But your code is anyway you see it more elegant than the original.

@Thaddy,
replacing C by Result is a good idea, but you need to initialyse Result to false at the start of the function, not only in the n > 3 case :
Code: Pascal  [Select][+][-]
  1. {$mode objfpc}
  2. type
  3.   TVector = array of double;
  4.  
  5. { InPolygon
  6.   Determine if point x,y lies in the polygon xs, ys. A polygon
  7.   with n segments is defined by n points.
  8.   Ref: http://www.paulbourke.net/geometry/ (Randolph Franklin) }
  9. function InPolygon(x, y: double; xs, ys: TVector): boolean;
  10. var
  11.   n, i, j: integer;
  12. begin
  13.   n := Length(xs);
  14.   Result := false;
  15.   if n >= 3 then
  16.     for i := 0 to n-1 do begin
  17.       j := i+1;
  18.       if j = n then
  19.         j := 0;
  20.       if ((((ys[i] <= y) and
  21.         (y < ys[j])) or ((ys[j] <= y) and (y < ys[i]))) and
  22.         (x < (xs[j] - xs[i]) * (y - ys[i]) / (ys[j] - ys[i]) + xs[i])) then
  23.         Result := not Result;
  24.     end;
  25. end;


VTwin

  • Hero Member
  • *****
  • Posts: 1215
  • Former Turbo Pascal 3 user
Re: Inpolygon function
« Reply #11 on: June 28, 2023, 10:09:49 pm »
A good reference is:

Haines, E., 1994. Point in Polygon Strategies. Graphics Gems IV, Academic Press, p. 24-46.
“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.2
macOS 12.1: Lazarus 2.2.6 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.6 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.6 (64 bit on VBox)

 

TinyPortal © 2005-2018