`
熊滔爱孟涛静
  • 浏览: 124745 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

游戏中判断一群点可否构成凸多边形

阅读更多

下面的代码需要box2d!!!!!!!!!!!

import org.jbox2d.common.Vec2;

public class PolyonUtil {
 private static PolyonUtil instance;
 private float a;
 private float b;
 private boolean x_axis;
 private boolean y_axis;
 private float axis;
 float i;

 public static PolyonUtil getInstance() {
  if (instance == null) {
   instance = new PolyonUtil();
  }
  return instance;
 }

 public void setAB(Vec2 point1, Vec2 point2) {
  if (point1.x == point2.x) {
   if (point1.y != point2.y) {
    y_axis = true;
    axis = point1.x;
   }
  } else if (point1.y == point2.y) {
   if (point1.x != point2.x) {
    x_axis = true;
    axis = point1.y;
   }
  } else {
   y_axis = false;
   x_axis = false;
   a = (point1.y - point2.y) / (point1.x - point2.x);
   b = point1.y - point1.x * a;
  }
 }

 public byte getFlag(Vec2 point) {
  if (y_axis) {
   if (point.x > axis) {
    return 1;
   } else if (point.x < axis) {
    return -1;
   } else {
    return 0;
   }

  } else if (x_axis) {
   if (point.y > axis) {
    return 1;
   } else if (point.y < axis) {
    return -1;
   } else {
    return 0;
   }
  } else {
    i = point.y - a * point.x - b;
   if ((point.y - a * point.x - b) < 0) {
    return -1;
   } else if ((point.y - a * point.x - b) > 0) {
    return 1;
   } else {
    return 0;
   }
  }
 }
}

//下面的函数判断一群点是否构成凸多边形

public boolean isHull(Vec2[] mouseStroke){

int mouseStrokeLength=mouseStroke.length;

for (int i = 0; i < mouseStrokeLength; i+=2) {
   PolyonUtil.getInstance().setAB(mouseStroke[(i) % mouseStrokeLength],
     mouseStroke[(i + 1) % mouseStrokeLength]);
   for (int j = 0, k = 0; j < mouseStrokeLength; j++) {
    if (j == i || j == (i + 1)) {
     continue;
    } else {
     flag[k] = PolyonUtil.getInstance().getFlag(mouseStroke[j
       % mouseStrokeLength]);
     k++;
    }
   }
   for (int l = 0; l < flag.length - 1; l++) {
    if (flag[l] * flag[l + 1] < 0) {
     // ao 当是凹多边形时候
          return false;
    }
   }
  }

return true;

}

分享到:
评论

相关推荐

    Go-polygon-判断点是否在一个多边形区域内支持凸多边形与凹多边形

    在计算机图形学中,判断一个点是否位于一个多边形内部是一项基本任务,这对于游戏开发、地理信息系统、图像处理等领域都非常重要。本知识点将详细介绍如何在Go语言中实现这个功能,支持凸多边形和凹多边形。我们将...

    凹多边形转凸多边形VC6

    在某些算法和应用中,处理凹多边形可能会带来复杂性,因此有时需要将凹多边形转换为由多个凸多边形组成的集合,这个过程称为凸分解。 标题"凹多边形转凸多边形VC6"暗示我们这是一个使用Visual C++ 6.0开发的程序,...

    凸多边形的算法求解方法

    通过输入n个点判断这n个点能否构成凸多边形,是输出是否则输出否!

    最小凸多边形生成算法——Qt实现

    最小凸多边形生成算法是一种在计算机图形学中常见的几何处理技术,它的目的是找到一个包含一组给定点的最小凸包。这个算法在很多领域都有应用,例如数据简化、形状识别、碰撞检测等。Qt是一个跨平台的应用程序开发...

    计算几何点到凸多边形距离

    计算几何计算点到凸多边形距离代码 已在各大oj在线测评通过

    凸多边形三角划分

    "凸多边形三角划分"是一个在计算机图形学领域中常见的问题,特别是在三维建模、游戏开发和物理模拟等场景中。这个问题的目标是将一个凸多边形分割成多个不相交的三角形,这些三角形能够无间隙地覆盖整个多边形。这种...

    凸多边形最小面积四边形包围盒算法

    2. **单共点边情况**:在特殊情况下,最小面积包围盒中的一边(称为单共点边)的中点会与凸多边形的某顶点重合。 基于这些结论,研究者设计了一种时间复杂度为O(n^4)的算法,能够有效地构造出凸多边形的最小面积凸...

    凸多边形最优三角剖分(C语言编写) 算法

    凸多边形最优三角剖分是一种在计算机图形学和计算几何领域中常见的问题,它涉及到如何将一个凸多边形分割成尽可能少的互不相交的三角形,同时满足某些优化目标,如最小化某种权值之和,如边界长度、三角形面积等。...

    opencv 随机凸多边形构建源代码

    在几何学中,凸多边形是一个多边形,其中任意两点之间的线段完全位于多边形内部或边界上。在OpenCV中,我们可以使用点集来表示多边形,并通过一系列的点连接形成封闭的图形。 创建随机凸多边形通常涉及以下几个步骤...

    多边形点集排序--针对凸多边形,按逆时针方向进行排序

    在二维空间中,一个凸多边形是由一系列点(顶点)连接形成的闭合图形,其中任意两点之间的连线都在多边形内部。如果从多边形外部向内射入的任何直线都会与多边形的边界交于连续的两点或不相交,那么这个多边形就是凸...

    凸多边形顶点排序

    了解了凸多边形顶点排序的概念后,我们可以利用这个知识来解决更复杂的问题,如判断点是否在多边形内、求多边形面积、计算多边形周长、以及在游戏和物理模拟中的碰撞检测等。在实际项目中,对凸多边形的高效处理是...

    使用c++计算凸多边形的面积

    在实际编程中,可能还需要处理一些边界情况,例如检查输入的点集是否真的构成了一个凸多边形,或者处理点集为空或只有一个点的情况。此外,如果点集是无序的,可能需要先将其排序,比如按X坐标或Y坐标排序,然后再...

    计算凸多边形面积

    凸多边形面积 【问题描述】 给出平面上一组顶点的坐标,计算出它们所围成的凸多边形的面积. 输入数据表示了如图所示的四边形。其面积为5.00。 评分标准: 本程序允许使用数学库函数,如果你的输出与标准...

    凸多边形的三角剖分

    首先,我们要明确凸多边形的定义:一个多边形如果从任何内部点出发,到所有边界点的连线都位于多边形内部,那么它就是凸多边形。例如,一个正方形或一个圆形都是凸多边形的例子。 在凸多边形的三角剖分中,每增加一...

    opencv 关于如何让创建凸多边形

    在几何学中,一个凸多边形是所有顶点都在同一边的多边形,这意味着从多边形内的任何点向边画直线都不会穿过多边形。在OpenCV中,我们可以使用点集来表示一个凸多边形,每个点由(x, y)坐标对定义。 创建凸多边形的...

    计算几何——凸多边形判断+点在多边形内判断+求点到直线距离.docx

    本文档主要探讨了三个关键概念:凸多边形的判断、点是否位于多边形内部的检测以及求一个点到直线的距离。以下是这三个方面的详细解释: 一、凸多边形判断 在二维平面上,一个凸多边形是由一系列连续的线段(边)围...

    论文研究-中轴求凸多边形直径算法.pdf

    总之,本篇论文研究提供了关于凸多边形直径求解问题的新算法,该算法在实现过程中可能涉及到中轴的快速求解、顶点最近点问题的高效处理以及对凸多边形几何性质的深刻理解。算法的高效性表明它有潜力在计算机图形学...

    判断点是否在多边形内(MFC)

    在计算机图形学中,判断一个点是否位于一个多边形内部是一项基本任务,尤其在MFC(Microsoft Foundation Classes)框架下开发图形用户界面时。本文将详细介绍如何使用射线法(也称为穿越法或Winding Number Test)来...

Global site tag (gtag.js) - Google Analytics