我有一个关系数据库,其中每个条目都标记为带有纬度/经度坐标的点。我让用户能够在地图上标记任意多边形,并希望返回多边形形状内的所有条目。
实现这一目标的最佳方法是什么?
此外,可能值得指出的是,小错误是可以的(即,如果有一种有效的方法可以将多边形变成一组矩形,那很好)。
我有一个关系数据库,其中每个条目都标记为带有纬度/经度坐标的点。我让用户能够在地图上标记任意多边形,并希望返回多边形形状内的所有条目。
实现这一目标的最佳方法是什么?
此外,可能值得指出的是,小错误是可以的(即,如果有一种有效的方法可以将多边形变成一组矩形,那很好)。
使用空间扩展,大多数数据库都有这个。在 MySql 中,您只能将它们与非事务性的 MyISAM 表一起使用。
http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html
一种快速减少要考虑的点数的方法是计算多边形的边界矩形(即多边形中点的 min-x、min-y、max-x、max-y),然后选择边界矩形内的点(即 x 在 min-x 和 max-x 之间,y 相同)。
当然,并非所有这些点都必须在多边形内,但现在您可以使用代码对其进行磨练。
一个老黑客:
计算连接<point far away>
到的线<point in question>
穿过多边形的任何边界段的次数。