文档章节

经营类游戏:由轴对齐矩形相交判定到判定菱形构成的平行四边形相交判定(一)

李勇2
 李勇2
发布于 2015/03/02 09:38
字数 1186
阅读 389
收藏 1
点赞 0
评论 0

普通多边形之间的相交测试是个复杂的问题,我们只考虑 轴对齐的 菱形问题即菱形的对角线和坐标轴平行的相交问题。

和坐标轴平行的矩形的相交问题:

矩形A B由左上角定点和右下角定点描述, x轴正方向右, y正方向 向下。

             图1

设:A的左上定点 x0y0, 右下 x1 y1    B 左上 x2 y2  右下 x3 y3

二维问题一般降维度处理:

有 如果两个矩形 在 x轴y轴投影都相交, 则两个矩形相交

即: x0 < x3  &&  x2 < x1 && y0 < y3 && y2 < y1

因为两个坐标轴上的相交区域唯一确定一个 矩形

具体的矩形 范围受 坐标的实际大小关系确定


现在我们需要考虑菱形的问题:

菱形的轴是倾斜的, 那么如何求轴上的投影范围, 来进行相交测试呢?

                            图2

好吧,这样计算的确有些困难, 我们参见图1, 可以有个思路, 首先确定一个菱形的包围盒, 任意一个菱形都有唯一的轴对称包围盒。

设一个菱形的坐标轴x方向宽度 2* sizeX,  坐标轴y方向  2* sizeY

考虑:以下三种情况

我们需要求得这些菱形组合的包围盒的大小:

设从左上到右下的为菱形的 轴x方向, 从 右上到坐下 为 菱形轴y方向, sx 为x向 菱形的个数, sy 为y方向个数

情况1:

除了第一个菱形块之外, 其它菱形块每增加一个宽度增加一个sizeX 高度增加 一个 sizeY


宽度 = (2+sy-1)*sizeX (sizeX是单个菱形宽度的一半)  

高度=(2+sy-1)*sizeY (sizeY 是单个菱形高度的一半)

情况2:(最下面的那个)

宽度 = (2+sx-1)*sizeX

高度=(2+sx-1) *sizeY

最后的复杂情况:

先考虑 沿x 方向的 值, 再加上 y方向的值

宽度 = (2+sx-1 + sy-1)*sizeX

高度 = (2+sx-1 + sy-1)*sizeY


实际上简化之后:

宽度 = (sx+sy)*sizeX

高度 = (sx+sy)*sizeY


这些拼接图形的中点 , 就是他们 包围盒的中点?

可以做上辅助线。 我们根据平线线的分割原理就可以证明


下一个问题是求得这个拼接图形的四个定点的位置; 首先我们需要假定 坐标轴的 0,0点在包围盒的左上角, x向右 ,y向下

上图就是四个顶点的所在位置的值。


最后如何判定相交?

考虑倾斜的轴构成的坐标系:

求一个点在这两个轴上的投影长度 , 可以采用内积:

x轴向: (sizeX, sizeY)

y轴向:(-sizeX, sizeY)

t1 = (x, y) *(sizeX, sizeY)/ ( |(x, y)|)

t2 = (x, y)*(-sizeX,  sizeY) /|(x, y)|



所以向判断 矩形一样判断 t1 t2的范围就可以了



下面是pyhon代码:

import math
sizeX = 135/4
sizeY = 67/4

#菱形拼图的x y 长度 和 中心位置
ab = sx1, sy1, x1, y1 = 2, 2, 0, 0
bb = sx2, sy2, x2, y2 = 2, 2, -40, 20

#求得一个拼图的左上角点和右下角点
def getBoundary(arg):
    sx, sy, x, y = arg
    x0 = x - (sx+sy)/2*sizeX
    y0 = y - (sx+sy)/2*sizeY
    x1 = x0 + sy*sizeX
    y1 = y0
    x2 = x0 + sx*sizeX
    y2 = y0 + (sx+sy)*sizeY
    print [x0, y0, x1, y1, x2, y2, sizeX, sizeY]
    return [x1, y1, x2, y2]

#求得一个点在x方向的投影
def getT1(x, y):
    if x == 0 and y == 0:
        return 0
    return (x*sizeX+y*-sizeY)/math.sqrt(x*x+y*y)/math.sqrt(sizeX*sizeX+sizeY*sizeY)
