！！！！！！！Java版有史以来最难的算法题。如果觉得你是高手就进来吧。

Question

这个题目严格说起来应该不算很难，因为它实际上是一个二维的题目，前面 honkyjiang(老蒋)已经提示了：三点确定一个平面，我想此题重点在于如何把多边形分解成若干个三角形，对每个三角形的查找点的过程应该是很容易的.至于写文件倒是不难，可以先把所有的行读入一个二维数组，再处理每一行，如果符合则放入另一个相同大小的二维数组，循环直至上面的平面全部遍历完为止。再把处理后的数组写回原来的文本即可。所以，重点还是怎么分割平面成为三角形。胡乱说了点，也不知道对不对，仅供参考。

Answer 1

我想至少要先把所有的点根据他的z分成不同的组，在每个组内讨论会好不少。具体怎么做，我现在还不知道，sorry。

Answer 2

呵呵，差这两百多分变三个三角。hohoho...

Answer 3

use Polygon.contains(Point p) to determine if a point is contained in a polygon. 
This problem is the easiest problem I've heard.

Answer 4

shut up. don't get in my way to get points. hohoo...ha..

Answer 5

那位大侠做出来了，贴出来啊，分不是问题，一定给你。
既然进来了就帮我UP一下再走啦，谢谢了。
UP 一次~

Answer 6

/******************************************************************
 * @author : 没人性 [email protected]
 *****************************************************************/
import java.awt.*;
import java.io.*;
import java.util.*;public class MyWay {
  public static void main(String[] args) {
    String filePath = "";
    Vector points = new Vector();
    while (filePath.equals("")) {
      System.out.println("Please input the file path of the 3D points.");
      System.out.print("File path (or input \"quit\" to quit.): ");
      DataInputStream in = new DataInputStream(System.in);
      try {
        filePath = in.readLine();
        if (filePath.toLowerCase().equals("quit")) {
          System.exit(0);
        }
        FileInputStream fin = new FileInputStream(filePath);
        int c = 0;
        String line = "";
        while ( (c = fin.read()) != -1) {
          if (c != '\r' && c != '\n') {
            line += (char) c;
          }
          else {
            if (!line.equals("")) {
              int x, y;
              float z;
              //suppose the x,y,z divided by space char.
              StringTokenizer st = new StringTokenizer(line);
              if (st.countTokens() == 3 && !line.startsWith("X") &&
                  !line.startsWith(".")) {
                try {
                  x = Integer.parseInt(st.nextToken());
                  y = Integer.parseInt(st.nextToken());
                  z = Float.parseFloat(st.nextToken());
                  Point3D p = new Point3D(x, y, z);
                  points.add(p);
                }
                catch (Exception e) {
                  System.out.println("File format is wrong.");
                  System.out.println(
                      "------------------Error Message------------------");
                  System.out.println("\t" + e.getMessage());
                  System.out.println(
                      "------------------Error Message------------------");
                  filePath = "";
                }
              }
            }
            line = "";
          }
        }
        fin.close();
        //in.close();
      }
      catch (IOException ioe) {
        System.out.println(
            "File path you input is not right. Please input another then try again.");
        System.out.println("------------------Error Message------------------");
        System.out.println("\t" + ioe.getMessage());
        System.out.println("------------------Error Message------------------");
        filePath = "";
      }
    }    //show all points
    int[] xValues=null;
    int[] yValues=null;
    System.out.println(
        "------------------All points in the file------------------");
    for (int i = 0; i < points.size(); i++) {
      Point3D p = (Point3D) points.elementAt(i);
      System.out.println("piont " + i + " :\t(" + p.getOriginalDesc());
    }
    System.out.println(
        "------------------All points in the file------------------");    String pts = "";
    while (pts.equals("")) {
      System.out.println(
          "Select points to generate a polygon.(divided by \",\")");
      System.out.println("For example: to select point 1 and 2 and 8, you should input 1,2,8 then press enter.");
      System.out.print("Points selected :");
      DataInputStream inSelect = new DataInputStream(System.in);
      try {
        pts = inSelect.readLine();
        StringTokenizer st = new StringTokenizer(pts, ",");
        int[] ptIndex = new int[st.countTokens()];
        try {
          for (int i = 0; i < ptIndex.length; i++) {
            ptIndex[i] = Integer.parseInt(st.nextToken());
          }
  xValues = new int[ptIndex.length];
  yValues = new int[ptIndex.length];
          for (int i = 0; i < ptIndex.length; i++) {
            Point3D p = (Point3D) points.elementAt(ptIndex[i]);
            System.out.println("Select piont " + ptIndex[i] + " :\t(" +
                               p.getOriginalDesc());
            xValues[i] = p.getX();
            yValues[i] = p.getY();
          }
        }
        catch (Exception e) {
          System.out.println("Error: " + e.getMessage());
          pts = "";
        }
        //inSelect.close();
      }
      catch (IOException ioe) {
        System.out.println("------------------Error Message------------------");
        System.out.println("\t" + ioe.getMessage());
        System.out.println("------------------Error Message------------------");
        pts = "";
      }    }    // input new z
    String newZ = "";
    float zPos = 0;
    while (newZ.equals("")) {
      System.out.print("Input new Z position of the polygon : ");
      DataInputStream inZ = new DataInputStream(System.in);
      try {
        newZ = inZ.readLine();
        try {
          zPos = Float.parseFloat(newZ);
        }
        catch (Exception e) {
          System.out.println("Error: " + e.getMessage());
          newZ = "";
        }
        //inZ.close();
      }
      catch (IOException ioe) {
        System.out.println("------------------Error Message------------------");
        System.out.println("\t" + ioe.getMessage());
        System.out.println("------------------Error Message------------------");
        newZ = "";
      }    }    // generate a polygon
    Polygon polygon = new Polygon(xValues, yValues, xValues.length);
    System.out.println("Testing point ....");
    for (int i = 0; i < points.size(); i++) {
      //System.out.println(i + "....done");
      Point3D p = (Point3D) points.elementAt(i);
      if (polygon.contains(p.getX(), p.getY())) {
        p.setZ(zPos);
        System.out.println("[ " + i + " ]" + p.getOriginalDesc() + " --> " +
                           p.getNewDesc());      }
    }
    FrmPolygon frm = new FrmPolygon(xValues, yValues, xValues.length);
    frm.setVisible(true);
  }
}class Point3D {
  private int x, y;
  private float z, oz;
  public Point3D(int x, int y, float z) {
    this.x = x;
    this.y = y;
    this.z = z;
    this.oz = z;
  }  public Point3D() {
    this(0, 0, 0);
  }  public int getX() {
    return x;
  }  public void setZ(float z) {
    this.z = z;
  }  public int getY() {
    return y;
  }  public float getZ() {
    return z;
  }  public float getOriginalZ() {
    return oz;
  }  public String getOriginalDesc() {
    return "point(" + getX() + "," + getY() + "," + getOriginalZ() + ")";
  }  public String getNewDesc() {
    return "point(" + getX() + "," + getY() + "," + getZ() + ")";
  }
}class FrmPolygon
    extends Frame {
  private int[] x;
  private int[] y;
  private int c;
  public FrmPolygon(int[] x, int[] y, int c) {
    this.x=x;
    this.y=y;
    this.c=c;
    this.initPos();
    this.setSize(300, 300);
  }  private void initPos(){
    for (int i = 0; i < x.length; i++) {
      x[i]=x[i]*22+25;
      y[i]=y[i]*22+18;
  System.out.println(x[i]+","+y[i]);
    }
  }  public void paint(Graphics g) {
    //super.paint(g);
    g.setColor(Color.BLUE);
    g.fillPolygon(x,y,c);
    g.setColor(Color.RED);
    int k = 0;
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        g.drawString(String.valueOf(k), j*20+50 , i*20+50);
        k++;
      }
    }
  }
}

