Проверьте, находится ли точка внутри отрезка плоскости - PullRequest
Новая
       106

Проверьте, находится ли точка внутри отрезка плоскости

1 голос
/ 09 марта 2012

Я хотел бы знать, если точка в сегменте плоскости и ее координаты в [0,1] [0,1] относительно сегмента. например, 0,0 левый нижний угол, 1,1 правый верхний угол, 0,5,0,5 центр

это то, что я уже знаю:

-точка находится в той же плоскости, что и сегмент плоскости. координаты 4-х точек отрезка плоскости. но это не порядок по часовой стрелке или порядок, который я бы знал. Самолет нормальный и его расстояние до начала координат. такие как; ax + by + cz + d. x, y, z, d известны.

вот эскиз, который я сделал: самолет http://s17.postimage.org/564cjyjy7/plane.png Точки A, B, C находятся на одной плоскости с сегментом плоскости. Координаты P1, P2, P3, P4 известны, но не упорядочены каким-либо значимым образом.

спасибо.

редактирование:

одна идея у меня есть

  • точки сортировки

  • создать вектор между точками

  • создание векторов из 2 точек

  • точечный продукт их

  • если градус находится между 0 и 90, он внутри

это будет работать? мне нужна хорошая производительность в режиме реального времени, разве точка не работает медленно на процессоре? как найти относительную координату точки?

Ответы [ 2 ]

1 голос
/ 09 марта 2012

На мой взгляд, лучший способ проверить это - преобразовать всю плоскость и точки в начало системы координат: перевести каждую точку так, чтобы левая нижняя точка была в центре системы координат, и повернуть все так, чтобы она была нормальной вектор будет указывать параллельно одной из осей. Это означает умножение матрицы для каждой точки, но после этого вы можете легко проверить, какие точки находятся в прямоугольнике. Это реализация XNA C #, но логика везде одинакова: (Я пытался использовать ваш эскиз для входных данных) 

// Inputs - Right handed coordinate system
Vector3 p1 = new Vector3(-1.0f, 1.0f, 1.0f);  // left top
Vector3 p2 = new Vector3(1.0f, -1.0f, 0.0f);  // right bottom
Vector3 p3 = new Vector3(1.0f, 1.0f, 1.0f);   // right top, redundant if this is a rectangle
Vector3 p4 = new Vector3(-1.0f, -1.0f, 0.0f); // left bottom

Vector3 a = new Vector3(-0.5f, 0.0f, 0.5f);

// Calculating transformation matrix
Vector3 right = Vector3.Normalize(p2 - p4);
Vector3 forward = Vector3.Normalize(p1 - p4);
Vector3 up = Vector3.Cross(right, forward);

Matrix transform = new Matrix();
transform.M11 = right.X;
transform.M12 = right.Y;
transform.M13 = right.Z;
transform.M14 = 0.0f;
transform.M21 = forward.X;
transform.M22 = forward.Y;
transform.M23 = forward.Z;
transform.M24 = 0.0f;
transform.M31 = up.X;
transform.M32 = up.Y;
transform.M33 = up.Z;
transform.M34 = 0.0f;
transform.M41 = p4.X;
transform.M42 = p4.Y;
transform.M43 = p4.Z;
transform.M44 = 1.0f;

transform = Matrix.Invert(transform);

// Transforming
Vector3 tp1 = Vector3.Transform(p1, transform);
Vector3 tp2 = Vector3.Transform(p2, transform);
Vector3 tp3 = Vector3.Transform(p3, transform);
Vector3 tp4 = Vector3.Transform(p4, transform);
Vector3 ta = Vector3.Transform(a, transform);

ta.X /= tp2.X; // divide with rectangle width
ta.Y /= tp1.Y; // divide with rectangle height

// Now everything is on the XY plane
// P1: {X:0    Y:2.236068 Z:0}
// P2: {X:2    Y:0        Z:0}
// P3: {X:2    Y:2.236068 Z:0}
// P4: {X:0    Y:0        Z:0}
// A:  {X:0.25 Y:0.5      Z:0}

Это работает для любых четырех точек.

Это не самое быстрое решение, но я уверен, что оно самое чистое и простое, если вы знаете преобразования матриц. Если вы найдете более быстрое и в то же время простое решение, мне тоже интересно, но, вероятно, проблем с производительностью не будет. На моем процессоре Intel 2.4 ГГц это вычисление происходит без проблем более 1 миллиона раз за 1 секунду. Надеюсь, это поможет, удачи!

0 голосов
/ 10 марта 2012

я нашел способ найти то, что я хочу.вот оно: (код C ++ / Ogre) 

    // top or bottom vector of rectangle
Ogre::Vector3 right = Ogre::Vector3(vertices[3] - vertices[2]); 
right.normalise();
    // vector opposite of the top vector
Ogre::Vector3 left = Ogre::Vector3(vertices[0] - vertices[1]); 
left.normalise();


    // you may store above values if rectangle doesnt move much. this would reduce amount of operations


    // vector from top vertex to position we are checking
Ogre::Vector3 p2ToPos = Ogre::Vector3(pos - vertices[2]);
p2ToPos.normalise();

    // vector from bot vertex to position we are checking
Ogre::Vector3 p1ToPos = Ogre::Vector3(pos - vertices[1]);
p1ToPos.normalise();

    // angle between our vectors
Ogre::Real dot1 = p2ToPos.dotProduct(right);
Ogre::Real dot2 = p1ToPos.dotProduct(left);

    // is both dot products (which gives cos) are positive point is between our rectangle
if(dot1 > 0 && dot2 > 0)
    return true;

это вычисляет то, что мы хотим, только с двумя нормализованными функциями и двумя точечными произведениями.

...