Click here to Skip to main content
15,867,453 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Hello Every one.

I hava a task to get location between polygon on map basically user draw a polygon on map (Bing/Google) and clicking search button.map will show all location between this polygon

http://www.justrentals.com/map_search.html

above link have same functionality i just need to implement this.user draw a polygon on map and after pressing view property button all location will show between this polygon
Posted
Comments
StM0n 19-Jan-13 5:35am    
Sorry, did you mean: all locations/point INSIDE the polygon?
Sergey Alexandrovich Kryukov 20-Jan-13 14:50pm    
What do you mean "between"? Probably you mean the region defined by the polygon — inside the polygon.
You did not tag the UI library, technology or application type you use.
—SA

The problem is not so trivial; please see this overview of this problem and the algorithms of the solution: http://en.wikipedia.org/wiki/Point_in_polygon[^].

Also, by apparent reasons, the formulation of this problem itself is somewhat questionable, if the polygon is self-intersecting, which is the usual thing. What is the inner point in this case. One definition could be related to the usual rendering of a polygon use everywhere. It is filled using some color. So, colored areas could be considered as "inner".

Sometimes, I suggest some "idiotic" workarounds, something which will certainly work but ugly or cheating. So, there is a very apparent cheating solution, ugly in its poor performance:

Create a bitmap. Get the instance of System.Drawing.Graphics from this bitmap. Render you polygon in this bitmap using System.Drawing.Graphics.FillPolygon with some contrast colors. Take your location and check up the color of it using GetPixel. If the color is the same as the color of your filling Brush, this is the inner point. :-)

Please don't consider this cheating solution too seriously, think about the "real" one described in Wikipedia, as per my first link above. :-)

—SA
 
Share this answer
 
v2
Comments
Andreas Gieriet 20-Jan-13 15:20pm    
My 5!
Brute force but effective!
Cheers
Andi
Sergey Alexandrovich Kryukov 20-Jan-13 15:49pm    
Thank you, Andi, for up-voting the pure cheating :-)
To my excuse, I honestly warned that this is a cheating. :-)

As to this questionable "effectiveness"... I don't know, it depends. In some rare cases, I use the following principle I once invented and keep in my repertoire:

"If you out of clever ideas, try a stupid one".

Believe or not, it worked amazingly well in a few cases. :-)

—SA
Andreas Gieriet 20-Jan-13 16:24pm    
I call them "brute force". This is like calculating PI/4 by Monte Carlo method: draw a square and an inscribed circle touching the square at each side. Then randomly (really randomly) shoot to the target. The ratio of the dots in the whole square and the dots within the circle are getting about PI/4 (if you are willing to invest enough time to do that exercise ;-)).
Cheers
Andi
This depends very much on the topology of the polygon: is it concave or convex, is it closed, is any line crossing any other, etc.

Assuming it's a convex and closed polygon, you can do the following:

  1. prune: check if the point is with in the polygon's bounding box

    1. if no: result = not within the polygon
    2. if yes: go to 2. bwlow

  2. check by one fo the following:

    • Traversing the polygon in an uniform order:
      if the point is always on the same side of any
      polygon segment, the point is inside the polygon
    • Or you triangulate the polygon:
      draw a line from one vertex to each other vertext.
      Check for each such triangle, if the point is inside of any of the triangles.


It's basically a collision detection problem. Checkout such algorithms.

Cheers
Andi

PS: I like Sergey's approach (see solution#1), since it is independent of any topology considerations from your side - the filling of the polygon is left to the system ;-)
 
Share this answer
 
v2
Comments
Sergey Alexandrovich Kryukov 20-Jan-13 15:51pm    
Not actually quite the solution, but some good ideas, a 5.
—SA
Andreas Gieriet 20-Jan-13 16:26pm    
Thanks. I think searching for collision detection is the key.
Andi

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900