如何根据 X,Y 的集合确定多边形的周长
我有一个布尔值[][]，其中真实索引构成一个实心多边形。有了这些信息，我如何
- A. 确定哪些块构成了周长，以及
- B. 哪些点（按顺序）可以使用多边形类绘制多边形。
我打算使用 Polygon 类来调用 .contains 但我目前的代码给了我乱序的多边形点（因为我只是从左到右、从上到下扫描）。任何有关该主题的帮助都将受到赞赏。
I have a boolean[][] where the true indexes make up a solid polygon. With this information how can I
- A. determine which blocks make up the perimeter, and
- B. which points (in order) can draw the polygon using the polygon class.
I intend to use Polygon class to call .contains but the code I have currently gives me the polygon points out of order (as i am simply scanning from left to right, top to bottom). Any help on the subject is appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我认为您只需要确定角点并将它们连接起来。凸包算法可能不起作用，因为多边形可能不是凸的。例如，多边形维基百科页面上从左边算起的第三个多边形（绿色多边形）是不是凸的。此外，对于已经是凸的多边形，凸包算法可能会显得过大。
除非我弄错了，否则根据点邻居的状态，布尔值列表中应该有四种类型的点。在常规网格中，索引 i,j 处的元素应该有 8 个邻居。基于这 8 个相邻点，假设您的多边形不接触该区域的任何边缘，您应该有四种不同类型的点：
您可以遍历布尔值并挑选出多边形的所有边缘点（当多边形接触区域边缘时，您必须格外小心，例如，在最小行和最小列处有一个真值）。获得边缘点后，您可以通过反复试验来确定哪些点连接到哪些点。尝试连接两个点并查看边是否有效。如果边缘有效，那么它将在一侧具有所有真值，在另一侧具有所有假值，直至合理的边际或误差。如果它不具有此属性，则它一定不是多边形的边。
I should think that you would just need to determine the corner points and connect them. A convex hull algorithm may not work because the polygon may not be convex. For instance, the third polygon from the left (the green one) on the wikipedia page for polygons is not convex. Also for polygons that are already convex a convex hull algorithm will likely be overkill.
Unless I am mistaken there should be four types of points in your list of Boolean values based on the status of the point's neighbors. In a regular grid an element at index i,j should have 8 neighbors. Based on these 8 neighbors you should have four different types of points assuming that your polygon does not touch any of the edges of the region:
You can go through your Boolean values and pick out all of the edge points for the polygon (you will have to take extra care in the case when the polygon is touching an edge of the region, for instance there is a true value at the smallest row and the smallest column). Once you have the edge points you determine which points connect to which by trial and error. Attempt to connect two points and see if the edge is valid. If the edge is valid then it will have all true values on one side and all false values on the other up to a reasonable margin or error. If it does not have this property then it must not be an edge of the polygon.
您正在寻找凸包算法。
You're looking for a Convex Hull algorithm.
首先，您需要一些算法
：一种将 boolean[][] 转换为一组 XY 坐标的方法。
第二：将这些点转换为多边形的方法（阅读凸包算法）
第三：计算该多边形周长的方法。
现在就去填空吧！
You need a couple of algorithms
First: a way to translate your boolean[][] into a set of X-Y coordinates.
Second: a way to convert those points into a polygon (read up on Convex Hull algorithm)
Third: a way to calculate the perimeter of that polygon.
Now go fill in the blanks!
听起来凸包算法还不够，因为多边形可能是凹的。您想要的是位图到矢量算法。查看此链接以获取此类算法的描述：http://cardhouse.com/computer/vector.htm
一旦获得多边形点，您就可以对每个线段进行距离计算。
It doesn't sound like a convex hull algorithm will be sufficient since the polygon might be concave. What you want is a bitmap to vector algorithm. Check out this link for a description of such an algorithm: http://cardhouse.com/computer/vector.htm
Once you've got the polygon points you can just do a distance calculation on each segment.