Polygons in VO

This paper is about  polygons. We are going to display and move polygons. We are going to do a hit test as well and I will show you how easy it is to compute the area of the polygon.

To make you think about how you can use this knowledge, I’ll tell you how I got involved.

Over a year ago one of my customers came to me and asked me if I could write a database application with a graphical front-end. This front-end had to display ships on several different maps of a harbor. The ships differ in size, the maps differ in scale and the quays in the harbor are not only horizontal and vertical, but have all kinds of directions. And it should be possible to  drag and drop ships to their moor position. These were the challenges.

Draw a polygon

Let’s start drawing a polygon first. To do so, we use a Win32 API function Polygon.

This function needs a pointer to the device context, an array of winpoint structures and the number of points to be drawn.

So the first code looks like this:

METHOD onDrawPolygon( ) CLASS DiW_Demo1

  LOCAL hDevC                 AS PTR
  LOCAL DIM aVerticles[10]    IS _WinPoint
  aVerticles[1].x := 20
  aVerticles[1].y := 30
  aVerticles[2].x := 20
  aVerticles[2].y := 130
  aVerticles[3].x := 120
  aVerticles[3].y := 130
  aVerticles[4].x := 120
  aVerticles[4].y := 230
  aVerticles[5].x := 220
  aVerticles[5].y := 230
  aVerticles[6].x := 220
  aVerticles[6].y := 30

  hDevC :=  GetDC( SELF:Handle() )
  Polygon(hDevC, @aVerticles, 6 )
  ReleaseDC( SELF:Handle(), hDevc )     

  RETURN NIL

Listing 1: Our first polygon

We get the device context (and we do not forget to release it afterwards) and we call the Polygon function with the defined parameters. If we run this code we see a simple polygon drawn on a window.

That is nice, isn’t it. We can add some colors by adding these lines:

  dwColor   := RGB ( 45, 100, 0 )
  hBrush    := CreateSolidBrush( dwColor )
  hOldBrush := SelectObject( hDevc , hBrush  )

  // After painting our polygon we must restore
  // the previous brush and delete the brush
  SelectObject ( hDevc , hOldBrush )
  DeleteObject ( hBrush )

Listing 2: Adding color to our polygon

We can do more to make our drawing even more fancy, but I suggest you have a look at the draw methods of some of the draw classes inside VO. You will find a LineObject, RectangleObject, EllipseObject and more.

Now we know how to draw a polygon on a window, we write a class for it. After all, we are in an object oriented language. Our basic class will looks like this:

CLASS EWV_Polygon
  PROTECT dwColor          AS DWORD
  PROTECT aCurrentpos      AS ARRAY
  PROTECT hWindow          AS PTR
  PROTECT iID              AS INT

METHOD Axit CLASS EWV_Polygon
  IF !InCollect()
    SELF:Destroy()
  ENDIF
  RETURN NIL

METHOD Destroy() AS VOID PASCAL CLASS EWV_Polygon
  aCurrentpos := NULL_ARRAY  //hold the current pos.
  hWindow     := NULL_PTR
  RETURN

METHOD INIT( oSurfacePtr, id )  CLASS EWV_Polygon
  SELF:hWindow     := oSurfacePtr
  SELF:iId         := id
  SELF:aCurrentpos := {}
  SELF:dwColor     := RGB( 45,0,0 )
  SELF:dwRop       := R2_XORPEN
  RegisterAxit( SELF )
RETURN SELF  

ASSIGN Verticles( aPoints AS ARRAY );
  AS ARRAY PASCAL CLASS EWV_Polygon
  SELF:aCurrentpos := AClone( aPoints )
  RETURN SELF:aCurrentposodeline2;

Listing 3: Basic Polygon class

Lets go back to our drawing code. If you have a closer look, you will see a problem. The array is a dimmed array, so the dimension is hard coded. That is not very practical.

We could of course take a large size dimmed array, but if we need a great number of polygons, this will consume too much memory.

We need to dynamically create a dimmed array

What we need here is to be able to dynamically create a dimmed array. That sounds like a contradiction, but it is possible. Not that I knew how, but here I want to emphasize the use of the international newsgroup.  Most questions over there are answered within hours.

This is what my onDrawPolygon event should look like:

METHOD onDrawPolygon() CLASS Diw_Demo2
  LOCAL aCorners AS ARRAY
  LOCAL oPolyGon AS EWV_Polygon
  aCorners := { { 20,30 },;
    { 20,130 },;
    { 120,130 },;
    { 120,230 },;
    { 220,230 },;
    { 220,30 } }
  oPolyGon := EWV_Polygon{ SELF:Handle(), 5333 }
  oPolyGon:Verticles := aCorners
  oPolyGon:Draw( 10 )
  RETURN NIL 

Listing 4: How it should be

