如何在多边形之间获取位置 [英] How to get location between polygon
问题描述
大家好。
我在地图上多边形之间获取位置的任务基本上是用户在地图上绘制多边形(Bing / Google)并点击搜索按钮.map将显示此多边形之间的所有位置
http://www.justrentals.com/map_search.html
以上链接具有相同的功能我只需要实现this.user在地图上绘制多边形,按下视图属性按钮后,所有位置都将显示此多边形
< blockquote>问题不是那么微不足道;请查看此问题的概述和解决方案的算法: http://en.wikipedia.org/wiki/Point_in_polygon [ ^ ]。
另外,由于明显的原因,如果多边形是自相交的,这个问题的表达本身就有些问题,这是常见的事情。在这种情况下,内在点是什么。一个定义可能与到处使用多边形的常规渲染有关。它使用一些颜色填充。所以,有色区域可以被认为是内在的。
有时,我建议一些愚蠢的解决方法,这肯定会起作用,但丑陋或作弊。所以,有一个非常明显的作弊解决方案,其糟糕的表现很难看:
创建一个位图。从此位图获取 System.Drawing.Graphics
的实例。使用带有一些对比色的 System.Drawing.Graphics.FillPolygon
在此位图中渲染多边形。获取您的位置并使用 GetPixel
检查它的颜色。如果颜色与填充 Brush
的颜色相同,那么这就是内在点。 :-)
请不要太认真地考虑这个作弊解决方案,考虑一下维基百科中描述的真实解决方案,根据我上面的第一个链接。 :-)
这在很大程度上取决于多边形的拓扑结构:它是凹的还是凸的,它是否闭合,是否有任何其他线穿过等等。
假设它是一个凸多边形的多边形,你可以做到以下几点:
- 修剪:检查点是否在多边形的边界框中
- 如果否:结果=不在多边形内
- 如果是:转到2. bwlow
- 按以下方式检查:
- 按统一顺序遍历多边形:
如果该点始终为
在任何
多边形线段的同一侧,该点位于多边形内部- 或者您对多边形进行三角剖分:
从一个顶点绘制一条线彼此的椎骨。
检查每个这样的三角形,如果该点位于任何三角形内部。
这基本上是一个碰撞检测问题。结帐这样的算法。
干杯
Andi
PS:我喜欢谢尔盖的方法(参见解决方案#1),因为它独立于您身边的任何拓扑考虑因素 - 多边形的填充留给系统; - )
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
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 ofSystem.Drawing.Graphics
from this bitmap. Render you polygon in this bitmap usingSystem.Drawing.Graphics.FillPolygon
with some contrast colors. Take your location and check up the color of it usingGetPixel
. If the color is the same as the color of your fillingBrush
, 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
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:
- prune: check if the point is with in the polygon''s bounding box
- if no: result = not within the polygon
- if yes: go to 2. bwlow
- 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 ;-)
这篇关于如何在多边形之间获取位置的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!