#求得一个点在y方向的投影
def getT2(x, y):
    if x == 0 and y == 0:
        return 0
    return (x*-sizeX+y*-sizeY)/math.sqrt(x*x+y*y)/math.sqrt(sizeX*sizeX+sizeY*sizeY)
def getABound(a):
    a = getBoundary(a)
    t1 = getT1(a[0], a[1])
    t2 = getT2(a[0], a[1])
    t11 = getT1(a[2], a[3])
    t22 = getT2(a[2], a[3])
    print [a, t1, t2, t11, t22]
    return [t1, t2, t11, t22]
def main():
    aBound = getABound(ab)
    bBound = getABound(bb)
    print aBound
    print bBound
main()


错了:

不能通过 求内积来求 点在菱形边上的投影, 只有当菱形的边互相垂直的时候才成立;

这是因为 非直角 不是 普通的几何。


那么该怎么办呢? 如何计算相交?

这个我 再想想



如果我们约束 所有的菱形拼图都是 n*n的话, 存在一种解法:

可以计算两个拼图中心的 x y 差值

再根据 拼图的 边的宽度 = sx*sizeX,  sx*sizeY    

只要保证两个拼图的 x , y 差值 不 小于 边的宽度 就可以了


拼图中心相差的 x y 方向的格子数目, abs(difx)+abs(dify) >= boundA + boundB  则不相交


本文转载自:http://blog.csdn.net/liyong748/article/details/7562170

共有 人打赏支持
李勇2

李勇2

粉丝 45
博文 188
码字总数 62209
作品 0
广州
程序员
BASIC-18 基础练习 矩形面积交

  在每行中,给出矩形的一对相对顶点的坐标,每个点的坐标都用两个绝对值不超过10^7的实数表示。 2 2 4 4 1.00 思路解析: 这次做题很有感触,就像做数学题一样,要学会抽象做起来才舒服 总体...

xnh_565175944 ⋅ 05/12 ⋅ 0

js之拖动节点放置链路上

在做项目的时候,甲方要求节点之间的连接关系如果不是直接相连,而是通过一系列网络设备如路由器才存在的连接关系。那么把中间这些路由器封装起来用一个云节点表示,在画布上拖动这个云节点到...

亭芳 ⋅ 2014/04/04 ⋅ 0

网页版几何画板开发笔记(十六) 作图检测说明

(已经过时, 新版的在: http://my.oschina.net/u/232554/blog/368393 ) 作图检测现在分为结果检测和过程检测两种: 结果检测: 判断是否有平行,垂直等最终结果的检测方式, 不区分如何作图出这些...

刘军兴 ⋅ 2013/12/16 ⋅ 0

POJ 1328: Radar Installation

题目在此 解题思路: 以岛屿坐标为圆心,输入值为半径画圆,此圆会与 X 轴相交于 S、E 两点(岛屿 Y 坐标等于圆半径时,交一点;Y 坐标大于圆半径的情况提前排除,不参与后面的计算)。然后对...

Alexander_zhou ⋅ 2014/02/22 ⋅ 0

判断两个矩形是否相交的算法

判断矩形是否相交,有很多种方法,比如说判断矩形的任意两条边是否相交。但是这种方法存在一个缺陷,就是当一个矩形被另外一个矩形包含的时候,没有边是相交的但是依然符合相交的定义 另一种...

robslove ⋅ 2015/09/27 ⋅ 0

《C++游戏开发》十八 角色在障碍物中智能行走的实现

最近一直在忙着写一个游戏,其中融入了RPG元素,有人物的行走与障碍物判定。 一般而言,当人物行走时碰到障碍物时应该停止不动,就像下面这样 这样的实现非常简单,每次移动前判断人物的矩形...

左岸流年 ⋅ 2013/09/13 ⋅ 1

判断线段相交是否相交

一.矢量基本知识 因为后面的计算需要一些矢量的基本知识,这里只是简单的列举如下,如果需要更加详细的信息,可以自行搜索wikipedia或google。 1.矢量的概念:如果一条线段的端点是有次序之分...

robslove ⋅ 2015/09/27 ⋅ 0

自动几何推理的研究(二) 线

现在研究线. 线对象被大量使用, 为此需要仔细分析. 线对象大致分两类: 线段(LSegment), 直线(LLine). 线段(LSegment) 主要用于线段相等记录(CongSeg), 线段等比(Ratio_Seg)记录中, 也用于线段...

刘军兴 ⋅ 2015/04/15 ⋅ 0

计算几何算法概览

计算几何算法概览 一、引言   计算机的出现使得很多原本十分繁琐的工作得以大幅度简化,但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案,比如几何问题。作为...

山哥 ⋅ 2014/04/10 ⋅ 1

判断两个矩形是否相交

说矩形相交算法之前,先看下如何判断两条线段是否相交 如果有两条线段 [a, b],[c, d](a, b, c, d 为 X 轴坐标点),有下面两种不相交的情况: 1)b < c 时,线段 [a, b] 在 [c, d] 的左边不...