Now the aCorners array is a dynamic one. We still hardcode the values here, but we could  also have read them from a database.

The dynamical creating of the DIM-med array is done by the EWV_Polygon:Draw method.

We MemCalloc memory for our array and fill the array element by element:

  pVertices := MemCAlloc(wElem, _SizeOf( PolyVertices ))
  IF pVertices != NULL_PTR
    FOR n := 1 UPTO wElem
      structWinPoint := @pVertices.aVertex[n]
      aSubArray        := aCurrentPos[n]
      structWinPoint.x := aSubArray[1]
      structWinPoint.y := aSubArray[2]
    NEXT     
    Polygon(hDevC, @pVertices.aVertex, Integer(wElem))

Listing 5: Dynamic creation of Dimmed array

If we run this code, it will crash at runtime ... that is, if we have the range-check compiler option selected. So we need to deselect this and it will run fine.

We can add as many vertices as we like and our polygon class can handle it all.

A nice feature here is shown by pressing the draw button a second time.

This is done by using SetRop2( R2_XORPEN). The SetRop2 function sets the current foreground mix mode. GDI uses the foreground mix mode to combine pens and interiors of filled objects with the colours already on the screen. The foreground mix mode defines how colours from the brush or pen and the colours in the existing image are to be combined.

This is going to be very handy when we are going to move or rotate the object. Otherwise we had to repaint (at least part  of) the background first, A perhaps negative side effect is that our polygon is drawn with a transparent colour.

Now that we’ve reached our first milestone, we want more, don’t we?

Rotation

Next step is to rotate our polygon. To do so, we first need to calc the centre of the polygon. There are other ways probably, but what I do here is to find the smallest and the largest point on the x-axis, and divide them by two. I do the same with the largest and smallest point on the y-axis.

METHOD CalcPos() AS VOID PASCAL CLASS EWV_Polygon
  LOCAL wLen  AS DWORD
  LOCAL ixMin  AS INT
  LOCAL iyMin  AS INT
  LOCAL ixMax  AS INT
  LOCAL iyMax  AS INT
  LOCAL n      AS DWORD
  ixMin  := iyMin := ixMax := iyMax  := 0
  wLen := ALen( SELF:aCurrentpos )
  FOR n := 1 UPTO wLen
    ixMin := Min( aCurrentpos[n][1], ixMin )
    iyMin := Min( aCurrentPos[n][2], iyMin )
    ixMax := Max( aCurrentpos[n][1], ixMax )
    iyMax := Max( aCurrentPos[n][2], iyMax )
  NEXT
  SELF:ixPos := Integer( (ixMin+ixMax / 2 ) )
  SELF:iyPos := Integer( (iyMin+iYMax / 2 ) )
  SELF:aStatic := AClone( SELF:aCurrentpos )
  FOR n := 1 UPTO wLen
    aStatic[n][1] -= SELF:iXpos
    aStatic[n][2] -= SELF:iYpos
  NEXT
  RETURN

Listing 6: Calculate the centre of the polygon

In de code above the aStatic array is introduced. We use this as a base. This array holds the original size/shape of the polygon, where aCurrentpos holds the vertices of the displayed polygon that can be sized, moved and/or rotated.

The ixPos and the iyPos are what I call the position of the polygon.

With a SetAngle method we rotate our drawing:

  fSin := Sin(  fAngle*0.0174532925199432957695 )
  fCos := Cos(  fAngle*0.0174532925199432957695 )
  FOR n := 1 UPTO wElem
     fx := SELF:aStatic[n][1] * ;
           fCos + SELF:aStatic[n][2] * fSin
     fy := SELF:aStatic[n][1] * ;
           fSin - SELF:aStatic[n][2] * fCos
     SELF:aCurrentpos[n][1] := Integer( fX + SELF:ixPos)
     SELF:aCurrentpos[n][2] := Integer( fY + SELF:iyPos)
  NEXT
  RETURN

Listing 7: Rotating the polygon

As you can see, I am used to working in degrees instead of radials, so I have to do some conversion. Next is to compute the new positions of the vertices, where we need the Sin and Cos functions. This is not really my area. But thanks to the internet I have found some C-routines that only had to be translated into VO.

Let’s take a look at the demo now:

By pressing the buttons we are able to move and rotate the polygon. What does the moving code look like? Well, that is an easy one. After we have calculated the position of our object, we only have to move it to the new position

METHOD MoveTo(iNewX AS INT,iNewY AS INT) ;
  AS VOID PASCAL CLASS EWV_Polygon

  LOCAL wElem, n AS DWORD
  wElem := ALen( SELF:aCurrentpos )
  SELF:Draw()
  FOR n := 1 UPTO wElem
    aCurrentPos[n][1] := (aCurrentPos[n][1]-ixPos)+iNewx
    aCurrentPos[n][2] := (aCurrentPos[n][2]-iyPos)+iNewy
  NEXT
  SELF:Draw()
  SELF:ixPos := iNewx
  SELF:iyPos := iNewy
