除以自交的多边形（C code） [英] Divide self intersecting polygon (C Code)

问题描述

我想将一个自交的多边形成简单的多边形。我有边缘，并保存在数据结构中的交叉点（连接列表）。

I want to divide a self-intersecting polygon into simple polygons. I have the edges and the intersection points saved in a data structure (a connected list).

因此​​，这里就是一个例子。我有一个连接列表与x，边缘的y坐标和交叉处的多边形的点。根据在此图象的多边形的这将是::（1） - > （2） - >（3） - >（7）。我正在试图做的是让简单的多边形（三角形在这里）的边缘。在这种情况下:: 1,2,7 / 3,4,5 / 5,6,7

So here is an example. I have a connected list with the x,y coordinates of the edges and the intersection points of the polygon. According to the polygon in this picture it would be :: (1) -> (2) -> (3) ... -> (7). What I'm trying to do is to get the edges of the simple polygons (triangles here). In this case :: 1,2,7 / 3,4,5 / 5,6,7.

推荐答案

我认为的宾利奥特曼将是你最好的选择。有一个很好的交互式可视化这里。另外一个不错的描述这里。

I would think that Bentley-Ottman would be your best bet. There's a nice interactive visualization here. Another nice description here.

这篇关于除以自交的多边形（C code）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！