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

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

0 голосов
/ 20 сентября 2018

У меня есть 2D-план с целочисленными координатами.

На этом плане есть много точек, разделенных на три категории.

  • "Источник".Существует только одна точка, которая является источником.
  • Группа Ниццы, содержащая неизвестное (но разумное) количество точек
  • Группа Зла, содержащая неизвестное (но разумное) числоОчки

Прежде всего я пытаюсь выяснить (да / нет), находятся ли две группы в отдельных полушариях.

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

Второй шаг - выяснить угол этого полушария.В первом примере (ниже) я нарисовал угол 180 градусов (прямая линия), но я хотел бы рассчитать наиболее несбалансированный угол (близкий к 0), который позволил бы идеально разделить группы.Линия тогда будет двумя половинками, начинающимися с источника, идущего в бесконечность.Я хочу знать наименьший угол (то есть, по логике, наибольший угол, если вы измеряете другую сторону), при котором первый тест остается истинным

Примеры:

1: enter image description here

2: enter image description here

3: enter image description here

Сейчас я могу,через код, чтобы вычислить угол между каждой отдельной точкой и источником.Я застрял в том, чтобы выяснить, как проверить «единство» групп и, самое главное, отсутствие члена другой группы между ними.

Я работаю в C #, но этот вопрос действительнобольше об алгоритме (я не могу думать о рабочем), поэтому я приму любой ответ, который решает проблему на любом (читаемом) языке, включая псевдокод или текстовое объяснение.

Всеиз точек, в контексте, сложные объекты, которые включают координаты X и Y.Другие атрибуты не имеют отношения к вопросу, так как они уже разделены в требуемых группах (источник один, а для остальных есть два списка).

Ответы [ 2 ]

0 голосов
/ 20 сентября 2018

получить наименьший ток х и наименьший ток у группы.и получите самый высокий ... затем сравните другую группу, чтобы увидеть там между ними.если хотя бы одна из других точек найдена между точками (highx, highy) и (lowx, lowy), они смешиваются.если не они разделены ...

как только вы узнаете, что они отделены, нарисуйте линию от вашего самого низкого (x, y) до вашего самого высокого (x, y) и преобразуйте эту линию в исходную точку, давая вамдве «полусферы»

обратите внимание, что это будет работать только в том случае, если они разделены линией, а не углом.

для углов

делайте a и y, когда вы разделенысамый низкий (или самый высокий) x, который другая группа не пересекает, затем сделайте то же самое для y.с этими двумя координатами и вашим происхождением вы сможете определить свой угол.

0 голосов
/ 20 сентября 2018

Вы можете сортировать и сканировать .Давайте введем полярную систему координат с ее началом в начале координат и произвольной осью.

  • Вычислим azimuth для каждой точки (хорошей или злой)
  • Порядокуказывает их azimuth, например
  • Сканирование отсортированной коллекции;если у вас есть 2 или меньше переход между добром к злу или злом к ​​добру;return true, в противном случае false

Например (пусть азимуты в градусах) 

   {nice,  12}
   {nice,  13}
   {nice,  15}
   {nice,  21} // nice to evil transition
   {evil,  47}
   {evil, 121}
   {evil, 133} // evil to nice transition
   {nice, 211}
   {nice, 354}

У нас есть два перехода, ответ true.

   {nice,  12}
   {nice,  13}
   {nice,  15} // nice to evil transition
   {evil, 121}
   {evil, 349}

Только один переход, ответ да 

   {nice,  12}
   {nice,  13} // nice to evil transition
   {evil, 121} // evil to nice transition
   {nice,  15} // nice to evil transition
   {evil, 121} // evil to nice transition
   {nice, 349}

Четыре перехода, точки не могут быть разделены, ответ false

...