判断点是否在自由曲线（大量边的多边形）内

yzli007 · 发表于 2016-8-8 10:37

本帖最后由 yzli007 于 2016-8-8 10:45 编辑

已知大量点的坐标，并且知道由大量点的坐标确定的自由曲线（也可以是大量边的多边形），如何筛选出落在曲线内部和曲线上的点的坐标？谢谢

蓝桥玄霜 · 发表于 2016-8-12 15:40

这是一个好题目。
请见代码。

liucqa · 发表于 2016-8-12 21:26

百度判断一个点是否在多边形内部

yzli007 · 发表于 2016-8-16 14:35

蓝桥玄霜发表于 2016-8-12 15:40
这是一个好题目。
请见代码。

您运行过了没？能把代码发一下吗

Moneky · 发表于 2016-8-16 14:42

以前干过类似的事（VB做一个小游戏），我是将多边形区域填充好指定颜色A，然后把要判断的点B的坐标所对应的像素颜色是否是颜色A，如果是则说明点在内部，不是就在外部。

上面只是一个思路，对于楼主的问题来说可能没什么用，数据太大了，一个像素对应很大的值。

yzli007 · 发表于 2016-8-16 14:48

Moneky 发表于 2016-8-16 14:42
以前干过类似的事（VB做一个小游戏），我是将多边形区域填充好指定颜色A，然后把要判断的点B的坐标所对应 ...

像素法恐怕不行，楼上版主的应该差不多的

蓝桥玄霜 · 发表于 2016-8-17 08:51

我的思路是：
1，先计算多边形范围边界的最大值，从而排除大量的范围外数据；
2，判断通过B列x值的垂直线与多边形的可能相交点，方法是：求得比x小的G列的所有值，然后按降序排序，
从最大的开始判断，如果它的相邻点的值大于x的话，表示x垂直线与这两点组成的直线相交，并可求得其交点的坐标值，如果有2个以上的交点，把这些交点值排序后，再依次判断相应的C列y值是否在这些交点值之间，如果在两点之间，再判断通过C列y值的平行线与多边形的可能相交点，求得交点的x值，判断是否在范围内。
请见附图。标有yes的点是在范围之内的。
代码已经给了，请自己抄一遍。对于初学者，抄写代码是必不可少的功夫，在此过程中会学到很多书上学不到的东西。