[RESOLVED] Polygons - See if they overlap/intersect?

Say there are 2 polygon regions on a form. What is the best way to see if they intersect or if they collide?

The polygons are just an array of points (POINTAPI type: x, y).

My math skills are basically non-existent. Anyone have any suggestions?

I've come across something called the DotProduct but am having a terrible time trying to understand it. :sick:

Should this maybe be in the game forum? :confused:

Thanks.

Edit: I forgot to point out that, the polygons will probably not have the same number of points, making this even more difficult.

The simplest IMO, but not necessarily the most efficient is to use regions. A region can be created from an array of points with createpolygonrgn api. Then the 2 can be combined to a 3rd (null) region using the RGN_AND flag of CombineRgn api. If the region is anything but a null region, then they overlap. Here is an example of intersecting regions from a region class I designed several years ago, maybe it might help. Hopefully no typos & hopefully it works.

Code:

---

Private Declare Function CreatePolygonRgn Lib "gdi32.dll" (ByRef lpPoint As POINTAPI, ByVal nCount As Long, ByVal nPolyFillMode As Long) As Long
Private Declare Function CombineRgn Lib "gdi32.dll" (ByVal hDestRgn As Long, ByVal hSrcRgn1 As Long, ByVal hSrcRgn2 As Long, ByVal nCombineMode As Long) As Long
Private Declare Function DeleteObject Lib "gdi32.dll" (ByVal hObject As Long) As Long
Private Declare Function GetRegionData Lib "gdi32.dll" (ByVal hRgn As Long, ByVal dwCount As Long, ByRef lpRgnData As Any) As Long
Private Const RGN_AND As Long = 1


Public Function RegionIntersect(rgnPts1() As POINTAPI, rgnPts2() As POINTAPI) As Boolean
    Dim rtnRgn As Long, Rgn1 As Long, Rgn2 As Long
   
  Rgn1 = CreatePolygonRgn(rgnPts1(0), UBound(rgnPts1) +1, 2)
  If Rgn1 = 0& Then Exit Function

  Rgn2 = CreatePolygonRgn(rgnPts2(0), UBound(rgnPts2) +1, 2)
  If Rgn2 = 0& Then
        DeleteObject Rgn1
        Exit Function
  End If

  rtnRgn = CreateRectRgn(0&, 0&, 0&, 0&)
  CombineRgn rtnRgn, Rgn1, Rgn2, RGN_AND
           
  ' if the total region size is 32bytes, this can be interpreted
  ' that 1) we have a region & 2) the region has no region rectangles
  ' since the 1st 32bytes of any region is the header information
  ' and the remaining bytes are the region rectangles.
  ' No additional rectangles, no collision
  If GetRegionData(rtnRgn, 0&, ByVal 0&) > 32& Then RegionIntersect = True
           
  DeleteObject Rgn1
  DeleteObject Rgn2
  DeleteObject rtnRgn
End Function

---

I wouldn't count on this method to use in any game that may require real speed. The mathematical solutions will probably be faster I would think.

Have a quick look over at the Maths forum, there is a thread on just the subject

The function in post #9 is nice. It could be adapted to not use any divisions (if the intersection coordinates aren't needed) making it potentially very fast.

Techniques vary depending on whether the polygons are concave or convex.

Edit: I've just seen LaVolpes post; I think it might be quite an expensive way to determine an intersection but it is very simple.

Quote:

---

Originally Posted by LaVolpe

The simplest IMO, but not necessarily the most efficient is to use regions. A region can be created from an array of points with createpolygonrgn api. Then the 2 can be combined to a 3rd (null) region using the RGN_AND flag of CombineRgn api. If the region is anything but a null region, then they overlap. Here is an example of intersecting regions from a region class I designed several years ago, maybe it might help. Hopefully no typos & hopefully it works.

Code:

---

Private Declare Function CreatePolygonRgn Lib "gdi32.dll" (ByRef lpPoint As POINTAPI, ByVal nCount As Long, ByVal nPolyFillMode As Long) As Long
Private Declare Function CombineRgn Lib "gdi32.dll" (ByVal hDestRgn As Long, ByVal hSrcRgn1 As Long, ByVal hSrcRgn2 As Long, ByVal nCombineMode As Long) As Long
Private Declare Function DeleteObject Lib "gdi32.dll" (ByVal hObject As Long) As Long
Private Declare Function GetRegionData Lib "gdi32.dll" (ByVal hRgn As Long, ByVal dwCount As Long, ByRef lpRgnData As Any) As Long
Private Const RGN_AND As Long = 1


