问题标签 [convex]

我的代码使用格雷厄姆算法找到凸包效果很好（它向我展示了它应该显示的多边形）但我可以看到它向我发送了一个额外的共线点（尽管我正在处理我的代码中的共线点) 这是我的代码：

我非常等待有一些提示来帮助我找到我的问题

我在 XNA 中编写游戏，现在正在研究 AI 的寻路工作。

在我的地图中有一些圆形障碍物，我想使用网格导航技术（http://udn.epicgames.com/Three/NavigationMeshReference.html）所以以前我需要将这些障碍物转换为一组凸多边形。

像这样的东西：

我在谷歌上搜索了很长时间，但找不到怎么做。有什么线索吗？谢谢！

我正在研究以下代码。

我不明白那个区域是负面的概念。面积不应该总是积极的吗？也许我对这里的术语缺乏一些理解。我试图联系原作者，但这段代码大约有 8 年的历史，我无法联系原作者。这种确定给定顶点 x2y2 是否为凸的方法似乎非常灵活。我真的很想了解它。任何帮助我理解这段代码的方向或参考将不胜感激。

源代码：http ://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applets/BruteForceEarCut.java

我的问题与Plough 的问题非常相似；但有这个区别：

如何找到可以适合非凸区域的最大凸区域？

例如，考虑这个非凸区域：

任何想法或解决方案将不胜感激，谢谢。

是否有任何方法或算法可以从外部（周长）确定区域的凸（或非凸）属性？

一种方法是在周长的每个点上绘制切线，并讨论这条线与周长点相交的次数。如果没有显示相交（对于周长的所有点），我们可以断定区域是凸的。在其他情况下，区域是非凸的。

第二种方法是确定周长每个点的内角，并讨论它是否大于180。如果周边至少有一个点存在，则该区域是非凸的，它的内角大于 180。

还有其他更简单的方法吗？

任何想法或解决方案将不胜感激，谢谢。

我正在尝试为我解决一个相当困难的问题。我对编程并不陌生，但我真的不知道如何解决这个问题。它给出了一组点 (point [])，其中 Xi 和 Yi 坐标作为输入。程序必须输出多边形凸包的周长，但如果有必要，它可以将凸包分成两部分，两个独立的凸包，每个凸包都包含许多点。此划分的目标是具有更短的周长（如果这两个外壳的周长之和小于一个外壳的周长；例如：两个远离彼此的点簇）。问题还在于不能超过两个船体。我会很感激任何想法。

这个问题有一个简单的说明（可能还有很多点）。在这里，您可以看到两个分开的船体的周长比一个船体的周长短。

ADD：实际上，“周长”是指周长。

这是我的代码的关键部分：

我有一个空间软件，在一个数据库中，我有几个城市的每条街道，每条街道的纬度/经度。每条街道都属于一个区域。我正在尝试为每个区域获取多边形，为此，我需要一种算法来为我提供覆盖多个点的最小多边形。非常类似于凸包。凸包是没用的，因为它是这样解决的：

而且，我需要的是：

我有一个空间软件，在一个数据库中，我有几个城市的每条街道，每条街道的纬度/经度。每条街道都属于一个区域。我正在尝试为每个区域获取多边形，为此，我需要一种算法来为我提供覆盖多个点的最小多边形。非常类似于凸包。凸包是没用的，因为它是这样解决的：

而且，我需要的是：

是否有任何用于一般精度数的 n 维 quickhull 算法的C++（Java或类似的可轻松转换为C++ ）的实现？

我知道qhull实现的存在（是任意维度，是C/C++，但不是一般精度）。

I have a 3D grid of binary data values (either the point is solid or it's not). I need to generate a physics mesh from that grid, but it needs to be able to move, so I can't use triangle mesh, I must use a compound shape made of boxes. I need to find the largest boxes (or rather the least number of boxes) that the grid can be split into. Here's a 2D representation of what I want to do in 3D:

The first image shows each point as its own box - terribly inefficient (22 boxes). The second image shows what I would like the grid to become (4 boxes).

I realise there are convex decomposition libraries out there, but I need this to be exact, not approximate, and I thought there might be some easier method when the data is guaranteed to be in a grid. Also, I need boxes, not just convex shapes.

Any tips, pointers or help would be much appreciated :)