在任意形状中遍历点

Question

我有一个包含（无缝）任意形状（具体的陆地区域）的点multimap<int,int>的多重映射。我将如何迭代包含在任意形状中的所有点？我知道multimap不足以确定内部点，因此我有一个额外的点，这是在形状内部（以确定形状的内部和外部）。

更多信息：由于multimap是一个已排序的容器，因此这些点将按x向排序。所有点都位于网格中，因为我使用的是位图。

Answer 1

1. 如果你的点距离比1个像素更远，那么按x坐标排序的点不会很有帮助。对它们进行排序，使得应该连接的点彼此相邻。

2. Draw lines between the points

3. 发现里面并flood fill形状的点，多数民众赞成。如果您自己实现它，则需要遍历该形状内的每个像素。

Answer 2

一个测试点是否在形状的内部/外部是想象一个射线从该点到已知在该形状之外的点。计算光线穿过边界的次数，如果这个数字是奇数，则该点在形状内，如果它的点数超过形状的话。请参阅ray casting algorithm for a point in polygon。

在你的情况下，最简单的方法是拍摄与你测试点具有相同x值的垂直射线，(x0,y0)表示。让(x0,y1)位于形状的边界框之外的某个点。只需使用相同的x值来计算multimap中的点数。如果它很奇怪，你就在里面，如果它甚至在外面。

上面假定了一些关于形状边界的细节：包含形状的完整边界，因此如果形状穿过边缘上的图像点的边缘包含在多重贴图中，也没有两个相邻的积分(x,y)和(x,y+1)都不在多重映射中。