提's profile袍泽之谊.:*・✿*゚¨゚゚・ ✿.。.:*葡萄...PhotosBlogListsMore Tools Help

Blog


    7/24/2009

    一个不完善的基于边界的面积算法

    偶然看到这个问题。如果有边界坐标怎么算边界围起来的图形面积。我开始建议直接计算图象颜色。不过提出这个问题的人好象希望从几何角度去计算。


    想了一个不成熟的办法。当然可行的算法是要能适应所有图案而不需要改动的。这是计算机科学的魅力所在:

     

    aa

    我临时想了一个算法,或许会有帮助
    已知图形边界如图。共11个顶点,顺序也是知道的。
    所有顶点按横坐标从大到小排序就是:10  11 1 9 8 2 7 4 5 3 6
    然后算三角形的面积。第一个三角形为头三个顶点(10 11 1)。
    后面的三角形的算法两个法则:

    1。每次按顺序增加下一个顶点,舍掉最靠左跟大家相连最多的顶点的,所以是:(10 1 9) (1 9 8) (1 8 2)。。。 这里还有问题

    2。如果该三角形的三个顶点中没有两个点是连续的比如算到(2 74)的时候,接下面应该不是一个三角形而是两个三角形。下两个三角形的坐标为(2 4 a) (7 4 b),a,b来自接下来的两个顶点5,3。具体的顶点5是a还是b要计算如下:5和2,4的差值的绝对值和A,以及5和7,4的差值的绝对值和B。如果 A小5就是a,B小5就是b。顶点3同样的道理。 所以接下来(2 7 4)之后是(2 4 3) (4 5 7)。

     

    3。每个三角形都有继承的三角形。(4 5 7)由(5 7 6)继承。除非这个三角形的新加入点跟旧点都只差1。如:(2 4 3)和(5 7 6)


    当所有的三角形都没有继承的时候。把所有的三角形面积加起来就出来了。


    应该是可行的,呵呵。


    总之一个三角形三个顶点:三个数字都不相邻就分开继承;有两个是数字上相邻的就舍掉靠左的再单一继承;三个都相邻就不用继续了。


    单一继承的规则还有点问题。反正以例子的图形为例,最后的三角形应该是(10 11 1)接(10 1 9)接(1 9 8)接(1 8 2)接(8 2 7)接(2 7 4)然后分为(2 4 3)和(7 4 5)再接(无)和(7 5 6)


    其实起始三角形也不应该只有一个。建议用补码代替里面的十进制数表示顶点,这样可以形成循环,篇号1和11的顶点实际上也是连着的。

     

    实际上这样的计算对于复杂的边界描述要遍历到所有三角形是需要很多计算的,应该有一个数学模型来描述他。我还是比较赞成计算颜色用滤波器来算面积。

    Comments

    Please wait...
    Sorry, the comment you entered is too long. Please shorten it.
    You didn't enter anything. Please try again.
    Sorry, we can't add your comment right now. Please try again later.
    To add a comment, you need permission from your parent. Ask for permission
    Your parent has turned off comments.
    Sorry, we can't delete your comment right now. Please try again later.
    You've exceeded the maximum number of comments that can be left in one day. Please try again in 24 hours.
    Your account has had the ability to leave comments disabled because our systems indicate that you may be spamming other users. If you believe that your account has been disabled in error please contact Windows Live support.
    Complete the security check below to finish leaving your comment.
    The characters you type in the security check must match the characters in the picture or audio.

    To add a comment, sign in with your Windows Live ID (if you use Hotmail, Messenger, or Xbox LIVE, you have a Windows Live ID). Sign in


    Don't have a Windows Live ID? Sign up

    Trackbacks

    The trackback URL for this entry is:
    http://1983alex.spaces.live.com/blog/cns!C243F43AE8B85BBC!1698.trak
    Weblogs that reference this entry
    • None