Точка внутри повернутого 2D прямоугольника (не используя перевод, триггерные функции или точечный продукт)

Мне было интересно, справедлив ли следующий алгоритм для проверки того, находится ли точка внутри прямоугольника. Я разработал его, используя свою собственную интуицию (нет сильной основы триггера/математики для ее поддержки), поэтому я бы хотел услышать от кого-то, у кого больше опыта в этом вопросе.Точка внутри повернутого 2D прямоугольника (не используя перевод, триггерные функции или точечный продукт)

Контекст:

Прямоугольник определяется с 4 очками. Он может быть повернут.
Координаты всегда положительные.
По определению точка рассматривается внутри прямоугольника, если пересекает его.

Гипотеза:

Используйте расстояние между точкой и прямоугольника вершин (первая диаграмма ниже).
Максимальное возможное полное расстояние, когда точка находится в одной вершине (вторая диаграмма).
Если точка находится за пределами прямоугольника, расстояние будет больше (третья диаграмма).

Диаграмма ссылка: http://i45.tinypic.com/id6o35.png

Алгоритм (Java):

static boolean pointInsideRectangle(Point[] rect, Point point) { 
    double maxDistance = distance(rect[0], rect[1]); 
    maxDistance += distance(rect[0], rect[2]); 
    maxDistance += distance(rect[0], rect[3]); 

    double distance = 0; 
    for (Point rectPoint : rect) {   
     distance += distance(rectPoint, point); 
     if (distance > maxDistance) return false; 
    } 
    return true; 
}

Вопросы: это правильно? не

источник

2012-06-07 user1442081

Короткий ответ: НЕТ: P (don't упал плохо об этом)

Длинный ответ: Intersecction области из четырех кругов, которые вы упоминаете (максимальное расстояние между противоположной вершиной) не производят прямоугольник. Common area of four circles of radius equal to the rectangle´s diagonal with center in each corner Поскольку я немного ржавый в геометрии, я не могу дать полное математическое объяснение (ограничение времени для моей части), но даю вам некоторый псевдокод процедуры со строками, которые вы задаете (без фантастических формул), действительными для любого прямоугольника wikipeida или геометрия могут заполнить пробелы.

Найти N, E, S, W вершину (самый верхний, крайний правый, низкий и крайняя левая вершина), это тривиально просто для любого прямоугольника, а ось выровнена, который может производить как ни странно ассигнование из вершины (см изображения с примеры)
Найти границу NE, SE, SW и NW, это уравнение линии in wikipedia или другой link, снова должен быть легким, но ось выровнена граница должна быть тщательно анализируются because those generate another type of ecuation/restriction.
Проверьте, находится ли ваша точка на «правой стороне» границы see inequality as mathematical term, только точка внутри вашего прямоугольника удовлетворяет четырем ограничениям, как вы можете видеть на прилагаемом изображении.
мои извинения, если у меня есть какая-либо команда java.геом, которые могут выполнить эту задачу

Я надеюсь, что это поможет с endevour

источник

2012-06-07 13:34:39 Alen

Я нашел много реализаций этого и многое, многое, намного лучшего алгоритма (глупо меня, я забыл проверить G с помощью «проверить, находится ли точка внутри полигона»), где на этот вопрос ответит множество раз в лучше, чем у меня: [Stackoverflow] (http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test), этот [веб-сайт] (http://alienryderflex.com/polygon/) и в [Wikipeida] (http://en.wikipedia.org/wiki/Point_in_polygon) – Alen

Вы можете попробовать this.Lets назвать точку мы имеем в A.Draw линии между А и каждой точкой прямоугольника. После этого вы получите 4 разных треугольника. Выделите область, в которой треугольники берут (используя формулу Герона), и сравнивайте ее с областью прямоугольника. Если области одинаковы, ваша точка находится внутри прямоугольника. Cheers

источник

2013-02-19 21:20:45 Aleksandar

Точка внутри повернутого 2D прямоугольника (не используя перевод, триггерные функции или точечный продукт)

ответ

Смежные вопросы