三角点指向一个点 [英] triangle points around a point

问题描述

我给出了一个平面上的1000个三角形的坐标（三角形数（T0001-T1000）及其坐标（x1，y1）（x2，y2），（x3，y3））。现在，对于给定点P（x，y），我需要找到一个包含点P的三角形。

一个选项可能是检查所有三角形，找到包含P的三角形，但是，我正在寻找针对此问题的有效解决方案。

解决方案

您将不得不在执行程序期间，检查某个点处的每个三角形。这显然是正确的？如果你想最大化这个计算的效率，那么你将创建一些缓存数据结构。数据结构的细节取决于您的应用程序。例如：三角形多久改变一次？您需要多长时间计算一次点的位置？

缓存的一种实现方式是：将您的飞机划分为有限的网格框。对于网格中的每个方框，存储可能与方框相交的三角形列表。

然后，当你需要找出你的点在哪个三角形内时，你会首先找出它在哪个盒子（这将是O（1）次，因为你只是看着坐标），然后看看那个盒子的三角形列表中的三角形。

I have given the coordinates of 1000 triangles on a plane (triangle number (T0001-T1000) and its coordinates (x1,y1) (x2,y2),(x3,y3)). Now, for a given point P(x,y), I need to find a triangle which contains the point P.

One option might be to check all the triangles and find the triangle that contain P. But, I am looking for efficient solution for this problem.

解决方案

You are going to have to check every triangle at some point during the execution of your program. That's obvious right? If you want to maximize the efficiency of this calculation then you are going to create some kind of cache data structure. The details of the data structure depend on your application. For example: How often do the triangles change? How often do you need to calculate where a point is?

One way to make the cache would be this: Divide your plane in to a finite grid of boxes. For each box in the grid, store a list of the triangles that might intersect with the box.

Then when you need to find out which triangles your point is inside of, you would first figure out which box it is in (this would be O(1) time because you just look at the coordinates) and then look at the triangles in the triangle list for that box.

这篇关于三角点指向一个点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！