TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

An Algorithm for Polygon Intersections

119 点作者 lnyan超过 2 年前

4 条评论

dahart超过 2 年前
Writing collision detection is really fun. There’s enough in this article to take it and then build a tiny rigid body physics simulation - you only need to add gravity and then work out the forces two rectangles impart on each other when they collide. There’s a change to the center of mass velocity and a change to the rotation velocity.<p>One thing that makes it easier IMO is to use Y-up coordinates. Instead of putting the origin top-left like the article, use bottom-left. If you need, convert screen coordinates to your “world space” and back in some code that is outside of the collision &amp; simulation. There’s no reason to be stuck with the default coordinates, or have to think upside down. (Intersection when “top bound of R1 is less than bottom bound of R2” sounds backwards to me.)<p>Another fun part is accelerating collision detection &#x2F; simulation. This algorithm in the demo code is O(n^2) in total edges, I believe. But you don’t need to change the algorithm necessarily, you can speed it up dramatically with an acceleration structure of some kind. It’s a fun weekend project and satisfying to suddenly be able to add thousands of polygons to your sim without locking up the machine.
EGreg超过 2 年前
22 years ago I wrote this for the special case of rectangles:<p><a href="https:&#x2F;&#x2F;www.flipcode.com&#x2F;archives&#x2F;Theory_Practice-Issue_01_Collision_Detection.shtml" rel="nofollow">https:&#x2F;&#x2F;www.flipcode.com&#x2F;archives&#x2F;Theory_Practice-Issue_01_C...</a>
评论 #33055784 未加载
dvh超过 2 年前
Neat algorithm to detect if point is inside polygon is too draw a random line and count intersections, if it&#x27;s odd the point is inside polygon.<p>I use a lot of operations with basic geometric primitives and whenever I use stackoverflow it takes years to iron out all the special cases in which top stackoverflow answer fails.
评论 #33056068 未加载
评论 #33054364 未加载
lemonade5117超过 2 年前
The blog looks really nice! Definitely gonna read the other posts when I have time.