[질문] 수학적 사고력이 너무 딸린다

[4:15 사이..(14.38)]

x,y 좌표를 가지는 임의의 수많은 점들이 있다.

그 중 몇개를 골라 이어 경계를 만들었을 때,

사용되지 않은 점들이 새로 나뉜 두 부분중 어느 곳에 속하는지 구하는 방법을 제시하시오.

당신은 모든 점들의 좌표를 알고 있습니다.

요 문제에서 막혀버렸음.. 생각나는 방법 다 얘기해주세여...

[익명(121.133)]

각 점들 두개씩 골라서 라인 만들고 저기 먼저 그어진 라인들 하나하나랑 다 intersection 테스트 해보면 되겠네 false면 두 점이 같은 영역 true면 다른 영역

[4:15 사이로(14.38)]

어우 그러네여 감사합니다

[익명(121.133)]

직선이랑 선분이랑 알고리즘 다르니까 주의하셈 2d line segment intersection test 구글링 ㄱㄱ

[4:15 사이로(14.38)]

넵 CCW 일고있어여 이거 쓰면 될거같네여 이해다 되면 적용해볼게여

[익명(121.133)]

위 다른 답변 보니까 내가 까먹은게 있음 intersection 테스트 짝수번 true면 같은 영역으로 분류해야 함 위 답변 보셈

[4:15 사이로(14.38)]

점하나 피벗으로잡고 다른 점 순회하면서 선분 충돌검사했어요! 짜다보니 저도 짝수번충돌 생각나서 짝수번충돌은 충돌안한취급했구요 신경많이써주시네여 ㅎㅎ 고맙습니다!

[츄럴(39.7)]

이거 계산기하학이야 computational geometry

[4:15 사이로(14.38)]

맞아여 도형 마우스로 조각내버리기 알고리즘 만드는 중이었어요 ㅋㅋ

[브닌떼(172.58)]

방법이 너무 많은데 용도를 알면 선택폭을 더 좁힐수 있을듯

[브닌떼(172.58)]

좌표를 다 알기때문에 이어서 만든 경계라도 특정한 transformation 에선 경계는 일직선이 되고 바깥은 왼쪽 내부는 오른쪽으로 간결화도 됨

[브닌떼(172.58)]

전자기학 수학구조에 어떻게든 닫힌 형태면 원형화 시키는 개념도 있고

[브닌떼(172.58)]

평면이면 마주보는 점들 최소거리 중점 구한다음 중점에서 각점 거리만 알아놓아도 안밖 구별가능 할것 같기도 하고

[브닌떼(172.58)]

너무 많다

[브닌떼(172.58)]

이게 인터섹션 테스트인지 모르겠고 함수 두개로 구분해서 각 선 아래 지역 겹치지 않은 구역이 안쪽으로도 되고

[브닌떼(172.58)]

이런걸 왜하는거야

[사이로 4:15(14.38)]

이제야 봤네여 반시계 알고리즘으로 해결했습니다 ㅋㅋ 평행선 부분도 해결 되더라구요 소숫점 오차는 어느정도 조절해야것지만여 .. 폴리곤을 그리는 정점들을 선을 이루는 정점들과 계산해서 두개의 폴리곤으로 분리시키기 위한 과정이었어요! 정상적으로 해결 했구여 하신 말씀 다 이해되진 않지만(특히 전자기학..) 한번더 공부해볼게여 관심 감사합니다 ㅋㅋ