본문 바로가기

Python_Matter/Solve

Python Learn the basics Quiz 91

반응형

Q>

When it comes to city planning it's import to understand the borders of various city structures.

(도시 계획에 관해서는 다양한 도시 구조의 경계를 이해하는 것이 수입입니다.)

Parks, lakes or living blocks can be represented as closed polygon and can be described using cartesian coordinates on a map .

(공원, 호수 또는 살아있는 블록은 닫힌 다각형으로 표현할 수 있으며지도의 직교 좌표를 사용하여 설명 할 수 있습니다.)

We need functionality to determine is a point (a building or a tree) lies inside the structure.

(우리는 구조 (건물 또는 나무)가 구조 안에 있는지를 결정하는 기능이 필요합니다.)

For the purpose of this mission, a city structure may be considered a polygon represented as a sequence of vertex coordinates on a plane or map.

(이 임무의 목적을 위해, 도시 구조는 비행기 또는지도에서 정점 좌표의 시퀀스로 표현되는 다각형으로 간주 될 수 있습니다.)

The vertices are connected sequentially with the last vertex in the list connecting to the first.

(정점은 첫 번째 정점에 연결된 목록의 마지막 정점과 순차적으로 연결됩니다.)

We are given the coordinates of the point which we need to check.

(우리는 점검 할 필요가있는 지점의 좌표를받습니다.)

If the point of impact lies on the edge of the polygon then it should be considered inside it.

(임팩트 포인트가 다각형의 가장자리에 있으면 그 안에 고려해야합니다.)

For this mission, you need to determine whether the given point lies inside the polygon.

(이 임무에서는 주어진 점이 다각형 안에 있는지 여부를 결정해야합니다.)

For example, on the left image you see a polygon which is described by ((2,1),(1,5),(5,7),(7,7),(7,2)) and the point at (2,7). The result is False.

(예를 들어, 왼쪽 이미지에서 ((2,1), (1,5), (5,7), (7,7), (7,2))로 설명되는 다각형과 (2,7). 결과는 거짓입니다. )
For the right image the point lies on the edge and gets counted as inside the polygon, making the result True.

(오른쪽 이미지의 경우 점이 모서리에 있고 폴리곤 내부로 계산되어 결과가 참이됩니다.)

 

Input: Two arguments. Polygon coordinates as a tuple of tuples with two integers each.

         (두 개의 인수. 다각형은 각각 두 개의 정수가있는 튜플의 튜플로 조정됩니다.)

         A checking point coordinates as a tuple of two integers.

         (검사 점은 두 정수의 튜플로 조정됩니다.)

 

Output: Whatever the point inside the polygon or not as a boolean.

           (다각형 안의 어떤 점이나 부울이 아닌지.)

 

Example:

is_inside(((1,1),(1,3),(3,3),(3,1)), (2,2)) == True
is_inside(((1,1),(1,3),(3,3),(3,1)), (4,2)) == False

 

How it is used: This concept is using for image recognizing.

                     (이 개념은 이미지 인식에 사용됩니다.)

                     But as we said early it can be useful for topographical software and city planning.

                     (그러나 우리가 일찍 말했듯이 지형 소프트웨어와 도시 계획에 유용 할 수 있습니다.)

 

Precondition:
all(x ≥ 0 and y ≥ 0 for x, y in polygon)
point[0] ≥ 0 and point[1] ≥ 0

 

A>

