多边形分解 - 去除凹点形成凸多边形 [英] Polygon Decomposition - Removing Concave Points to Form Convex Polygons

问题描述

我想解构下面以蓝色显示的多边形，从多边形中删除所有引起凹陷的点。

i.stack.imgur.com/APQiz.pngalt =alt text>

目前，我一直试图做的是：

• 从多边形中取出每个点
  
• 测试点以查看它是否落在由其余部分创建的多边形内
  
• 如果为true，则删除该点


• 如果为false，请保留该点

这在大多数情况下都适用，但在前一种情况下，（2,3）和（2,4）处的点不会同时被删除。在这两种情况下，其中一个点将被删除，但另一个不会取决于数组传递的顺序。

我想知道的是：

1. 有没有什么方法可以测试我正在处理的多边形是否恰好有这些情况之一（IE：3分）
   或


2. 创建凸多边形是否更简单？

谢谢。

解决方案

我想也许您正在寻找凸包？

头脑是QuickHull。最初，采取最左边和最右边的点，l和r。他们必须在船体上。

构造对两个外表面的第一个猜测，一个从l到r，一个从r到l。所以你有一个零体积的多边形。

将所有剩余的点分成lr前面和rl前面的那些点。

从那时起，任何脸部都有任何点数：

• 从脸上找出最远的点


• 删除此边并用两条边替换它，一条从原始起点到最远点，另一条从最远点到原始终点


• 在旧脸前的所有点上，把那些放在前面的新脸上的第一张脸前面，把第二张脸放在前面，不要保留对现在内部的任何引用

最后，您将拥有凸包。

I would like to deconstruct the following polygon shown in blue removing all of the points from the polygon that cause concavity.

Currently, what I have been attempting to do is:

• Take each point out of the polygon
• Test the point to see if it falls within the polygon created by the rest of the set
• If true remove the point
• If false keep the point

This works in most cases, but in the previous case the points at (2,3) and (2,4) will not both be removed. In both cases either one of the points will be removed, but the other will not depending on the order which the array is passed in.

What I am wondering is this:

1. Is there some way to test to see if the polygon I am dealing with happens to have one of these cases (IE: 3 points of failure in a row?)
   or
2. Is there simply a more effective way of creating convex polygons?

Thank you.

解决方案

I think perhaps you're looking for the convex hull?

The first algorithm that springs to mind is QuickHull. Initially, take the leftmost and the rightmost points, l and r. They must be on the hull.

Construct a first guess at the hull that's two outward faces, one from l to r and one from r to l. So you have a polygon with zero volume.

Divide all remaining points into those in front of lr and those in front of rl.

From then on, while any face has any points in front of it:

• find the furthest point from the face
• delete this edge and replace it with two edges, one from the original start point to the furthest point and one from the furthest point to the original end point
• of all the points that were in front of the old face, put those in front of the first of the new faces you've added into its in front set, put those in front of the second into its in front set and don't retain any reference to those now inside

At the end you'll have the convex hull.

这篇关于多边形分解 - 去除凹点形成凸多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！