RETURN

Listing 8: Moving the polygon

Hit test

The next step is to perform a hit test. I have been searching through the Win32 SDK to find a function for this. And yes, it can be done. We need to create a so called region with CreatePolygonRgn() and then call PtInRegion() to determine if the point falls within the region. But this can be expensive in both GDI resources and in speed. And as a bonus,  if a polygon is complex, CreatePolygonRgn() will often fail due to lack of memory in Windows because regions are in the GDI's heap.

This is something Microsoft found out before I ran into trouble, so they provide an alternative (see MSDN Article 121960 ). This article contains a nice set of C-functions and I have translated these into VO as well. It is fast and does not use regions. The trick lies in determining the number of times an imaginary line drawn from the point you want to test crosses edges of your polygon. If the line crosses edges an even number of times, the point is outside the polygon. If it crosses an odd number of times it is inside. The line is drawn horizontally from the point to the right.

The original C-code is included as a textblock in the AEF. I will not go into the details of this code. What I will do is to show you how fast VO calculates a hit test with these routines. The next figure shows several, more or less complicated polygons and inside the mousemove-event a hit test is performed on the polygons.

Area

I am not very well educated on math’s. But I need to be able to calculate the area of the polygon. And of course I want a fast, optimized algorithm for it.  Thanks (again) to the internet, I did not have to do a lot of work myself; again I only had to translate a C-routine into VO.

I am not very well educated on math’s

In C it is almost a one-liner (how easy can things be?):

Float area2D_Polygon( int n, Point* V )
{
  float area = 0;
  int   i, j, k;     // indices

  for (i=1, j=2, k=0; i<=n; i++, j++, k++) {
     area += V[i].x * (V[j].y - V[k].y);
  }
  return area / 2.0;
}

Listing 9: C-Routine to compute the area of a 2D polygon

Let’s take a simple polygon to be able to understand this algorithm (see the figure):

A = 50, 100
B = 50, 200
C = 350,200
D = 350,100

Now this is what we need to do. We create an array of the points and add the first two points so we get {A,B,C,D,A,B}. The area*2 now is found with:

Bx * (Cy – Ay )  +  // -5000
Cx * (Dy – By )  +  // 35000
Dx *( Ay – Cy )  +  // 35000
Ax *( By – Dy )     // -5000

So the Area will be 60000/2.

To ‘prove’ this is a valid way to calc the area, I have made the polygon a little more complicated (see the figure). We would expect the same result, but let’s see what our algorithm makes of it.

Our array will look like {A,B,C, D, E,F,G,H,A,B}.

A =  50,100
B =  50,200
C = 250,200
D = 250,150
E = 350,150
F = 350,50 
G = 250,50
H = 250,100

And the computation goes like:

Bx * (Cy - Ay )+  //  50 * (200 - 100)=   5000                                                     
Cx * (Dy - By )+  // 250 * (150 - 200)= -12500                                                  
Dx *( Ey - Cy )+  // 250 * (150 - 200)= -12500
Ex *( Fy - Dy )+  // 350 * (50 - 150 )= -35000 
Fx *( Gy - Ey )+  // 350 * (50 - 150 )= -35000 
Gx *( Hy - Fy )+  // 250 * (100 - 50 )=  12500
Hx *( Ay - Gy )+  // 250 * (100 - 50 )=  12500   
Ax *( By - Hy )   //  50 * (200 - 100)=   5000  

Now we get a negative value, - 60000/2=-30000, so we’ll have to change it into a positive one.

The VO- code for the Polygon:Area access will be:

  w :=  ALen(SELF:aCurrentpos )
  aVertex := ArrayCreate( w + 2 )
  FOR i := 1 UPTO w
     aVertex[i] := acurrentpos[i]
  NEXT
  aVertex[w+1] :=  acurrentpos[1]
  aVertex[w+2] :=  acurrentpos[2]
  farea := 0.00
  FOR i = 2 UPTO w+1
    farea += aVertex[i,1] * ;
             (aVertex[i+1,2]-aVertex[i-1,2])
  NEXT
  IF fArea < 0
    fArea := -fArea
  ENDIF
  RETURN fArea/2.0

Listing 10: Area access of the poygon

Conclusion

You have seen how you can draw a polygon, with the aid of a dynamically created DIM-med array. We have moved our drawing around the screen, enlarged it and made it smaller. We have rotated it in any direction, performed hit tests and we have seen a way to compute the area. I am sure you can find a practical use for it and I hope you enjoyed reading.

De sources zijn beschikbaar via Visser_Polygons_Sources.zip.

If you have any questions, please don’t hesitate to contact me at evisser@wilg.nl