class Line(object):
    # 교차 검사
    def __init__(self, point1, point2):
        self.point1 = point1
        self.point2 = point2

    def intersect_with(self, another_line):

        """Canother_line이 자신과 교차하는지 검사.
        Args:
            another_line (Line): 다른 선
        Returns:
            bool: 교차 할 때 true를 반환합니다.
        """

        # 일반 및 특수 사례에 필요한 네 가지 방향 찾기
        o1 = self.orientation(self.point1, self.point2, another_line.point1)
        o2 = self.orientation(self.point1, self.point2, another_line.point2)
        o3 = self.orientation(another_line.point1, another_line.point2, self.point1)
        o4 = self.orientation(another_line.point1, another_line.point2, self.point2)

        # 일반적인 경우
        if o1 != o2 and o3 != o4:
            return True

        # 특수한 경우
        # p1, q1 및 p2는 동일 선상에 있고 p2는 세그먼트 p1q1에 놓여 있습니다
        if o1 == 0 and self.on_segment(self.point1, another_line.point1, self.point2):
            return True

        # p1, q1 및 p2는 동일 선상에 있고 q2는 세그먼트 p1q1에 놓여있다
        if o2 == 0 and self.on_segment(self.point1, another_line.point2, self.point2):
            return True

        # p2, q2 및 p1은 동일 선상에 있고 p1은 세그먼트 p2q2에 놓여 있습니다
        if o3 == 0 and self.on_segment(
                another_line.point1, self.point1, another_line.point2
        ):
            return True

        # p2, q2 및 q1은 동일 선상에 있고 q1은 세그먼트 p2q2에 놓여있다
        if o4 == 0 and self.on_segment(
                another_line.point1, self.point2, another_line.point2
        ):
            return True

        # 위의 경우에 해당되지 않습니다.
        return False

    def on_segment(self, point1, point2, point3):
        """체크 포인트 q가 라인 pr에 있는지 여부
        주어진 3 개의 공선 점 p, q, r
        함수는 점 q가 선분 'pr'에 있는지 검사합니다.
        Args:
            point1 (Point): p
            point2 (Point): q
            point3 (Point): r
        Returns:
            bool: true를 반환합니다.
        """

        if (
                point2.x <= max(point1.x, point3.x)
                and point2.x >= min(point1.x, point3.x)
                and point2.y <= max(point1.y, point3.y)
                and point2.y >= min(point1.y, point3.y)
        ):
            return True
        else:
            return False

    def orientation(self, point1, point2, point3):
        """순서가있는 삼중 항의 방향을 찾으려면 (p, q, r).
        Args:
            point1 (Point): p
            point2 (Point): q
            point3 (Point): r
        Returns:
            int: 0 --> 0 -> p, q 및 r은 동일 선상에 있음
                 1 --> 시계방향
                 2 --> 반시계방향
        """
        val = (point2.y - point1.y) * (point3.x - point2.x) - (point2.x - point1.x) * (
                point3.y - point2.y
        )
        if val == 0:
            return 0
        elif val > 0:
            return 1
        else:
            return 2

    def double_length(self):
        """
        현재 줄의 길이를 point1에서 point2로 두 배로 늘립니다.
        Returns:
            tuple: 새로운 엔드포인트
        """
        return (
            self.point1.x + 2 * (self.point2.x - self.point1.x),
            self.point1.y + 2 * (self.point2.y - self.point1.y),
        )

class Point(object):
    # 점의 클래스. 주로 Line 클래스에서 사용된다.
    def __init__(self, x, y):
        self.x = x
        self.y = y

def is_inside(polygon, point):
    line2 = Line(Point(point[0], point[1]), Point(100, point[1]))
    intersections = 0
    point_pairs = [i for i in zip(polygon, polygon[1:])] + [(polygon[-1], polygon[0])]
    while point_pairs:
        # 다각형을 역으로 그립니다.
        i = point_pairs.pop()
        q1 = Point(i[0][0], i[0][1])
        p1 = Point(i[1][0], i[1][1])
        line1 = Line(p1, q1)
        if line1.intersect_with(line2):
            # 교차로를 찾을 때 길이를 두 배로 늘린다.
            if point_pairs:
                point_pairs[-1] = (point_pairs[-1][0], line1.double_length())
            if line1.orientation(p1, Point(*point), q1) == 0:
                return line1.on_segment(p1, Point(*point), q1)
            intersections += 1

    if intersections % 2:
        return True
    else:
        return False

if __name__ == '__main__':
    assert is_inside(((1, 1), (1, 3), (3, 3), (3, 1)),
                     (2, 2)) == True, "First"
    assert is_inside(((1, 1), (1, 3), (3, 3), (3, 1)),
                     (4, 2)) == False, "Second"
    assert is_inside(((1, 1), (4, 1), (2, 3)),
                     (3, 2)) == True, "Third"
    assert is_inside(((1, 1), (4, 1), (1, 3)),
                     (3, 3)) == False, "Fourth"
    assert is_inside(((2, 1), (4, 1), (5, 3), (3, 4), (1, 3)),
                     (4, 3)) == True, "Fifth"
    assert is_inside(((2, 1), (4, 1), (3, 2), (3, 4), (1, 3)),
                     (4, 3)) == False, "Sixth"
    assert is_inside(((1, 1), (3, 2), (5, 1), (4, 3), (5, 5), (3, 4), (1, 5), (2, 3)),
                     (3, 3)) == True, "Seventh"
    assert is_inside(((1, 1), (1, 5), (5, 5), (5, 4), (2, 4), (2, 2), (5, 2), (5, 1)),
                     (4, 3)) == False, "Eighth"

 

O>

is_inside(((5,1),(1,5),(5,9),(9,5),(5,5)),(6,4)))

 Your result: false

 

S>

https://py.checkio.org/

반응형

'Python_Matter > Solve' 카테고리의 다른 글

Python Learn the basics Quiz 93  (0) 2019.06.23
Python Learn the basics Quiz 92  (0) 2019.06.22
Python Learn the basics Quiz 91  (0) 2019.06.21
Python Learn the basics Quiz 90  (0) 2019.06.21
Python Learn the basics Quiz 89  (0) 2019.06.21
Python Learn the basics Quiz 88  (0) 2019.06.21