Answer 7

说明一下：
1、主要的一点正如 wobelisk() 说的。关键的是Polygon类。
2、FrmPolygon类是为了显示点阵和选区的效果，方便检查
3、contains方法对右边界和下边界上的点返回假。如果要边界上的点则在points里加上那几个选中的边界点。
4、我用的点集文件如下：文件以.或空行结束，文件名points.list
X   Y   Z
1  1   12.666
2  1   12.666
3  1   12.666
4  1   12.666
5  1   12.666
6  1   12.666
7  1   12.666
8  1   12.666
9  1   12.666
1  2   12.666
2  2   12.666
3  2   12.666
4  2   12.666
5  2   12.666
6  2   12.666
7  2   12.666
8  2   12.666
9  2   12.666
1  3   12.666
2  3   12.666
3  3   12.666
4  3   12.666
5  3   12.666
6  3   12.666
7  3   12.666
8  3   12.666
9  3   12.666
1  4   12.666
2  4   12.666
3  4   12.666
4  4   12.666
5  4   12.666
6  4   12.666
7  4   12.666
8  4   12.666
9  4   12.666
1  5   12.666
2  5   12.666
3  5   12.666
4  5   12.666
5  5   12.666
6  5   12.666
7  5   12.666
8  5   12.666
9  5   12.666
1  6   12.666
2  6   12.666
3  6   12.666
4  6   12.666
5  6   12.666
6  6   12.666
7  6   12.666
8  6   12.666
9  6   12.666
1  7   12.666
2  7   12.666
3  7   12.666
4  7   12.666
5  7   12.666
6  7   12.666
7  7   12.666
8  7   12.666
9  7   12.666
1  8   12.666
2  8   12.666
3  8   12.666
4  8   12.666
5  8   12.666
6  8   12.666
7  8   12.666
8  8   12.666
9  8   12.666
1  9   12.666
2  9   12.666
3  9   12.666
4  9   12.666
5  9   12.666
6  9   12.666
7  9   12.666
8  9   12.666
9  9   12.666
.

