张叶安的博客 - 直骨架的研究

边事件

Anonymous (anonymous@undisclosed.example.com) — 2025-10-15T07:29:53+00:00

```cpp void PSLGSSkeleton::handleEdgeEvent(PSLGEdge* event) { sslog::Logf(3, L"[EDGE] t=%.6f types=(%d,%d)", event->vanishTime, (int)event->tailvex->type, (int)event->headvex->type); //��ñ��˻�Ϊһ�� if (event->headvex == event->tailvex) {//如果头尾的节点一样，则删除这个事件 delete event->headvex; delete event; return; } //��¶�� QPointF collisionPoint = event->tailvex->movedPosition( event->vanishTime ); PSLGVertex* collisionvex = new PSLGVertex(collisionPoint, event->vanishTime); //边向内收缩时首次相遇的“交汇点”…

代码分析

Anonymous (anonymous@undisclosed.example.com) — 2025-10-17T02:45:11+00:00

```cpp #include “HDSkeleton_capi.h” #include ``` 这是 C++ 的预处理指令（preprocessor directives）语法，用于在编译前由预处理器处理。逐行解释：这是用户自定义头文件的包含方式。使用双引号 `

射线法

Anonymous (anonymous@undisclosed.example.com) — 2025-10-14T09:25:02+00:00

``` 检查点是否在多边形内（射线法） bool containsPoint(const Point2D& point) const { if (size() < 3) return false; int intersections = 0; int n = size(); for (int i = 0; i < n; ++i) { int j = (i + 1) % n; Point2D p1 = at(i); Point2D p2 = at(j); if

鞋带公式

Anonymous (anonymous@undisclosed.example.com) — 2025-10-14T08:37:21+00:00

``` // 计算面积（使用鞋带公式） double area() const { if (size() < 3) return 0.0; double area = 0.0; int n = size(); for (int i = 0; i < n; ++i) { int j = (i + 1) % n; area += at(i).x * at(j).y; area -= at(j).x * at(i).y; } return std::abs(area) / 2.0; }

abstract

Anonymous (anonymous@undisclosed.example.com) — 2025-09-25T01:54:29+00:00

The straight skeleton is a geometric structure that is similar to generalized Voronoi diagrams. Straight skeletons were introduced to the ﬁeld of computational geometry one and a half decades ago. Since then many industrial and academical applications emerged, such as the computation of mitered oﬀset curves, automatic roof construction, solving fold-and-cut problems and the reconstruction of surfaces, to name the most prominent ones. However, there is a signiﬁcant gap between the most eﬃcient st…

computing_the_straight_skeleton

Anonymous (anonymous@undisclosed.example.com) — 2025-09-25T08:53:37+00:00

In order to make straight skeletons applicable in practice we seek an algorithm which is (i) easy to implement and (ii)exhibits an actual runtime that is relatively close to linear in the input size. Fortune started his introduction [For00] to the 27th volume of Algorithmica with the following words:

introduction

Anonymous (anonymous@undisclosed.example.com) — 2025-09-25T02:04:54+00:00

Assume we are given a simple1 polygon in the plane which constitutes the outer walls of a house in a ground plan. How can we automatically build a roof such that all faces of the roof have equal slope and no rain drop gets caught in a sink? Assume we are given a polygon with holes2 which is to be milled out with a numerically controlled machine (NC machine). How do we compute so-called oﬀset curves of the input such that sharp vertices of the input remain sharp for the oﬀset curve?3 Assume we ar…