在高度图上插点 [英] interpolate points on a height map

问题描述

我在均匀分布的平面(例如实际温度)上有一些值(字节)，例如温度. 我正在尝试生成整个表面.但是我没有成功.

I have some values (bytes) over a plane evenly distributed (the come from real measures) like for instance temperature. I'm trying to generate the whole surface. But I'm not successful.

主要条件是不知道点的数量和位置，并且表面必须在要测量的点中保留值，并在其之间进行插值.

The main condition is that the number and position of the points will not be known and that the surface MUST keep the value in the points where is measured and the points in between will be interpolated.

理想情况下，如果只设置一个点，则最终曲面应该是山峰.

Ideally, if only one point is set the final surface should be a mountain.

顺便说一句，以防万一.我在WPF(C#)上对其进行编码，最好不要涉及繁重的库或如此小的工作

By the way, and just in the case that it may help. Im coding it on WPF (C#) and it would nice to not involve heavy libraries or whatever for such an small job

提前谢谢！

推荐答案

典型的方法是构建 Delaunay对该区域中的样本集进行三角剖分(在您的情况下为矩形)，然后使用发现的三角形作为曲面.

The typical way is to build a Delaunay triangulation of the sample set in the domain (a rectangle in your case), then use the triangles found as the surface.

一般点集的Delaunay三角剖分定义为外接圆不包含任何其他点的三角形集.

The delaunay triangulation of a general set of points is defined as the set of triangles whose circumcircles does not contain any other point.

用于计算Delaunay三角剖分的平凡算法(选择所有三角形以查看是否有任何点在其外接圆范围内)为O(n^4).

The trivial algorithm for computing the Delaunay triangulation (pick all triangles to see if any point is within their circumcircle) is O(n^4).

增量算法在O(n log n)预期时间运行:

• 生成三个点的三角剖分(在您的情况下为四个-房间的四角).
• 每个点
  • 将其添加到三角剖分中.
  • 针对与新点相对的每个边递归
  • 如果边缘不是当前点集的Delaunay三角剖分的一部分，则将其翻转.
  • Generate a triangulation of three points (in your case, four - the corners of the room).
  • For each point
    • add it to the triangulation.
    • for every edge opposite the new point recursively
    • if the edge is not a part of the Delaunay triangulation of the current set of points, flip it.

    分而治之算法也提供了O(n log n)，但也为某些点集提供了O(n log log n).

    The divide and conquer algorithm offers O(n log n) as well, but offers O(n log log n) for some point sets as well.

    一旦有了三角剖分，您只需要通过将一条垂直线与曲面相交来找到测量值:

    Once you have the triangulation, you just need to find the measured value by intersecting a vertical line with the surface:

    • 找到该点所在的三角形ABC.
    • 将点坐标表示为A + k(B-A) + l(C-A)
    • 然后将点值指定为A.value + k(B.value-A.value) + l(C.value-A.value)(将三角形作为[domain x range]空间中的平面进行处理.
    • find the triangle ABC on which the point lies.
    • express the point coordinates as A + k(B-A) + l(C-A)
    • then the point value is given as A.value + k(B.value-A.value) + l(C.value-A.value) (treat the triangle as a plane in the [domain x range] space.

    这篇关于在高度图上插点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！