在简单图像中查找角点坐标的算法
我有一个位图，其中两个大颜色块相交，我想找到这两个块的交集。
请注意，我不知道这两个形状的实际几何形状，因为这只是原始像素数据。
有什么算法可以用来做到这一点吗？
I have a bitmap where two large blocks of colors intersect, and I would like to find the intersection of these two blocks.
Note that I do not know the actual geometry of the two shapes, because this is all just raw pixel data.
Is there any algorithm I could use to do this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果内存中拥有所有像素数据（我假设你这样做，但这是一个主要的症结点）并且只有两种不同的颜色，那么你需要做的就是运行水平扫描线来找到其中的点RGB 从颜色 X 变为颜色 Y（请注意，您可能需要运行此扫描线几次，但无论如何它不比 O(height) 差）。
然后，一个简单的图形遍历（BFS 或 DFS）将继续引导您沿着这条线走（您应该只需要 3 个点，然后您将能够使用方程 a*x + b*y + c = 0 形成一条几何线（假设它不是曲线））。
垂直重复这条扫描线（同样，最坏的情况是 O（宽度））。找到 3 个点，然后您将得到两条 d*x + e*y + f = 0 的线。使用一点点 comp。 geom，这两条线的交点将给你你的观点。
If you have all the pixel data in memory (which I'd assume you do, but this is a major sticking point) and there are only two distinct colours, all you should need to do is run a horizontal scanline to find the point where RGB changes from colour X to colour Y (note that you may need to run this scanline a few times, but in any case it's no worse than O(height)).
A simple graph traversal (BFS or DFS) will then continue to walk you down that line (you should only need 3 points and then you'll be able to form a geometric line with equation a*x + b*y + c = 0 (assuming it's not a curve)).
Repeat this scanline vertically (again, worst case it's O(width)). Find 3 points and you'll then have two lines with d*x + e*y + f = 0. Using a little bit of comp. geom, the intersection of these two lines will give you your point.