算法找个角落的坐标在一个简单的图像 [英] Algorithm to find the coordinates of a corner in a simple image

问题描述

我有一个位图，其中的颜色两大块相交，我想找到这两个区块的交集。

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?

推荐答案

如果您在内存中的所有像素数据（我认为你这样做，但是这是一个主要症结点）和只有两个截然不同的颜色，所有你需要做的工作是运行水平扫描线找到的地步，从彩色X RGB改变颜色Y（请注意，您可能需要运行该扫描线几次，但在任何情况下，它比啊，不差（高度））。
一个简单的图遍历（BFS或DFS），那么将继续走你失望该行（你应该只需要3分，那么你就能够形成与方程* X + B * Y的几何线条+ C = 0 （假设它不是一个曲线））。
垂直重复该扫描线（同样​​，最坏的情况是O（宽））。找到3分，那么你就必须两条线与D * X + E * Y + F = 0。使用补偿了一点点。 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.

这篇关于算法找个角落的坐标在一个简单的图像的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！