6
A
回答
0
对不起,我没有任何好的关键词供您查阅。
我试图想象一些三维地形在三维近似三角形。如果在轮廓内形成一个湖泊,使得湖泊没有岛屿,那么湖泊的轮廓将成为您想要的多边形 - 并且对于游戏而言,它可能相当直观,因为它基于现实世界的景观。
如果您可以找到众所周知的算法来制作三角形的三维景观,我会找到最高点并找到周围的循环路径,以使循环中的最低点达到最大。根据地形你可能会得到一些有趣的多边形。
再次 - 抱歉,我不知道任何完美的算法,但我只是觉得这是一个非常有趣的问题。
0
我在C++中编写了一些关于几何算法的单元测试,这些几何算法需要非自相交多边形来处理。它没有被设计为高效,不可读,并且多边形有时在边缘之间具有相当小的角度。看看你是否喜欢它,如果你愿意,可以扩展它。没有保证。
文件rpoly.h
:
#include <vector>
#include <list>
#include <algorithm>
#include <iterator>
#include <stdexcept>
#include <iostream>
using namespace std;
struct HalfEdge
{
HalfEdge() {};
HalfEdge(size_t start, size_t end) : start(start), end(end) {};
size_t start;
size_t end;
};
typedef vector<HalfEdge>::iterator edge_iterator;
typedef vector<HalfEdge>::const_iterator const_edge_iterator;
template <class Point>
struct non_intersecting_edges
{
non_intersecting_edges(const vector<Point>& vertices, vector<HalfEdge>& edgelist)
: vertices(vertices), edgelist(edgelist) {}
void operator() (size_t i)
{
const Point &p = vertices[i];
for (edge_iterator it=edgelist.begin(); it!=edgelist.end(); ++it)
{
HalfEdge edge = *it;
Point start_vertex = vertices[it->start];
Point end_vertex = vertices[it->end];
if (point_intersects_edge(p, start_vertex, end_vertex))
return; // skip this point
if(!edge_intersects_polygon(start_vertex, p) &&
!edge_intersects_polygon(end_vertex, p))
{
edgelist.push_back(HalfEdge(i,it->end));
it->end = i;
return;
}
}
cerr << "[rpoly] Warning: no possible edge found for vertex " << p << endl;
}
private:
bool point_intersects_edge(const Point& p, const Point& A, const Point& B) const
{
double d = (A.y-p.y) * (B.x-p.x) - (B.y-p.y) * (A.x-p.x);
if (abs(d) < 1e-14)
{
return ((A.x <= p.x && p.x <= B.x) || (A.x >= p.x && p.x >= B.x))
&& ((A.y <= p.y && p.y <= B.y) || (A.y >= p.y && p.y >= B.y));
}
else return false;
}
bool edge_intersects_polygon(const Point& A, const Point& B) const
{
double dx = B.x-A.x;
double dy = B.y-A.y;
for (const_edge_iterator it=edgelist.begin(); it!=edgelist.end(); ++it)
{
double d,u1,u2;
const Point &C = vertices[it->start];
const Point &D = vertices[it->end];
d = (D.y-C.y)*dx - (D.x-C.x)*dy;
if (d != 0) {
u1 = ((D.x-C.x)*(A.y-C.y) - (D.y-C.y)*(A.x-C.x))/d;
u2 = (dx*(A.y-C.y) - dy*(A.x-C.x))/d;
if (u1 > 0 && u1 <= 1 && u2 > 0 && u2 <= 1) // half-open edges
return true;
}
}
return false;
}
const vector<Point>& vertices;
vector<HalfEdge>& edgelist;
};
bool start_index_less(const HalfEdge &a, const HalfEdge &b)
{
return a.start < b.start;
}
bool start_index_equals(const HalfEdge &a, size_t idx)
{
return a.start == idx;
}
template <class Point>
struct random_point
{
Point operator()() const
{
return Point(rand() % 1000 - 500, rand() % 1000 - 500);
}
};
const HalfEdge& find_edge(const vector<HalfEdge>& list, size_t start)
{
for (const_edge_iterator it=list.begin(); it!=list.end(); ++it)
if (it->start == start) return *it;
throw runtime_error("find_edge: requested edge not found");
}
/// \brief Outputs random, non self-intersecting polygon with \a N vertices
template <class Point, class OutputIterator>
void generate_random_polygon(unsigned int N, OutputIterator out)
{
if (N<3) return;
vector<Point> vertices(N);
generate(vertices.begin(), vertices.end(), random_point<Point>());
vector<HalfEdge> edgelist(2);
edgelist.reserve(N);
edgelist[0] = HalfEdge(0,1);
edgelist[1] = HalfEdge(1,0);
non_intersecting_edges<Point> generator(vertices,edgelist);
for (size_t i=2; i<vertices.size(); ++i)
generator(i);
int index=0;
for (unsigned int i=0; i<N; ++i)
{
const HalfEdge &edge = find_edge(edgelist, index);
*out++ = vertices[edge.start];
index = edge.end;
}
}
1
一个想法:生成一串随机点的,然后使用alpha shapes它们括起来。
有一个参数可以调整以确定最终的多边形是多么“紧密”。
另一个想法:产生一串随机形状的,然后compute their union(例如生成随机简单的多边形,或者使用metaballs。)。
虽然您可能需要使用一些技巧来确保联合仅为单一形状。
相关问题
- 1. 在封闭的多段线上画一个多边形
- 2. 多边形不封闭
- 3. 创建封闭区域多边形的算法
- 4. 为封闭多边形寻找Douglas-Peucker算法的好起点
- 5. 连接在简单的xy走向最终和初始点(绘制封闭曲线/多边形)
- 6. 设计一个随机生成的简单(非交叉)曲线
- 7. 创建封闭的空间多边形
- 8. 形成一个凸多边形的算法
- 9. QGraphicsPolygonItem绘制一个开放的(不封闭的)多边形
- 10. 将简单多边形的轮廓样条轮廓线转换成简单的多边形
- 11. 计算平面上封闭多边形的面积
- 12. 生成一个简单的折线图
- 13. 任意四边形网格生成最简单的算法是什么?
- 14. 用于多个多边形的点多边形算法
- 15. 如何在一组简单多边形中分割多边形
- 16. 多边形化一个像素化的2D曲线
- 17. 在多边形中生成均匀分布点的算法
- 18. SVG - 如何填充其边从贝塞尔曲线形成的多边形?
- 19. 获取简单多边形
- 20. 简单封闭的困境
- 21. R:多边形不与曲线对齐
- 22. 如何生成面积相等但边长不变的简单多边形
- 23. 找到四边形内最大的矩形的简单算法
- 24. 处理多边形的多边形算法,处理跨边界的多边形
- 25. 生成二维多边形的斜边
- 26. 生成具有固定内边的多边形三角剖分的算法?
- 27. 使用相同的多个矩形覆盖直线多边形的算法
- 28. 从边界点创建封闭多边形
- 29. 从弧形边缘画一条曲线
- 30. Python龟图形填充非封闭多边形