Public Function RegionIntersect(rgnPts1() As POINTAPI, rgnPts2() As POINTAPI) As Boolean
    Dim rtnRgn As Long, Rgn1 As Long, Rgn2 As Long
   
  Rgn1 = CreatePolygonRgn(rgnPts1(0), UBound(rgnPts1) +1, 2)
  If Rgn1 = 0& Then Exit Function

  Rgn2 = CreatePolygonRgn(rgnPts2(0), UBound(rgnPts2) +1, 2)
  If Rgn2 = 0& Then
        DeleteObject Rgn1
        Exit Function
  End If

  rtnRgn = CreateRectRgn(0&, 0&, 0&, 0&)
  CombineRgn rtnRgn, Rgn1, Rgn2, RGN_AND
           
  ' if the total region size is 32bytes, this can be interpreted
  ' that 1) we have a region & 2) the region has no region rectangles
  ' since the 1st 32bytes of any region is the header information
  ' and the remaining bytes are the region rectangles.
  ' No additional rectangles, no collision
  If GetRegionData(rtnRgn, 0&, ByVal 0&) > 32& Then RegionIntersect = True
           
  DeleteObject Rgn1
  DeleteObject Rgn2
  DeleteObject rtnRgn
End Function

---

I wouldn't count on this method to use in any game that may require real speed. The mathematical solutions will probably be faster I would think.

---

Perfect. I am already using regions like in your code, so this works perfectly.

Thanks. :cool:

Hi!
I tried your code but im getting some problems in the run time error.
I gave declared the POINTAPI AS
PUBLIC TYPE POINTAPI
X() AS LONG
Y() AS LONG
END TYPE

please do help me in this declaration.
it is giving script out of range error.

seth,

Code:

---

Public Type POINTAPI
X As Long
Y As Long
End Type

... delcare the array like this
Dim myPts() As POINTAPI

.... Fill like this, after ReDim to appropriate size
myPts(0).X = 123: myPts(0).Y = 456

---

Hi!
Thnks for ur code!

But i also have i more problem.

Is it possible to get a wireframe effect of images in vb6.

wht ever image i put it should display the outline of image in wireframe.

pls help me in this regard.

with regards!
Sethuraman R

Hi!
I have i problem.
i will click 4 points at different places in an image & once i click the 4th point the system should automatically draw a circle of that radius.
How to do this.

i will click 4 points in an image & after clicking the 4th point then the system should automatically draw a perfect circle with centerpoint.

pls help me in this regard!

with regards!
Sethuraman R

Hi!
Can anybody help me out in getting the intersection points where 2 images overlapp each other.
I have tried out alkl possible methods but it ended up in a mess.

pls help me out in getting the intersection points where 2 images are overlapped each other in visual basic 6

HI!
I have 1 problem. i have attached 1 image refer that i image.
i have 1 line which displays a center point in pixels.
now i want to draw a circle for that line which meets that line.

pls help me in this regard!

with regards!
Sethuraman R

HI!
This requirement is very important for me & it is required urgently....

I have 1 line drawn using mouse & im able to find the length of the line & using the length im finding the center point of the line but can i get the mouse position x & y where the center point lies.

By using the center point of line i want to know the Mouse x posistion & y position.

pls help & it is required urgently.

with regards!
Sethuraman R

Not sure if I follow you exactly but calculating the center point is easy, it's just the average of the two endpoints. For the radius use Pythagoras theorem.
Assuming the line is defined x1,y1 - x2,y2

Code:

---

CenterX=(x1+x2)/2

CenterY=(y1+y2)/2

Radius=sqr((x1-x2)^2+(y1-y2)^2)/2

---

Edit: is this not getting a bit Off Topic?

Hi!
Thnks a lot.
But i want to know the mouse x position & mouse u position of the center point of the line & is it possible to get that.

pls help me in this regard.

with regards!
Sethuraman R

Hi!
This problem is fuzzing me from the past 3 days & i have not been able to find out a solution for this.