晓寒 ⋅ 2014/09/06 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

个人博客的运营模式能否学习TMALL天猫质量为上?

心情随笔|个人博客的运营模式能否学习TMALL天猫质量为上? 中国的互联网已经发展了很多年了,记得在十年前,个人博客十分流行,大量的人都在写博客,而且质量还不错,很多高质量的文章都是在...

原创小博客 ⋅ 43分钟前 ⋅ 0

JavaScript零基础入门——(十一)JavaScript的DOM操作

JavaScript零基础入门——(十一)JavaScript的DOM操作 大家好,欢迎回到我们的JavaScript零基础入门。最近有些同学问我说,我讲的的比书上的精简不少。其实呢,我主要讲的是我在开发中经常会...

JandenMa ⋅ 今天 ⋅ 0

volatile和synchronized的区别

volatile和synchronized的区别 在讲这个之前需要先了解下JMM(Java memory Model :java内存模型):并发过程中如何处理可见性、原子性、有序性的问题--建立JMM模型 详情请看:https://baike.b...

MarinJ_Shao ⋅ 今天 ⋅ 0

深入分析Kubernetes Critical Pod(一)

Author: xidianwangtao@gmail.com 摘要:大家在部署Kubernetes集群AddOn组件的时候,经常会看到Annotation scheduler.alpha.kubernetes.io/critical-pod"="",以表示这是一个关键服务,那你知...

WaltonWang ⋅ 今天 ⋅ 0

原子性 - synchronized关键词

原子性概念 原子性提供了程序的互斥操作,同一时刻只能有一个线程能对某块代码进行操作。 原子性的实现方式 在jdk中,原子性的实现方式主要分为: synchronized:关键词,它依赖于JVM,保证了同...

dotleo ⋅ 今天 ⋅ 0

【2018.06.22学习笔记】【linux高级知识 14.4-15.3】

14.4 exportfs命令 14.5 NFS客户端问题 15.1 FTP介绍 15.2/15.3 使用vsftpd搭建ftp

lgsxp ⋅ 今天 ⋅ 0

JeeSite 4.0 功能权限管理基础(Shiro)

Shiro是Apache的一个开源框架,是一个权限管理的框架,实现用户认证、用户授权等。 只要有用户参与一般都要有权限管理,权限管理实现对用户访问系统的控制,按照安全规则或者安全策略控制用户...

ThinkGem ⋅ 昨天 ⋅ 0

python f-string 字符串格式化

主要内容 从Python 3.6开始,f-string是格式化字符串的一种很好的新方法。与其他格式化方式相比,它们不仅更易读,更简洁,不易出错,而且速度更快! 在本文的最后,您将了解如何以及为什么今...

阿豪boy ⋅ 昨天 ⋅ 0

Python实现自动登录站点

如果我们想要实现自动登录,那么我们就需要能够驱动浏览器(比如谷歌浏览器)来实现操作,ChromeDriver 刚好能够帮助我们这一点(非谷歌浏览器的驱动有所不同)。 一、确认软件版本 首先我们...

blackfoxya ⋅ 昨天 ⋅ 0

线性回归原理和实现基本认识

一:介绍 定义:线性回归在假设特证满足线性关系,根据给定的训练数据训练一个模型,并用此模型进行预测。为了了解这个定义,我们先举个简单的例子;我们假设一个线性方程 Y=2x+1, x变量为商...

wangxuwei ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部