Answer 8

运行：
C:\test>java MyWay
Please input the file path of the 3D points.
File path (or input "quit" to quit.): points.list
------------------All points in the file------------------
piont 0 :       (point(1,1,12.666)
piont 1 :       (point(2,1,12.666)
...
...
...
piont 78 :      (point(7,9,12.666)
piont 79 :      (point(8,9,12.666)
piont 80 :      (point(9,9,12.666)
------------------All points in the file------------------
Select points to generate a polygon.(divided by ",")
For example: to select point 1 and 2 and 8, you should input 1,2,8 then press en
ter.
Points selected :0,46,58,52,8  (选择时按顺/反时针方向)
Select piont 0 :        (point(1,1,12.666)
Select piont 46 :       (point(2,6,12.666)
Select piont 58 :       (point(5,7,12.666)
Select piont 52 :       (point(8,6,12.666)
Select piont 9 :        (point(9,1,12.666)
Input new Z position of the polygon : 15 (选中点的新高度)
Testing point ....
[ 0 ]point(1,1,12.666) --> point(1,1,15.0)
[ 1 ]point(2,1,12.666) --> point(2,1,15.0)
[ 2 ]point(3,1,12.666) --> point(3,1,15.0)
[ 3 ]point(4,1,12.666) --> point(4,1,15.0)
[ 4 ]point(5,1,12.666) --> point(5,1,15.0)
[ 5 ]point(6,1,12.666) --> point(6,1,15.0)
[ 6 ]point(7,1,12.666) --> point(7,1,15.0)
[ 7 ]point(8,1,12.666) --> point(8,1,15.0)
[ 10 ]point(2,2,12.666) --> point(2,2,15.0)
[ 11 ]point(3,2,12.666) --> point(3,2,15.0)
[ 12 ]point(4,2,12.666) --> point(4,2,15.0)
[ 13 ]point(5,2,12.666) --> point(5,2,15.0)
[ 14 ]point(6,2,12.666) --> point(6,2,15.0)
[ 15 ]point(7,2,12.666) --> point(7,2,15.0)
[ 16 ]point(8,2,12.666) --> point(8,2,15.0)
[ 19 ]point(2,3,12.666) --> point(2,3,15.0)
[ 20 ]point(3,3,12.666) --> point(3,3,15.0)
[ 21 ]point(4,3,12.666) --> point(4,3,15.0)
[ 22 ]point(5,3,12.666) --> point(5,3,15.0)
[ 23 ]point(6,3,12.666) --> point(6,3,15.0)
[ 24 ]point(7,3,12.666) --> point(7,3,15.0)
[ 25 ]point(8,3,12.666) --> point(8,3,15.0)
[ 28 ]point(2,4,12.666) --> point(2,4,15.0)
[ 29 ]point(3,4,12.666) --> point(3,4,15.0)
[ 30 ]point(4,4,12.666) --> point(4,4,15.0)
[ 31 ]point(5,4,12.666) --> point(5,4,15.0)
[ 32 ]point(6,4,12.666) --> point(6,4,15.0)
[ 33 ]point(7,4,12.666) --> point(7,4,15.0)
[ 34 ]point(8,4,12.666) --> point(8,4,15.0)
[ 37 ]point(2,5,12.666) --> point(2,5,15.0)
[ 38 ]point(3,5,12.666) --> point(3,5,15.0)
[ 39 ]point(4,5,12.666) --> point(4,5,15.0)
[ 40 ]point(5,5,12.666) --> point(5,5,15.0)
[ 41 ]point(6,5,12.666) --> point(6,5,15.0)
[ 42 ]point(7,5,12.666) --> point(7,5,15.0)
[ 43 ]point(8,5,12.666) --> point(8,5,15.0)
[ 46 ]point(2,6,12.666) --> point(2,6,15.0)
[ 47 ]point(3,6,12.666) --> point(3,6,15.0)
[ 48 ]point(4,6,12.666) --> point(4,6,15.0)
[ 49 ]point(5,6,12.666) --> point(5,6,15.0)
[ 50 ]point(6,6,12.666) --> point(6,6,15.0)
[ 51 ]point(7,6,12.666) --> point(7,6,15.0)
（以上是选中的点，左边是原，右边已经设置了新的高度）
弹出的窗口显示了：如图
http://www.dw-mx.com/forum/temp_img/MyWay.gif

Answer 9

SwordsmanF（没人性）大侠，非常感谢您的回答，我已经又给您开了个100分的帖子请来接分
这是帖子号http://expert.csdn.net/Expert/topic/2395/2395797.xml?temp=.7373773
您的msn我已经加了，希望向您多多学习。

Answer 10

哦，对了。那个窗体我没有实现关闭退出的功能，反正是显示一下效果。在控制台按Ctrl+C可结束程序。