I'm drawing a line using mouse and im also displaying the length of line in pixels. i'm able to find out the center of the line but i want to know the mouse x position & mouse y position of the center point.
i have the total length of the line measured in pixel is it possible to get the mouse x & mouse y position of the center point .

pls help me pls...

This is getting off Topic and maybe should be in its own thread.

Your question makes no sense to me. What do you mean by 'mouse x & mouse y position of the center point'. Do you want the coordinates in relation to the current mouse position?

Can you post a picture with the line, circle, and mouse all indicated.

I have attached a image.
In the image u can find a line drawn & it has been measured in pixel.

u will find 2 labels placed.

one at the bottom is the length of line in pixel.

the second one is at the top which is divided by the total pixel length.

now i want tha secong label which is placed at the top to be fixed at the center of the line.

pls help me.....

with regards!
Sethuraman R

Hi!
I have once again attached the image.

I'd seen the previous picture, I asked you to post a picture with more detail as to what you want.
As it is the way you describe the picture and what it shows contradict each other, the second label already is shown at the center.

http://i20.photobucket.com/albums/b202/Shypt/THING.jpg
Here is your picture again with a little more info. The coordinates x1,y1 and x2,y2 are known. Please explain as best you can what you want because as it is it makes no sense and reads to me like "I know how to calculate the center point but how do I calculate the center point."
Please also explain the circle you talk of but don't show.
:)

hi!
Im sorry i have attached a wrong picture in that picture what you see the center point label is adjusted to show that it is in center.
Im sorry for explaining properly.

Here is my problem.
i will draw a line & im calculating the length of the line in pixels say for example 3451 is the total length of the line.
Now i this i can calculate the center point by 3451/2=1725.5.

My problem is i want to place this value 1725.5 at the center of the line by getting the x position & y position.

this is my problem.

i want to place the center point in the middle of the line.

how to do this?
pls let me know & dont take the previuos as example.

i want to place or point the center point of the line.

with regards!
Sethuraman R

Hi !
just like how you have plotted a point in the center of the line just like that based on the length of the line the center point shoud be made visible in images.

hi!
Im extremely sorry for not furnishing all the details of my problem.
1) i have 1 image
2) i will draw a st line.
3) i will calculate the length of the line in pixels.
4) i will get the center point of the line by dividing the total length by 2.
********************
5) how to plot a point as you have done in the image which i had attached in the previous mail?
6) i want the center point to be pointed so that the user can know that it i the center point of the line.
how to do this in images?

7) after plotting the center point i should be able to automatically draw a circle which meets the where this line passes through the middle of the circle.

with regards!
Sethuraman R

Hi!
I saw the figure you have plotted x1,y1 as starting point as x2,y2 as ending point i want to know cx & cy positions.

This is what my requirement is.

pls dont get upset for all the posts that i ahve made relevant to this topic.

im trying to explain the best that can make you to help me.

with regards
Sethuraman R

Code:

---

cx=(x1+x2)/2
cy=(y1+y2)/2

---

Thats all it is.

Consider the line (123,456)-(765,432)

cx=(123+765)/2=444
cy=(456+432)/2=444

The center point is 444,444

Thnks ~
i got it but how to plot a point in that position say 444,444

Hi!
I also want to draw a cirle for this center point.

pls help me out in this case too..


with regards!
Sethuraman R

Code:

---

Pset (cx,cy) 'draws a dot at cx,cy
Circle (cx,cy),10 'draws a circle at cx,cy with a radius of 10

---

See post #12 for calculating a radius that goes through the endpoints.

Hi!
Thanks a lot it works.

I also have i more problem related to printing.

Say i have 1 image it may be aything say my face.

Is it possible in vb that if i give the print button then only my face should be printed not the background of the image.

Is it possible in vb6 to achieve this?
Printing only my face in paper not the background.

pls help me in this problem.

with regards!
Sethuraman R

Hi!
I have 1 problem now which is very urgent.
I have developed a software for inventory control in my office.
I have used Visual Basic 6 & crystal report 9 for report purpose.

Is it possible to automatically export the report in pdf of a current transaction?
i want to export the report automatically as soon as the transaction is saved.

can you please help me in this regard.

with regards!
Sethuraman R